Traveling Salesman Problem < Sonstiges < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 17:28 Do 19.06.2008 | | Autor: | barsch |
| Aufgabe | Wende den TSP (Traveling Salesman Problem) - Algorithmus auf die Entfernungsmatrix
[mm] \pmat{ - & 2 & 8 & 7 & 9\\ 2 &-&6&2&4 \\8&6&-&8&5\\ 7&2&8&-&3\\ 9&4&5&3&- }
[/mm]
an. Beginne mit Knoten 1 und die maximale Weglänge sei 45. |
Hi,
ich habe schon im Internet nachgeschlagen, wie der Algorithmus funktioniert, jedoch keine anschauliche Erklärung gefunden (Wikipedia habe ich auch schon konsultiert). Kennt ihr eine Seite, oder seid ihr evtl. sogar bereit, mir die Vorgehensweise zu erklären? Ich wünschte, ich könnte einen eigenen Ansatz präsentieren ![[kopfschuettel]](/images/smileys/kopfschuettel.gif "[kopfschuettel]")
Danke.
MfG barsch
Ich habe diese Frage in keinem anderen Forum gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:47 Fr 20.06.2008 | | Autor: | Gilga |
http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo40.php
|
|
|
| |
|
Das Problem des Handelsreisenden kannst du auf das Hamilton-Kreis-Problem reduzieren (und damit auch zeigen, dass TSP NP-vollständig ist). Vielleicht hilft es dir, wenn du dir einmal Algorithmen zum Hamilton-Kreis-Problem anschaust.
Beispiel eines TSP mit 4 Knoten, minimale Kosten liegen hier bei 7.
Du hast die Entfernungsmatrix der Knoten (u,v,x,w) wie folgt:
[mm] \pmat{ - & 4 & 3 & 1 \\ 4 & - & 1 & 2 \\ 3 & 1 & - & 5 \\ 1 & 2 & 5 & - \\}
[/mm]
Die Tour mit den minimalen Kosten geht dann entlang u,w,v,x nach u.
Übrigens: Im Falle, dass man keine guten Algorithmen vorliegen hat, ist ein Versuch mittels Brute Force auch manchmal hilfreich (wenn auch relativ teuer, was die Kosten angeht) 
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 06:35 Mo 23.06.2008 | | Autor: | bazzzty |
> Wende den TSP (Traveling Salesman Problem) - Algorithmus
> auf die Entfernungsmatrix
>
> [mm]\pmat{ - & 2 & 8 & 7 & 9\\ 2 &-&6&2&4 \\8&6&-&8&5\\ 7&2&8&-&3\\ 9&4&5&3&- }[/mm]
>
> an. Beginne mit Knoten 1 und die maximale Weglänge sei 45.
> Hi,
>
> ich habe schon im Internet nachgeschlagen, wie der
> Algorithmus funktioniert, jedoch keine anschauliche
> Erklärung gefunden (Wikipedia habe ich auch schon
> konsultiert).
Das Problem ist: TSP ist ein (schweres) Problem, und es gibt nicht etwa einen kanonischen Algorithmus, sondern eine ganze Schar. Gilga hat ja schon auf einen Artikel verlinkt, aber was genau im Rahmen eurer Vorlesung als "TSP-Algorithmus" bezeichnet wurde, das kann sich nur aus der Vorlesung heraus erklären. Einigermaßen sicher ist ein exaktes Verfahren gemeint, wahrscheinlich was clevereres als Brute-Force, Also entweder dynamische Optimierung oder Eröffnungsverfahren.
Die 45 könnte ein Hinweis auf DP sein (das ist aber Kaffeesatzleserei), weil 45 ja nicht die Länge der kürzesten Tour ist, sondern eine triviale obere Schranke.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 07:37 Mo 23.06.2008 | | Autor: | bazzzty |
Vielleicht noch etwas mehr Kaffeesatzleserei: Wenn das ne Wiwi-Vorlesung ist, könnte auch der Patching-Algorithmus gemeint sein. Die Instanz ist ziemlich darauf zugeschnitten (obwohl man den PA eigentlich eher asymmetrischen TSPs verwendet.
Wine gute Quelle im Netz habe ich grade nicht parat, aber vielleicht guckst Du mal in Deinen Aufschrieb. Wenn Du Dir nicht sicher bist, gib uns mal ein Beispiel aus der Vorlesung oder aus dem Skript, die Algorithmen zu erkennen ist leichter als sie zu erraten.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:35 Di 24.06.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
