Malen nach Zahlen
Konrad-Zuse-Zentrum für Informationstechnik Berlin
Ein Gesicht in einem Zug gezeichnet? Ähnlich zum „Haus des Nikolaus“ ist das Traveling Salesman Problem (TSP), bei dem ein Handlungsreisender eine kürzeste Tour durch gegebene Städte sucht.
Das Traveling Salesman Problem ist ein typisches kombinatorisches Optimierungsproblem, bei dem mit steigender Anzahl von Städten die Zahl der möglichen Rundtouren dramatisch ansteigt.
Bei 5 Städten gibt es nur 24 mögliche Touren, bei 10 Städten gibt es immerhin schon 362.880 Touren, und bei 20 Städten gibt es bereits 121.645.100.408.832.000, also mehr als 121 Billiarden, mögliche Rundtouren. Clevere Lösungsstrategien sind erforderlich, um diesem Phänomen, auch als kombinatorische Explosion bezeichnet, zu begegnen.
Am Stand der TSP-Gesichter wird ein mathematisches Modell zur Lösung des Traveling Salesman Problems vorgestellt. Außerdem wird das Problem so abgewandelt, dass durch das Zeichnen einer Rundreise ein Foto (z. B. eines Gesichts) skizziert werden kann. Das vorliegende Foto wird dabei zunächst mittels Software auf ein Bild reduziert, dass nur aus wenigen tausend Pixeln besteht, aber noch die wesentlichen Merkmale des fotografierten Gegenstands/Gesichts wiedergibt. Anschließend wird durch die Pixel eine möglichst kurze Rundtour gezogen.
