3. The Travel(ling) Salesman Problem

The Travel(ling) Salesman Problem

  • D

    Mein lehrer hat mir die aufgabe gestellt das oben genannte problem zu lösen. für die meisten sollte dies ein begriff sein, wenn nicht eine kruze erklärung. es geht darum das irgendein verkäufer von waren, zu bestimmten orten einmal muss und dann wieder zurück zum ausganspunkt. dabei soll der weg herrausgesucht werden der am kürzesten ist. es sind entweder die koordinaten der orte gegeben oder die entfernungen von jedem ort zum anderen.

    ich könnte zwar alle möglichkeiten durchlaufen und vergleichen lassen aber das wir nach einer bestimmten anzahl zu rechen- und zeitintensiv. jetzt habe ich gelesen es gibt da so ein paar algorithmen die das schneller und effizienter lösen können aber ich habe noch kein codebeispiel gefunden immer nur erklärung wie es theoretisch funktioniert. ich schaff es nicht dies in code umzusetzen.

    bei wiki gibts eigentlich ne ganz gute erklärung
    wiki

    1. kann mir einer nen codebeispiel geben wie dieses problem gelößt werden kann. ne funktion wo ich nen array angebe und das mir dann die kleinste strecke sucht
    2. was ist günstiger ne karte mit koordinaten oder nen array mit den abständen von einem ort zu den anderen?

    ich hoffe ihr könnt mir helfen ich hab nämlich keine ahnung wie ich anfangen und lösen soll. ich programmiere normalerweise mit dem borland c++ builder wenn das wichtig ist.

    0
  • ?

    Ist dein Lehrer unfähig oder hast du den Unterricht verpennt. Wenn dein
    Lehrer solche Aufgaben stellt sollte eigentlich alles notwendige zur
    Lösung behandelt worden sein.
    Fertige Lösungen gibts hier nicht, du musst hier schon mit eigenen Ansätzen
    aktiv werden. Ich bin mir aber sehr sicher das es zu diesen klassischen Problem
    fertige Lösungen und auch detaillierte Beschreibungen bereits im Internet gibt.

    0
  • ?

    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!

    0
  • ?

    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).

    0
  • D

    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.

    0
  • ?

    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?

    0
  • C

    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?

    0
  • C

    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.

    0
  • T

    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/

    0
  • W

    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

    0
  • J

    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.

    0
  • M

    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.

    0
  • D

    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

    0
  • B

    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 🙂

    0
Anmelden zum Antworten