Die Rundreise – und warum sie schwer ist

Städte:
Der Graph ist vollständig: Zwischen je zwei Städten gibt es eine Straße – das sind n·(n−1)/2 Verbindungen, hell im Hintergrund. Ein Vertreter startet in A, will jede Stadt genau einmal besuchen und wieder zurückkommen. Klicke die Städte in der Reihenfolge an, in der du fahren würdest – die letzte Strecke zurück nach A zieht die Seite selbst. Danach lässt sich die wirklich kürzeste Tour suchen: durch Ausprobieren aller Reihenfolgen. Achte dabei auf die Zahl rechts.

Rückmeldung

Für dieses Experiment werden alle Reihenfolgen durchprobiert. Das ist ehrlich, aber es geht nur bei wenigen Städten – die Tabelle rechts sagt, warum.

Informatik · Algorithmen und Komplexität · aristomenes.de/experimente
Impressum