PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Traveling Salesman Problem

stm
02.07.2002, 23:48
Hallo. Ich habe so meine Probleme mit dem Coden. Ich soll aber ein Programm für ein naives TSP schreiben, dass einfach alle Städteverbindungen ausprobiert und schließlich die kürzeste Strecke ausgibt.

Hat soetwas schon mal jemand programmiert? Gibt es den Code dazu irgendwo? Konnte leider nichts finden!!!

xOOn
03.07.2002, 09:00
nicht alle staedte sind untereinander verbunden und alle haben eine andere distanz zueinander start=endpunkt, meist du das teil, das habe ich mal in der schule gecodet, den quellcode habe ich nicht mehr aber ich kann mal die unterlagen suchen, wenn dir das weiterhilft?
smpx7
03.07.2002, 09:55
Mich würde der Lösungsweg auch interessieren. Würde evtl jede Stadt mit Ihren Längen-/Breitengraden in eine DB hauen und somit irgendwie berechnen.. hm, nur wie. :mauer:
xOOn
03.07.2002, 10:32
man speicher alle die staede in einem n mal n feld ab, wobei ich die zahl -1 als keine verbindung vorhanden genommen habe, ansonsten wird immer die distanz eingetragen die obere bzw unterge diagol haelfte wird gespiegelt aber wen interessierts. die verbindung von A nach B ist ja immer die selbe wie von B nach A
sami
03.07.2002, 11:21
das ganze ist mit ner rekursion zu lösen.
du beginnst bei nem beliebigen punkt und nimmst da den ersten weg. von da her machst wieder das selbe (also aufruf der funktion aus der funktion heraus - das ist die rekursion). das ganze machst, bis kein weg mehr vorhanden ist (abbruchkriterium), dann gehst ne stufe zurück und nimmst vom 2. letzten punkt den 2. weg.
usw... (deshalb ist das problem ja so gross/interessant, weil es keine anständig schnelle lösung gibt)

dass einzelne städte nicht miteinander verbunden sind, ist mir zwar neu, tut aber ned wirklich was zur sache.
xOOn
03.07.2002, 11:52
probier das mal fuer 50 staedte durchrechnen zu lassen, da schmiltzt dir der prozessor :p :p
Codeq
03.07.2002, 12:03
huhu

schau hier mal rein
http://www.inf.fh-flensburg.de/lang/algorithmen/np/tsp/roundtrip.htm

und sollten fragen offen sein zu den mathematischen ausdrücken schau am besten mal ins forum algorithmen da gibts ne kleinen grundlagen thread.. :)
xOOn
03.07.2002, 16:19
also ich habe es damals mit dem einfacheren algo durchgetestet

starte bei stadt 1 zu stadt 2 zu ... stadt n
und ende bei
starte bei stadt n zu stadt n - 1 zu ... stadt 1

zum verschnellern habe ich immer ueberprueft ob er aktuelle weg nicht bereits beschissener ist als der beste, dann habe ich die rechnung unterbrochen...
das ganze mit ner rekursion, und dann einfach die bereits vorhanden staedte ausgelassen