Routenplaner mit bestimmten Funktionen gesucht.

[Cypher]

Moin!

Ich suche einen Routenplaner, am besten online, der es ermöglicht, mir eine Route zu generieren aus mehreren Anfahrtspunkten, die er selbstständig in die richtige sinnvollste Reihenfolge gibt.
Dass heisst also ich sage ihm nur den Start und den Zielpunkt und gebe ihm 40 Punkte vor die ich anfahren will und er schaut wie ich dass am besten mache ohne dass ich die Reihenfolge vorgeben muss.

Gruß, Cypher

[josefYY]

Einen Routenplaner der das "travelling Salesman" Problem löst.
Wenn es den gibt fress ich nen Besen :wink:

[Cypher]

Warum?

Findest du dass so abartig??
So schwer ist das doch eigentlich nicht, oder?

Gruß, Cypher

[DonVitoCorleone]

hrrr hrrr hrrr

hab das grad mal bei viamichelin.de ausporbiert:

Von München nach Berlin.
Als Etappen in folgender Reihenfolge : Hamburg-Stuttgart-Hannover

http://map014.viamichelin.com/mapsgene/dm/FJVBag=z9F0Dl6b-saPU0GnkqgmBuV9=GFE7aKkoQ2otjA7MqLYmkqM8Ni4gHpLPgzKqOYyknlohHa29GOAx5jw0BFiZh73Q lvaownrrpm4xvzutmzMGlvW2f-iEhBkb8X=HNoMpNBB=mFutMZ8IbwuLfb8O9fljqfnqfT8JPiL4oeA3oawOwbQjMaL0P9o9XNSgLmk_uB 3yTYVpXJOOwtN_pQ=kYLjP7KS=s23b88=D0VWI1Wi3uK8JpN3uq3srf=ey1zaahqO0mAgwUnkfRs=SaN iqwbbd0z_bv5k0KrvZjJ53yThF23tFYDaRnc1GE1gHM0XSRC78ENhbgzDNfAQCATKGNkp9vL_FhFCvYC oJa=tsGpvMe1mryBjXO8l4xqFaY4rzzmXBm9rs7z=dDJzm_JJZSkYutBC1m9Re=kHHMLZFdaHdT9tYbX vesR1FM1B-Y5X5_vJ44EEUdv2Z=jr2JKlOo5NXT9pwzyE-J_WOI5oXmnEoZUO3Im=TSa3w04w4EQk4LnXoqCCx2uInUYAzIE-uXj5m_3q1D-1mUw=txbk_=qTN1-jkf5p_zKzE3wUq30LLiy11rb3SyP1fG8AurIl74b9n2zcN1dq-ecYeToYXeclua8cEigWJxKJPTcpDl01sRd_8cW7av=W0oKwYzTP2SH1JGfb5tmpYvn7Elm3-24EPX5j7wqQN66


Naja, ist ja nicht das wahre ^^

Aber wenn du selbst schon die Ziele in eine relativ logische Reihenfolge bringst (München-Stuttgart-Hannover-Hamburg-Berlin)

http://map014.viamichelin.com/mapsgene/dm/37VzOUmsgxHtVdWs4u-49DsZ1CK=DONxrYwyRBcgXfvha1yE_hvvVc2S65Wu3sGEIvcHOXpD3K8ve7I36jDBtgiaAsjdJRezwZO AOlsDzlwDpOk2x0QXEgG8lrFxGuYd35GHeS0oOTHQ2KYogN1DR3bieLzG0ed2C3lKJgVGa3ARCkF_t6M E1S2f84pei44edoe77vfpKTQznlGXJd_rEtlRrvzS-rUyiOvwxk4bHxAv5tOatedyZLBACNrpa0BRahANNEopQPhU3LBCEvJikre4sgSmPuhi-OfvlQAyrmifDsNj98obajklfKWwJ4sUGLg3KgMEGNd_czpI4g9KXl6AFNqNmTNruY1X4fbnh37Ow5diJ NKoQdUeGzIxTpoabEbAEjnKuMJ5eA3cPpy8Nf4djf81rJt91FUabKOpMQxfxO2iDbt-jFR9mKicTqgDlOgdR90KszZu8LR0KgjFVv4evhyPvenrND51QpVlPjugfq4iNqtPkqSkEvJFgwhFVjex cXuHlEXWSpi1su4jiPSONEIyEF5HDnwt-NYkCDmSMtpWwYvuk03AcN1swnFSiamzWxkeQa6B=

Dann ist das doch relativ annehmbar, oder?
Oder hast du so viele und vorallem kleine Etappen dass du alles nachschauen müsstest? Dann ist das natürlich a weng umständlich...


€dit: Aber mann kann schön malen :

http://map014.viamichelin.com/mapsgene/dm/FJRBag=91JOjrWt2eyg5GEf9vGuaC-swwxIc4oGwvXKpDfcrLp2HmjacTLy103DukG4YkuBj8qg-w60n9nDpajSl6jmq-0FKYVLlf0YuLV-7a-Cz-4HTzXGa7ecU25yrj=5ieXV4IdsU-YBDLks1MVScWtSgXwyV1GFOu=DGT2tFjPnOM8JD0tLm7GKZXy_KwGF62jJqyZFTNwL6HfN=noM9CkjQT aSHoXViJfOOP510SQ5AmfCCjnIu2a910NNsB5cEx-T3=S_0CRh1tUG0DaqSm1ZjW5iNOenVSZm-4-WHRDjaEECPXzM3EgklFEM7dRE69CTzQdSR96l__N-p5hhJNxtmpGizYcGRzY_s5imtJqedx6csv-TU8lpq3geG8dM76dyE3UY0RhyMIE6zfVOSQw5Wum_pq_8s-SOJT_pmIv22jc6QN7K6S1xrdMXo1lhoGWRavDv4X7wCAYKQN0GYXB1ZUgRjkCPqLG1N7vTH3ESt6z3hL 0Yy2MjuUQIELkRAgVg1XUweDzjjuqsr3vWBHKJWCzR9GBNnpJVWWEj02Ma8sfHMRd3LIqI7OxMkxpDjd WWp5zDToEgi=R1g3GaS5BN1jeWaAOWCgpz0PqOWh3VZacw3r1NE

[josefYY]

Warum?

Findest du dass so abartig??
So schwer ist das doch eigentlich nicht, oder?

Gruß, Cypher

Eine 'relativ' gute Lösung lässt sich sicherlich schnell errechnen.
Einen mathematisch optimale ist jedoch was ganz anderes.
Wobei, bei 40 Zielen mag das vielleicht sogar noch funktionieren.

Aber derlei Aufgaben lassen sich für größere Mengen an Zielen nicht optimal lösen, da mit zunehmender Anzahl an der Rechenaufwand exponentiell steigt.
Für derlei Probleme gibt es in der Mathematik bzw. Informatik einen separaten Forschungszweig.

[DonVitoCorleone]

Es wäre natürlich schon sehr praktisch sowas.
Bin grad auf der Suche nach nem Gebrauchtem Winterauto.
Einfach alle rausgesuchten Adressen eintragen und den optimalen Weg berchnen lassen.... :rolleyes:

[aCiD]

Es wäre natürlich schon sehr praktisch sowas.
Bin grad auf der Suche nach nem Gebrauchtem Winterauto.
Einfach alle rausgesuchten Adressen eintragen und den optimalen Weg berchnen lassen.... :rolleyes:


Hmm naja ich weiß ja nicht wonach du suchst, aber normalerweise wenn man nicht genau einen bestimmen Typ sucht, findet sich immer was gutes im Umkreis, und wenn man ne Woche wartet. Ich hab z.B. mein Auto in 10 km Entfernung gefunden und ein gutes Angebot war es auch noch. Auch wenn ich vorher noch n anderes probegefahren bin und am selben Tag, wie ich meinen probe gefahren bin, abends noch nen weiteren Termin gehabt hätte...

Also, was suchst du denn und in was für ner Preisklasse?

Greetz
aCiD

[Melbourne, FL]

So schwer ist das doch eigentlich nicht, oder?

Doch...und zwar mordsmäßig...

Alexander

[Cypher]

Naja ich werd mir mal viamichelin anschaun...

Problem ist ich habe circa 40 Adressen in und um Hannover und überlege nun wie ich die beste Möglichkeit finde sie abzufahren.
Aber vermutlich werd ich mir dann doch nur nen großen Stadtplan nehmen und Kreuze draufmalen oder so...

Gruß, Cypher

[Spasstiger]

Naja ich werd mir mal viamichelin anschaun...

Problem ist ich habe circa 40 Adressen in und um Hannover und überlege nun wie ich die beste Möglichkeit finde sie abzufahren.
Aber vermutlich werd ich mir dann doch nur nen großen Stadtplan nehmen und Kreuze draufmalen oder so...

Gruß, Cypher

Mann, das ist ja wie in GTA. :D


Aber derlei Aufgaben lassen sich für größere Mengen an Zielen nicht optimal lösen, da mit zunehmender Anzahl an der Rechenaufwand exponentiell steigt.
Für derlei Probleme gibt es in der Mathematik bzw. Informatik einen separaten Forschungszweig.

Du spielst wohl auf die Graphentheorie an.
In Strategiespielen muss die KI auch solche Kürzeste-Wege-Probleme beherrschen.

[josefYY]

Mann, das ist ja wie in GTA. :D



Du spielst wohl auf die Graphentheorie an.
In Strategiespielen muss die KI auch solche Kürzeste-Wege-Probleme beherrschen.

Jepp, werter Herr Vorstandsvorsitzender :wink:

Stimmt in Strategiespielen gibt es das Problem auch, wobei dort ist die Anzahl der Stationen in der Regel sehr gering ist. Ausserdem reicht es in Spielen wenn bereits eine gute Näherung gefunden wird. Das absolute Optimum ist gar nicht nötig. Aber genau darin leigt das Problem. Lösungen die dem Optimum sehr nahe kommen lassen, sich oft mit einem vertretbaren Rechenaufwand errechnen. Das absolute Optimum jedoch ist ungleich schwieriger.
Man sieht ja auch wie gut manche Strategiespiele dies Problem gelöst haben :D

@Cypher
Ich Zitier hier mal jemanden von einer Uni-Homepage der die Problematik noch mal anschaulich verdeutlicht:

"Die "brute-force"-Methode, d.h. Berechnung und Vergleich der Gesamtweglänge für alle denkbaren Wege, ist nur für sehr kleines N sinnvoll, da es bei N Städten insgesamt (N-1) ! = 1 * 2 * ... * (N-1) mögliche Rundwege gibt.
Für N = 20 sind z. B. bereits 19 ! = 1,2 * 1017 Routen auszurechnen, was bei einer Millisekunde pro Weg ca. vier Millionen Jahre dauern würde.
Das "Problem des Handlungsreisenden" ist das klassische Beispiel für ein sog. NP-vollständiges Problem, was bedeutet, daß die Rechenzeit im worst case schneller als polynomial (hier sogar stärker als exponentiell) mit N wächst.
Ein allgemeiner Algorithmus zur seiner Lösung ist nicht bekannt. "

[DonVitoCorleone]

Hmm naja ich weiß ja nicht wonach du suchst, aber normalerweise wenn man nicht genau einen bestimmen Typ sucht, findet sich immer was gutes im Umkreis, und wenn man ne Woche wartet. Ich hab z.B. mein Auto in 10 km Entfernung gefunden und ein gutes Angebot war es auch noch. Auch wenn ich vorher noch n anderes probegefahren bin und am selben Tag, wie ich meinen probe gefahren bin, abends noch nen weiteren Termin gehabt hätte...

Also, was suchst du denn und in was für ner Preisklasse?

Greetz
aCiD


Öhmmm...
danke für die Tipps, aber das hat eigentlich nix mit meinem Posting zu tun... ;D

[Stone2001]

Du spielst wohl auf die Graphentheorie an.
In Strategiespielen muss die KI auch solche Kürzeste-Wege-Probleme beherrschen.
: TSP ist NP-Vollständig! Shortest Path nicht! Deswegen hat man mit der Routenplanung auch weniger Probleme.


Ich persönlich würde die 40 Punkte in eine grobe Reihenfolge bringen und dann nur noch die Webbeschreibungen ausdrucken.

[Cypher]

Das ist ja ne interessante Materie...
Dann werd ich die Suche wohl aufgeben...

Vielen Dank für die Antworten!

Gruß, Cypher