Handlungsreisender

[Gast]

Hallo,
ich suche ein einfachen Beispielcode für das Problem des Handlungsreisenden.
Der Handlungsreisende soll mehrere Städte besuchen, und die kürzeste Strecke soll berechnet werden (Hin-Rückweg).

 

[Jockel]

Schonmal selbst gesucht? Wenn man bei Google 'TSP Java' eingibt, werden einem 96.000 Treffer angezeigt, unter anderem auch mit Source, wie z.B.: http://www.patol.com/java/TSP/

 

[Gast]

Ja ich habe schon selbst gesucht, ich suche allerdings einen einfachen java code für ein application den ich nachvollziehen kann, denn ich habe gerade esrt mit java angefangen.

 

[Bert Brenner]

Dann lass dein Programm doch einfach alle möglichkeiten durchgehen.

 

[boskop]

Alle möglichkeiten durchgehen scheint mir doch eher eine schlechte variante:

bei n Städten gibt es n!/2n verschiedene Touren

für n = 20 sind das dann schon 6.1 * 10^16 verschiedene Touren.

Wenn du es voll krass machen willst, kannst du es mit einem neuronalen Netz à la Hopfield oder so. Es gibt dazu auch Java Frameworks.

link

mfg

boskop

 

[Wildcard]

Alle möglichkeiten durchgehen scheint mir doch eher eine schlechte variante:

bei n Städten gibt es n!/2n verschiedene Touren

für n = 20 sind das dann schon 6.1 * 10^16 verschiedene Touren.

Deshalb spricht man auch vom Problem des Handlungsreisenden :wink:

 

[mic_checker]

Vielleicht solltest du dir als Approximationsverfahren auch z.B. mal die Cristofides-Heuristik anschauen, da du ohne Approximationsverfahren schnell an best. Grenzen stoßen wirst, schließlich willst du nicht zig Jahre an deinem PC sitzen um die beste Route zu berechnen

 

[Bert Brenner]

War mir bewusst das meine Lösung nicht ideal ist, aber Gast hatte doch geschrieben das er sich nicht so mit Java auskennt. Dann währe doch das erst mal eine möglichkeit um sich nen bischen damit vertraut zu machen, den Suchalgoritmus auszutauschen sollte dann ja relativ schnell gehen.

 

[mic_checker]

Wie gesagt, in dem Fall stößt man schnell an die zumutbare Grenze was Laufzeit betrifft. Da bist du schnell soweit das du ein paar Jahre auf dein Ergebnis warten müsstest - darum gibt es ja auch die bereits erwähten Approximationsverfahren, die dann teilweise max. das 1,5 bis 2 fache der besten Lösung liefern....

 

[bygones]

das hat man nun mal bei NP vollständigen Problemen... entweder man probiert alles aus und wartet womöglich, oder man nutzt eine Approximierung oder man findet den (!) Algorithmus :wink:

ich würde dir raten wenn du nicht alles probieren willst - eine Heuristik zu nehmen ! Es gibt hier einige - einen guten überblick gibt http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden

 

[Bleiglanz]

zum lernen würde ich simulated annealing vorschlagen, weils am bekanntesten ist und auch bei anderen Problemen eingesetzt werden kann