The Travel(ling) Salesman Problem

naja, ein paar tips kann man schon noch geben.
sonst sucht er sich eine fertige lösung woanders, und so ist es auch nicht gedacht!

Eine exakte Lösung wirst du wohl nicht schneller bekommen als mit der Methode "alle Wege suchen und vergleichen" - TSP ist NP-vollständig.
Für Näherungslösungen kannst du ja mal den Links in deinem Wikipedia-Artikel folgen (oder google nach TSP).

Der Richter

joa also
mein lehrer hat mir nichts gegeben halt mach mal ist meine aufgabe. er hat uns noch nicht mal erklärt was nen pointer ist weils nicht im lehrplan steht. ich weiß nur so viel dass das zeug dann nicht im stack liegt sondern im RAM.

ich find es eigentlich sinnlos alle möglichkeiten durchzugehen und zu vergleichen, weil es ja n! lösungen gibt und bei zu vielen städten dauert es ewig.

die aufgabenstellung von meinem lehrer war ich soll nen algorithmus suchen der das problem löst z.B. Dijkstra.
jetzt war ich bei ihm nach ner woche hat jetzt gemeint ich soll es nicht zu kompliziert machen und einfach alles vergleichen. ja toll erst kompliziert dann einfach ne woche umsonst rechrchiert.

ich hab jetzt nen lösungsanstz er ist vielleicht nicht perfekt aber vielleicht ganz gut und sehr einfach.
ich such von meinem ausganspunkt den nächst nähersten punkt und von dort aus wieder den nächsten usw. so kommt ein annährend identischer wert heraus aber manchmal oder meistens nicht das minimum

tut mir leid wegen der blöden frage aber hatte hat keinen plan mit dem Dijkstra weil das alles ziemlich kompliziert war weil wir das noch nie behandelt haben kein #define "" oder sonstiges vertex, pointer.

sorry das es so lange gedauert hat zu antworten war unter stress.

CStoll (off) schrieb:

Eine exakte Lösung wirst du wohl nicht schneller bekommen als mit der Methode "alle Wege suchen und vergleichen" - TSP ist NP-vollständig.
Für Näherungslösungen kannst du ja mal den Links in deinem Wikipedia-Artikel folgen (oder google nach TSP).

nanana, gilt das denn auch für wege in einer ebene?

CStoll

Wikipedia schrieb:

Das Problem des Handlungsreisenden ist NP-vollständig. Die Optimierungs- und Suchvariante sind NP-äquivalent. Daran ändert sich nichts, wenn man sich auf das metrische PdH oder sogar noch spezieller auf das euklidische oder rektilineare PdH beschränkt.

-> Ja, das gilt auch auf der Ebene.

@Richter: Wenn du noch nichtmal die elementarsten C(++)-Grundlagen erklärt bekommen hast, dürfte die Umsetzung etwas schwierig werden.
Aber dein Ansatz ist schonmal eine recht gute Näherungslösung (ich müßte doch glatt mal in meinen Unterlagen nachsehen, wie nahe du damit ans Optimum rankommen kannst).

PS: Wo lernst du denn eigentlich?

C++ Forumbot

Dieser Thread wurde von Moderator/in HumeSikkins aus dem Forum C++ in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

TheToast

Immer den nächsten Punkt suchen ist die "Nearest Neighbour" Methode, die ist nicht sonderlich gut, liefert vielleicht in einfachen Fällen eine gute Route, aber in den etwas komplizierteren eher selten. Recht einfach sind noch die Nearest Insertion und die Farthest Insertion, danach mal einfach suchen, die liefern oft was besseres als der NEarest Neighbour und sind trotzdem noch recht einfach. Aber das heißt nicht, dass die _immer_ besser sind, als NN, manchmal sind die sogar schlechter, je nach Route.

Interessant vielleicht noch (etwas komplizierter): http://www.ameisenalgorithmus.de/

Winn

Der Richter schrieb:

... die aufgabenstellung von meinem lehrer war ich soll nen algorithmus suchen der das problem löst z.B. Dijkstra...

Dijkstra wird (so weit ich mich noch an DV zurückerinnern kann) beim TCP/IP Routing eingesetzt... ein weiterer wäre der Floyd-Algorithmus... und ein guter Herr Euler war der Erste (meine ich), der sich mit Strecken-Netz-Findung auseinander gesetzt hat...

See you

Jester

Zu Anfang solltest Du Dich erstmal entscheiden, ob Du nun das Problem exakt lösen willst (das ist NP vollständig und viel mehr als durchprobieren evtl. mit Backtracking wird sich nicht machen lassen) oder ob Dir auch ein Weg reicht, der gut ist, aber nicht unbedingt optimal. Es ist zum Beispiel recht einfach einen Weg zu konstruieren, von dem man zeigen kann, daß er höchstens 1,5 mal so lang wie der kürzeste ist.

Maxi

bei ai-junkie.com (oder so ähnlich) wird das problem mittels genetischer algorithmen gelöst. Ich weiß aber nich, wie weit die kommen, wenn die strecken komplizierter sind. Da hat er nur einen Kreis verwendet um die städetpositionen darzustellen. Ausserdem dauert son algo auch ziemlich lange, um das ergebnis zu finden.

daniel12345

stichworte: savings-algorithmus, sweep-algorithmus, n-opt-verfahren. damit bekommt man ganz gute lösungen, und die algorithmen sind recht gut zu implementieren. tip: für matlab gibts ein modul (matlog), da sind die implementiert, als ansatz

Blue-Tiger

Erhm.... ich will ja nicht rummeckern, aber findet ihr's nicht uebertrieben einem Schueler (dessen Info-Lehrer anscheinend recht inkompetent ist) mit Begriffen aus der Graphentheorie, NP-Vollstaendigkeit, Mathlab-Modulen, Fehlerabschaetzungen fuer Approximationsalgorithmen etc. daher zu kommen? o_0
Niemand hat ihm erklaert was ein Pointer ist und ihr kommt mit Stoff daher, der normalerweise an der Uni abgehandelt wird

Anyway, wenn ich meinen Senf mal dazu geben darf:
Probier einfach alle Moeglichkeiten auf. Wie CStoll schon gesagt hat ist das TSP ein "NP-vollstaendiges" Problem, was auf gut Deutsch heisst dass es keinen guten Algorithmus gibt, der immer funktioniert. Fuer die 100%ig optimale Loesung wirst du nicht um das durchprobieren aller Faelle rumkommen. Ausserdem ist das relativ einfach zu machen
Dass es so lange dauert sollte dich vorerst mal nicht kuemmern, wenn du nicht grad mit 100 verschiedenen Staedten rechnest sollte das deine CPU in akzeptabler Zeit ausrechnen koennen