Travelling Salesman Problem in Java

[witch doctor]

Wir haben in Softwaretechnik eine Aufgabe bekommen das Travelling Salesman Problem zu programmieren.

Das Programm lag als C Programm vor und wir sollten es nach Java portieren.

Nur da gibt es einige Probleme meinerseits

1. Ich kann kein C und verstehe den Code nicht.

Habe mir aber gedacht, dass es halb so schlimm ist.

Wenn du den Algorithmus verstanden hast wird das schon gehen.

2. Ich verstehe den Algorithmus nur in der Theorie, aber weiß nicht wie ich ihn umsetzen kann.

3. Ich muss das Programm abgeben und habe noch keine Zeile Code geschrieben.

Das Problem läßt sich folgendermaßen beschreiben.

Wir haben mehrere Städte und ein Handelsvertreter möchte eine Rundreise machen. Diese sollte Kostengünstig verlaufen. Jedes Stadt (bis auf die Start-Stadt) darf nur einmal vorkommen.

Eine Lösung wäre sicherlich durch die ganzen durchzupermutieren. Nur wie realisiere ich das in Java??? Ich habe ehrlich keinen Plan.

Die Städte habe ich in einem Array abgelegt und die Entfernungen in einem 2-dimensionalen Array.

Theoretisch würde man ja so vorgehen. Man nimmt zuerst die erste Stadt und permutiert dort durch, also so:

a b c

a c b

b a c

b c a

c a b

c b a

Damit es aber eine Rundreise wird muss natürlich die Start-Stadt gleichzeitig auch die End-Stadt sein. Nur wie bekomme ich diese Permutation hin und wie speicher ich dann die Entfernungen ab und vergleiche sie??

Den C-Code könnt ihr übrigens hier herunterladen.

[M.A.Knapp]

bei 3 städten (2^3 = 8) kann man ja noch alles durchpermutieren, aber bei 1000 (2^1000 = 10^301) geht das schon nicht mehr in einer sinnvollen Zeit.

Du kannst die Lösung mit Branch & Bound, mit einem Genetischen Algo oder mit Simulated Annealing annähern.

MfG, Michael

[witch doctor]

Ich habe lediglich 10 Städte. Trotzdem danke für die Alternativen.

Wenn jemand mir einfach die Permuation und die Berechnung etc erklären könnte reicht mir das.

[nic_power]

Hallo,

das Travelling Salesman-Problem ist eines der beliebtesten Probleme in der Informatik (damit werden gerne Studenten in den untschiedlichsten Programmiersprachen gequält). Folglich gibt es auch eine Unmenge an Web-Seiten, die sich damit beschäftigen und Code bzw. den Algorithmus bereit halten:

Als Methaseite kannst Du mal hier nachschauen:

http://www.math.princeton.edu/tsp/

Mögliche Lösungen und Algorithmen gibt es mittlerweile sehr viele:

http://ai-depot.com/Articles/51/TSP.html

http://www.math.uu.nl/people/beukers/anneal/anneal.html

http://www.informatik.uni-trier.de/~naeher/Professur/PROJECTS/TSP/hilfe/

Nic

[Gast roaxius]

Also, auch wenn das natürlich nicht schick ist, einfach den Code zu nehmen: (Nur halt, falls du wirklich gaaanz knapp dran bist...)

Einfach mal bei Google java "travelling salesman" eingeben und es kommt z.B. folgende Seite mit Quellcode:

http://www.patol.com/java/TSP/

Ob du das dann trotzdem noch so durchsiehst, dass du es auch verstehst, bleibt dann ja dir überlassen