TSP - Traveling Salesman Problem

Computer: Software & Programmierung Programmierung allgemein
#1

hallo!

Ich bin derzeit im 2. Semester eines Informatik-Studienganges und wir haben die Aufgabenstellung bekommen, einen Traveling Salesman Problem - Algorithmus zu implementieren.

Nach zahlreien Stunden mithilfe von Google, bin ich echt am verzweifeln :frowning:
Kennt jemand eine gute Adresse wo ich Codebeispiele für diesen Algorithmus finde?

In meinem Beispiel geht es derzeit „nur“ um 5 Städte/Knoten in einem Koordinatensystem. Theoretisch ist es ja wirklich leicht zu verstehen nur happerts an der Umsetzung.

Bzw. wie könnte ich folgendes am Besten umsetzen:
Ich habe die 5 Städte (Stadt 1, Stadt 2, Stadt 3, Stadt 4, Stadt 5)
Jetzt möchte ich die verschiedenen Anordnungsmöglichkeiten zurückgeliefert haben -> zB 1, 2, 4, 5, 3 oder 3,4,5,1,2, usw.
wie könnte ich das am besten realisieren bzw. gibts auch ne gute quelle dazu im internet?? würde ich die verschiedenen anordnungsmöglichkeiten haben, dann wäre auch die lösung meines problems leicht umsetzbar!

bin für jeden tipp seeehr dankbar!

lg peter

#2

Moien

Ich bin derzeit im 2. Semester eines Informatik-Studienganges
und wir haben die Aufgabenstellung bekommen, einen Traveling
Salesman Problem - Algorithmus zu implementieren.

*g* Der Prof ist ein kleiner Sadist, richtig ?

Kennt jemand eine gute Adresse wo ich Codebeispiele für diesen
Algorithmus finde?

Der TSP ist NP-vollständig. D.h. nach derzeitigem Stand der Dinge gibt es nur eine zuverlässige Lösung: alle möglichen Kombinationen durchprobieren.

Es gibt einen Haufen schnellerer Ansätze und zu jedem dieser Ansätze gibt es mindestens ein Gegenbeispiel. Google wird dich mit nicht-ganz-100% Ansätzen zumüllen.

wie könnte ich das am besten realisieren

rekursiv:

anhängen (Liste-der-schon-festgelegten-Städte, Liste-der-noch-nicht-benutzen-Städte){
 if (Liste-der-noch-nicht-benutzen-Städte == {}){
 Liste komplett, Länge ausrechnen
 } else {
 for each stadt in Liste-der-noch-nicht-benutzen-Städte{
 temp-liste1 = Kopie von Liste-der-schon-festgelegten-Städte
 temp-liste2 = Kopie von Liste-der-noch-nicht-benutzen-Städte
 temp-liste2.remove (stadt)
 temp-liste1.append (stadt)
 anhängen (temp-liste1, temp-liste2)
 }
}

rein geht man mit anhängen({}, {1,2,3,4,5})

würde ich die verschiedenen
anordnungsmöglichkeiten haben, dann wäre auch die lösung
meines problems leicht umsetzbar!

Richtig. In dem Code fehlt nur die Rückgabe der besten Kombination.

cu

#3

Naja, das TSP Problem kann ohnehin nicht effizient (liegt in NP) implementiert werden. Deshalb schäme ich dafür auch nicht *g:

Für jede Permutation in der Städtemenge könntest du überprüfen, ob es eine gültige Lösung ist. Von allen Lösungen kannst du ja dann die beste suchen.

Wenn es dir allerdings nur um eine Approximation geht, dann gibt es da Lösungen basierend auf Delaunay-Triangulationen. Einmal die Doubeling-EMST und Christofides Heuristik. Erstere Lösung liefert Lösungen, die maximal das 2-fache der optimalen Lösung liefert. Zweitere höchstens das 1.5-fache.

so long,
KoRn

#4

Super danke für eure Antworten!

Ich habe daraufhin in Google nach dem Begriff „Permutation“ gesucht und die Lösung gefunden.
hier ist der Link zur funktion, welche entsprechend abgeändert gehört:
http://www.spotlight.de/zforen/ccc/m/ccc-1133511192-…

nochmals recht herzlichen dank…lg aus wien - peter!