|
Anzeige
|
travelling salesman problem
Gast
#1620860
hallo an alle! Wir müssen uns für die Schule mit dem travelling salesman problem außeinander setzten bzw. mit einem Lösungsalgorithmus von Held & Karp und diesen in C++ realisiern. Da meine Frage kennt jemand eine Seite oder etwas wo man sich darüber informieren kann, denn allzu viel hab ich im Internet noch nicht gefunden was ich brauchbar verwerten konnte verstand meistens nur bahnhof. Mit freundlichen Grüßen und Dank im voraus Hans hans schrieb: > oder etwas wo man sich darüber informieren kann, denn allzu viel hab ich > im Internet noch nicht gefunden was ich brauchbar verwerten konnte > verstand meistens nur bahnhof. Aha... und wir sollen dir das jetzt was hunderte Leute schon beschrieben haben nochmal beschreiben ohne zu wissen was du nicht verstanden hast? http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden Da kann man aber nun wirklich selber draufkommen... Hmm. Für den spezifischen Lösungsansatz von Held und Karp findet sich tatsächlich nur sehr wenig im Web (zumindest mit den naheliegenden Suchbegriffen). Bisher hab ich nur eine Referenz gefunden, die sich zumindest soweit herablässt zu verraten, dass man dabei eine ganze Menge 'Minimum Spanning Trees' aufbauen muss. Aber Details: Fehlanzeige
Gast
#1620952
die seite von wiki hab ich natürlich gesehen sowie jede menge andere von neuronalen netzen (hopfield) usw aber da wir eigl bisher nur die oberfläche und grundbegriffe von c++ angekratzt haben find ich es sowieso ein starkes stück das wir das machen müssen.. was ich bisjetzt habe ist das einlesen von städten bzw deren koordinaten das umwandeln in dezimal zahl das durch spielen aller möglichkeiten und die distanzberechnung mittels wgs84 ellipsoid. start und endpunkt sind eben gleich jeder ort einmal und funktioniert soweit gut nur halt bis ca 14 orte.. danach dauerts schon ganz schön lang deswegn müssen wir jetzt das schneller machen.. vom lehrer vorgeschlagen eben held und karp (weiß sonst jemand literatur was man eventuell in einer bibliothek finden könnte?) und was ich nicht verstehe ist eigl alles ich weiß nicht wie ich das problem anpacken soll verstehe auch diese ansätze mit den neuronalen netzten nicht oder die schnittebenen usw deswegn wäre ich über jeden kleine hinweis glücklich
Gast
#1621297
Also ich weis ja nicht wie, womit oder wonach Ihr sucht. Google liefert mehrere tausend Treffer. Unter anderem auch: http://www.cse.wustl.edu/~chen/7102/Karp-TSP.pdf Man kanns auch mal via http://scholar.google.de probieren. Und wenn man in der Wikipedia mal den Links folgt, landet man z.B. hier: http://www.tsp.gatech.edu/concorde/index.html Da kann man sich den Sourcecode runterladen und mal ins "HELDKARP" Verzeichnis schauen.
Gast
#1621303
... oder auch mal hier reinschauen: http://www.cs.utoronto.ca/~neto/research/lk Da drin ist Held&Karp wohl auch implementiert.
Gast
#1621914
danke der erste nützt mir jetzt mal schon einiges dort kann ich zumindest mal reinlesen.. gestern abend hab ich es noch fertig gebracht mir den minimum spanning tree zu konstruieren jetzt mal dort reinlesen und hoffentlich herausfinden wies weiter geht
Gast
#1622029
Groß und Kleinscheibung beachten und Satzzeichen benutzen erhöht die Lust der Forenteilnehmen deinen hingekotzen Text auch zu lesen... Die Forenregeln schrieben: > Wichtige Regeln - erst lesen, dann posten! > > Groß- und Kleinschreibung verwenden Antwort schreibenBitte melde dich an, um einen Beitrag zu schreiben. |
Anzeige
|
