Traveling Salesman Problem

[MisterX]

Hallo,

ich hab ein Problem. Und zwar sitzte ich vor einer Aufgabe bei der ich 16 Städte in beliebiger Reihenfolge besuchen soll, und zwar auf dem kürzestmöglichsten Weg, und am Schluß wieder am Startknoten sein soll. Bekannt als Traveling Salesman Problem. Ich möchte für dieses Problem einen Algorithmus, im Pseudocode, spezifizieren. Ich hab schon das halbe www durchgeforstet, bin aber auf keine zufriedenstellende Lösung gekommen.
Ich hab das Gefühl ich sitze auf der Leitung. Vielleicht kann mir ja jemand weiterhelfen. Bitte bitte. Wäre echt net.

Danke.

Grüße

 

[SlaterB]

> Ich möchte für dieses Problem einen Algorithmus, im Pseudocode, spezifizieren.

so wie du die Frage stellst, klingt das Problem um Längen zu hoch für dich,
was für eine Art von Algorithmus willst du denn dafür?
einfach alle möglichen Kombinationen durchprobieren oder irgendwas höheres?
eine Übersicht der Möglichkeiten gibts hier:
http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden

wie gesagt aber ein mächtig schweres Problem,
wenn man da keinen eigenen Ansatz hat, macht es eigentlich keinen Sinn, da von jemand anderen zu kopieren,
(außer von allgemein öffentlichen Quellen im Internet )

das ist ja nun keine Fleiß-/ Grundlagenaufgabe sondern schweres Denken

 

[Guest]

Ich hätte es jetzt so gemacht:

Eine beliebige Stadt als Startknoten genommen, von dort aus geguckt welche Städte ich erreiche, und dann zu der Stadt mit der kürzesten Distanz gegangen, und das gleiche für die jetzt erreichte Stadt gemacht.
Aber wie komm ich dann wieder an meinen Startknoten zurück?
Und wie schreib ich das in Pseudocode?

Ich denke es läuft auf einfach alle möglichen Kombinationen durchprobieren raus, oder?

Den Artikel in Wikipedia hab ich schon mehrfach durchgelesen, aber verstehen ist die andere Frage!!!!

 

[byte]

Wenn die Laufzeit wurscht ist, dann kann man das doch sicher auch nach dem Backtracking Verfahren lösen. Damit dann einfach alle Wege bestimmen, die wieder beim Startort enden. Der mit der kürzesten Strecke ist dann das Ergebnis. Effizient ist das sicher nicht, aber das scheint ja nicht gefordert zu sein.

 

[SlaterB]

@Gast
das klingt doch gar nicht schlecht, vielleicht noch eine Erweiterung:
Vom Startknoten mit zwei beliebigen Knoten ein Dreieck bilden, dann nach und nach alle anderen Knoten einfügen und zwar zwischen den beiden Knoten, bei denen der entstehende Weg am kürzesten ist.

gibts natürlich schon:
http://de.wikipedia.org/wiki/Nearest-Insertion-Heuristik
(edit: ne ist doch was anderes, na irgendwo da sicherlich auch genannt,
oder nimm Nearest-Insertion, das wolltest du ja )

was ist dann am Pseudocode schwer?
Knotenmengen, ne Hauptschleife, Wege berechnen und vergleichen, kürzesten Weg merken,
das sind doch einfache Dinge,

erstmal auf Deutsch, dann pseudocodisch

 

[MisterX]

Am Pseudocode ist für mich schwer, dass ich nicht so genau weiß wie detailiert es schon am orginal Code dran sein muß. Ist dies z.B. schon Pseudocode:

Knotenmenge(alle Elemente der Rundreise)
while(Knotenmenge nicht leer ist) {
berechne(Wege zu alle benachbarten Knoten)
vergleiche(die einzelnen Distanzen)
speichere die kleinste Distanz
entferne Knoten aus Knotenmenge
}
if (Knotenmenge leer)
gib kürzeste Distanz aus

:?: :?: :?: :?: :?:

 

[SlaterB]

das kann nur der beantworten, der dir diese Frage stellt?!
alles andere ist reine Spekulation,

wenn dir Spekulationen gefallen:
für mich ist dein Code noch bisschen zu kurz,
was mit den Knoten passiert die ausgewählt wurden erwähnst du gar nicht,
warum sollte man die kleinste Distanz speichern?
vielleicht den kleinsten Weg speichern, also die Knoten in Reihenfolge?