Eine Sightseeing-Tour planen

Die folgende Aufgabe wurde von Djamil, Ferdinand und Tayyib aus der achten Klasse eines Berliner Gymnasiums erstellt.
Das Ziel ist, eine optimale Rundfahrt zu den Sehenswürdigkeiten einer Stadt zu planen.
 Lesen Sie mehr...

Traveleling Salesman - Evolutionär

Das Traveling-Salesman Problem gilt als eines der schwierigsten Probleme der kombinatorischen Optimierung. Effiziente Lösungsverfahren sind für dieses Problem nicht bekannt. Wir stellen hier eine Heuristik aus dem Bereich der Evolutionären Algorithmen zur Lösung dieses Problems dar. Lesen Sie mehr...

Traveleling Salesman mit neuronalen Netzen

Eine weitere Klasse von Heuristiken - diesmal aus der künstlichen Intelligenz - liefern die neuronalen Netze. Wiederum am Beispiel des euklidischen TSP wollen wir die Wirkungsweise eines Kohonen-Netzes darstellen. Lesen Sie mehr...

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.
Lesen Sie mehr...