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