List Google stadt Algorithmus Beispiel Umsetzung

TSP - Traveling Salesman Problem

Von: , Frage gestellt am So, 27. Mai 2007

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 :-(
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

3 Antworten zu dieser Frage

1. Antwort von nach 47 Minuten 0 hilfreich

   Re: TSP - Traveling Salesman Problem

   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
   

   • Antwort von nach 17 Stunden 0 hilfreich

     Re^2: TSP - Traveling Salesman Problem

     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!
     

2. Antwort von nach 49 Minuten 0 hilfreich

   Re: TSP - Traveling Salesman Problem

   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
   

Keine passende Antwort gefunden? Jetzt eigene Frage stellen!