Problem eines Handlungsreisenden

[Cloudx]

Hallo alle miteinander,
hab in einem C++ Buch folgende Aufgabe gefunden aber leider keine Lösung dazu.
Hat jemand eine Idee wie man dies in einem C++ Programm realisieren könnte.
Danke


Problem eines Handlungsreisenden

Ein Handelsvertreter soll nacheinander eine bestimmte Anzahl von Städten (z.B. 6) besuchen.
Die Städte werden von 1 bis 10 durchnummeriert. Die Entfernungen der Städte sind ein einer Entfernungsmatrix fest vorgegeben.

Beispiel:
| 1 2 3 4 5 6
---------------------------------------------------------
1 | 0 4 3 6 9 10
2 | 4 0 6 4 6 8
3 | 3 6 0 4 11 7
4 | 6 4 4 0 5 6
5 | 9 6 11 5 0 5
6 | 10 8 7 6 5 0

Es müssen alle Städte besucht werden.

Gesucht ist eine Strategie mit der man mit einem Rechner die vermutlich kürzeste Rundreise findet. Die Länge der Rundreise hängt auch vom Startpunkt ab! Dies bedeutet, dass die für einen bestimmten Startpunkt gefundene, kürzeste Rundreise, nicht unbedingt die absolut kürzeste sein muss.

Durch Vergleich aller kürzesten Rundreisen kann man jedoch eine Rundreise finden, die wahrscheinlich die Kürzeste ist.

Aufgabe
Ihr C++-Programm soll die Eingabe des Startpunktes anfordern und zunächst mit einer im Quellcode verankerten Entfernungsmatrix, die kürzeste Rundreise finden und ausgeben. Natürlich soll die auch die Länge der gefundenen Rundreise angegeben werden.

 

[TakaBo]

Hi,

das Problem des Handlungsreisenden ist sehr komplex. Es gehört zu den sog. NP-Vollständigen Problemen für die es keine wirklich beste Lösung gibt. Man kann höchstens eine Lösungen finden, die der besten sehr nahe kommen....usw...usw...

Eine Möglichkeit, die realisierbar ist, kommt aus der Graphentheorie. Erzeuge einfach eine Permutation aller Teilstrecken und prüfe, ob sie einene Weg ergeben. Ein Weg ist in diesem Fall dadurch definiert, dass Du von Deinem Startpunkt alle anderen Punkte erreichst und wieder zu Deinem Startpunkt zurück kommst. Wenn Du jetzt auch noch erreichst, dass jeder Weg nur 1x vor kommt, hättest Du sogar einen Hamiltonschen Kreis.
Siehe dazu:

Wikipedia-Hamiltonkreisproblem

Das ganze kann man optimieren, indem man sich nur Permutationen der Länge n vor nimmt. Hast Du z.b. 2 Städte, so gibt es, soweit ich das noch weiss, 2 Wege (bei gerichteten Graphen!). Einer hin und einer zurück zum Start. Bei 3 Städten sind es 3 Wege. Bei Deinem Problem z.B. wären es 6 Teilwege. D.h. im Idealfall müßte der kürzeste Weg aus 6 Teilwegen bestehen. Du brauchst also keine Permutationen der Länge 7 mehr erzeugen.

Hoffe ich hab jetzt nicht nur Blödsinn geschrieben, und das ganze einigermaßen verständlich gemacht. Theorie ist doch was schönes ;-)

Gruss TB

 

[Cloudx]

Vielen Dank.
Werds mal versuchen.

 

[hpvw]

Eine kleine Korrektur an TakaBo:
Es gibt eine Optimale Lösung des TSP. Leider ist die bei realistischen Problemen nur in "unrealistischer" Zeit zu finden.

Warum werden 6 Städte von 1 bis 10 Nummeriert? (Tippfehler?)

Eine Möglichkeit (in der Praxis unbrauchbar):
Da Du eine Distanzmatrix hast, die einem vollständigen Netz entspricht, kannst Du alle möglichen Reihenfolgen der 6 Orte bilden.
Das sind 6 * 5 * 4 * 3 * 2 * 1 = 720 mögliche Wege des Handlungsreisenden.
(Man sieht, wenn mehr Städte ins Spiel kommen werden es schnell viel mehr Möglichkeiten)
Dann ermittelst Du aus der Distanzmatrix die Strecke für jeden Weg (abbrechen, wenn bereits länger als der kürzeste bisher gefundene Gesamtweg) und wähst den Weg mit der kürzesten Strecke.
Diese Methode findet sicher die optimale Lösung, fragt sich nur wann.
Vorher muss allerdings mit z.B. dem Dykstraalgorithmus sichergestellt werden, dass in der Distanzmatrix bereits die kürzesten Verbindungen stehen. (1-3-2 könnte kürzer sein, als 1-2).

Es gibt diverse Heuristiken, die zum Teil sehr nahe an die optimale Lösung herankommen, das kann aber keine Heuristik garantieren.
Ich denke, nach so einer heuristischen Strategie ist in der Aufgabe gefragt.

Ein mögliche Heuristik, um eine erste zulässige Lösung zu erhalten, ist die Nearest Neighbour Heuristik. Hier wältst Du Dir zufällig einen Startpunkt (wenn er nicht als Ort 0 gegeben ist) und wählst aus den noch nicht besuchten Städten immer den dichtesten, am Ende gehst Du zurück an Deinen Startort.

Dann kommen diverse Heuristiken zu Verbesserung ins Spiel.
Dazu erwähne ich einfach nur mal 2Opt und 3Opt.
Möglich ist sicher auch die Anwendung von Tabu Search oder genetischen Algorithmen.

Es gibt diverse Bücher zur Tourenplanung und speziell zum TSP in Büchern zur Wirtschaftsinformatik und, wer hätte es gedacht, Logistik.

Wenn Du Suchbegriffe kombinierst wirst Du unter Umständen auf einigen Uni-Seiten landen und Folien und Skripte dazu finden.

Gruß hpvw