Das Problem darf also nicht mehr als Entscheidungsproblem (Erfüllungsproblem, Satisfizierungsproblem) beschrieben werden, sondern als Optimierungsproblem.
Gibt es einen oder mehrere Hamiltonsche Wege, dann finde unter ihnen den mit der geringsten Länge. |
Eine etwas allgemeinere Formulierung wäre: ... mit geringster Kantenbewertung. Prinzipiell läßt sich diese Problemstellung problemlos auf maximale Länge ändern.
Damit sind wir beim travelling salesperson problem. Meistens heißt es travelling salesman problem, heute ist aber auch die andere Formulierung schon zu finden. Warum es in der deutschen Literatur immer Handlungsreisenden und nicht Vertreter heißt, weiß ich nicht.
travelling salesperson problem |
---|
Unter allen geschlossenen einfachen Wegen, auf denen alle Ecken des Graphen liegen, ist einer mit minimaler Länge gesucht. |
Um den insbesondere in seinen Auswirkungen auf den Berechnungsaufwand nicht trivialen Unterschied zum Problem der kürzesten Wege klar zu machen, sehen wir uns zunächst wieder einmal das Beispiel dazu aus dem Buch von Turau an. Betrachten wir hier -wie dort- den Knoten 1 als Startknoten, dann wird man sicher zunächst intuitiv als zweiten Knoten den Knoten 2 wählen, da die Kantenbewertung dort am kleinsten ist. Bei kurzem Nachdenken wird aber sofort klar, dass vermutlich der Weg zum Knoten 7 mit der Länge 5 genausogut gewesen wäre, da wir ja auch wieder zum Knoten 1 zurückkehren müssen. | ![]() |
Bleiben wir aber einmal bei der ersten Entscheidung und wählen von dort aus weitergehend immer die kürzeste freie Kante im Sinne einer greedy Strategie, dann wäre als nächste Kante also die zum Knoten 7 zu wählen. Von dort aus gehen wir weiter zum Knoten 3 und gelangen über 4, 5 und 6 zurück zu Knoten 1. Ein sehr einfaches Verfahren und in diesem Fall auch sehr erfolgreich. Der Rundweg hat eine Länge von 36. Hätte es aber besser gehen können ?
Anmerkung: Zunächst einmal ist vor einer Optimierung die Existenz zu sichern. Es gibt also tsp-Probleme, die überhaupt nicht lösbar sind !