Didaktische Hinweise zu TSP
| Da das TSP zu den NP-schweren Optimierungsproblemen gehört, findet man keine so einfachen Lösungsalgorithmen wie für andere Graphen-Optimierungsprobleme. Eine lösgelöste Behandlung dieses Themas im Schulunterricht ist deshalb nur bedingt sinnvoll. Vielmehr bietet sich dieses Thema als Vertiefungsthema nach der Behandlung von Euler-Touren oder minimaler aufspannender Bäume an. Das Problem der Euler-Touren (finde eine Tour durch den Graphen, die jeder Kante genau einmal benutzt) und das Problem der Hamiltonschen Touren (finde eine Tour, die jeden Knoten genau einmal und jede Kante höchstens einmal besucht) scheinen zunächst ähnliche Probleme zu sein. Dennoch ist die Komplexität dieser beiden Probleme sehr unterschiedlich. So ist es leicht (polynomiell lösbar), Mülltouren optimal zu planen, aber eine Sightseeing-Tour zu optimieren ist schwer. Dies kann mit den Schülern diskutiert und an Beispielen ausprobiert werden. Da keine effizienten Algorithmen zur Lösung des TSP bekannt sind, versucht man Verfahren zu finden, um möglicht gute Lösungen zu produzieren. Hier können sich die Schüler auf einem kreativen Feld selbst betätigen. Wir unterscheiden letztlich zwei Klassen von Näherungsverfahren. Die erste Klasse, die sogenannten Heuristiken, suchen irgendwelche Lösungen, die nach der Erfahrung im allgemeinen recht gut sind, was wir aber nicht garantieren können. Der gezeigte evolutionäre Algorithmus und das neuronale Netz sind zwei Beispiele für solche Heuristiken. Die weitaus besseren Algorithmen sind sogenannte Approximationsalgorithmen. Diese liefern zwar nicht immer eine Optimallösung, aber zumindest eine Lösung, deren Wert den einer Optimallösung höchstens um einen konstanten Faktor übersteigt. Sie haben also eine Gütegarantie. Ein solcher Algorithmus für das metrische TSP ist der sogenannte Double-Tree-Algorithmus. Dieser berechnet zunächst einen minimalen aufspannenden Baum der Knoten und fährt diesen Baum vorwärts und rückwärts ab. Wann immer es geht, wird eine Abkürzung genommen. Die so entstandene Tour ist beweisbar höchstens doppelt so lang wie eine optimale Rundtour. (Das hört sich zunächst schlecht an, ist es aber eigentlich gar nicht. In der Praxis ist die gefundene Lösung meistens auch viel besser!) Was bedeutet das für den Unterricht? Nun ja, Schüler könnenn diesen Approximationsalgorithmus selbst finden und seine Güte beweisen! Während einer Unterrichtseinheit zu minimal aufspannenden Bäumen an einem Berliner Gymnasium haben drei Achtklässler die gestellte Einstiegsaufgabe zum MST-Problem selbst abgewandelt und sind so zu der Taxi-Sightseeing-Aufgabe gelangt. Sie haben das Problem des TSP selbst als neue Fragestellung formuliert. Zunächst wollten sie das Problem mit Hilfe eines MST lösen. Im Gespräch stellten sie fest, dass diese Lösung aber doppel gefahren werden muss, was bedeutet, dass die Länge des Baumes verdoppelt werden muss. Sie suchten nun nach einer besseren Lösung, einer optimalen Rundfahrt. Dies war der erste Schritt zum Bewis der Gütefaktors 2 ihrer anfänglichen Lösung. |