vorige

Was passiert beim travelling salesman problem ?


Beim travelling salesman problem ist die Aufgabe zu lösen, dass der salesman eine Rundreise minimaler Länge durchführt, die einerseits durch alle Städte führt, dabei soll er aber jede Stadt genau einmal anfahren. Auf den ersten Blick ist das Problem nicht von den vorigen zu unterscheiden. Daher liegt es nahe, die Lösung nach einer dieser Strategien zu finden. Anders als beim minimal spanning tree ist hier die Auswahl der Nachfolgeknoten, da der Weg in diesem Fall keine Verzweigungen haben darf und sicher keinen Baum darstellt, im Gegenteil aus genau einem Zyklus besteht. Man verwendet in jedem Fall den noch nicht im Weg enthaltenen Knoten, der dem Endknoten ( alternativ einem der beiden Endknoten ) am nächsten ist und setzt den Weg damit fort.

Leider zeigt sich, dass dieser Algorithmus zwar sehr schnell und auch nicht so schlecht ist, aber nicht die optimale Lösung liefert. Ein Beispiel zeigt der folgende Graph, bei dem mögliche Verbesserungen "mit bloßem Auge" zu erkennen sind.

tsp mit einer greedy Strategie

Warum erkennt das Verfahren diese Umwege nicht ?
Man suche nach einem Algorithmus, der ähnlich leistungsfähig ist, aber bessere Ergebnisse liefert!

Das Hauptproblem wollen wir dabei aber nicht aus den Augen verlieren: Bei den vorigen Problemen konnten wir nachweisen, dass sie stets die optimale Lösung liefern, hier haben wir durch Beispiel nachgewiesen, dass der Algorithmus das in diesem Fall nicht kann!