Wegfindung: Wie funktioniert sowas (theoretisch)

[yankee]

Hi @ll,

mich würde mal interessieren, wie Wegfindungsalgorithmen funzen. Also bei riesigen Karten (zum Beispiel bei Routenplanern, wie Map&Guide, die gleich Kartenh für ganze Europ haben, mit allen Nebenstarßen usw.) ist es schließlich (fast) unmöglich einfach alles auszuprbieren. Es sei denn man hat den neuen Highend 20GB RAM-Computer mit 50 Gigahertz und 20 Jahre Zeit...
Also mal rein von der Theorie: Wie kommt man an den kürzesten/schnellsten Weg?
Bitte jetzt nicht Seitenweise Delphi-code, ich glaube, das würde ich nicht verstehen ;-).
Nur mal so, auf welchen Grundgedanken diese Algorithmen basieren...

Und wie ist das mit "Kombinationstests"? Also ich meine, zum Beispiel ein Stundenplangenerator: Wenn man sowas schriben will (besonders in der Oberstufe: Alle Wahlzettel eingeben und das Programm rechnet sich die optimale Blockung aus). Das funktioniert doch betsimmt ähnlich, oder wie sehe ich das?

[JasonDX]

Sowas funktioniert anhand von graphenalgorithmen (daijkstra- und A*-Algorithmen)
(sry, wenn ich den herrn falsch geschrieben hab ;) )

Das mit stundenplänen-generatoren ist glaub ich dynamische programmierung, bin mir aber nicht sicher!

[fwsp]

moin

oder wowas geht auch nach einem Ameisen-Algorithmus.
musst mal auf die website der c't gehen. unter dem soft-link 0505204 solltest du dazu was finden.

[BenjaminH]

Dazu gibts ein schönes Buch:
Das Geheimnis des kürzesten Weges von Peter Gritzmann und Rene Brandenberg
Da werden mehrere Algorithmen beschrieben und sehr gut erklärt
//Edit ISBN

[brechi]

Routenplaner haben schon bestimtme Routen drin z.b wenn man von Hamburg -> München will wird nur berechnet von Hamburg -> Autobahn und Autobahn -> München, der Rest ist (autobahn zu autobahn) ist schon fest eingespeichert

[mr47]

Zitat:

Zitat von brechi

Routenplaner haben schon bestimtme Routen drin z.b wenn man von Hamburg -> München will wird nur berechnet von Hamburg -> Autobahn und Autobahn -> München, der Rest ist (autobahn zu autobahn) ist schon fest eingespeichert

Das glaub ich nicht! Wenn du nähmlich einfach anderst fährst als es das Navi will, berechnet der schnell mal ne neue Route. Der sagt dann nicht ne halbe Stunde lang "Bitte umdrehen". Ausserdem kann man bei guten Navisoftwares auch einstellen von Hamburg nach München OHNE Autobahn zu benutzen. Dann klappt dein System auch net

mfg

[alcaeus]

Bei den Themen "kuerzester Weg" oder "Navigation" kommt man ums Thema "Graphenalgorithmen" nicht rum.
In der Praxis sieht es so aus (grob abstrahiert), dass jede Stadt, jeder Ort ein Knoten ist, welche teilweise mit Graphen verbunden sind (A->B fuer Einbahnstrassen, A<->B fuer "normale" Strassen). Jeder Graph hat nun zusaetzlich zur Laenge auch die Durchschnittsgeschwindigkeit und vielleicht noch mehr gespeichert, und wenn man sich die Route von ABC nach XYZ berechnen laesst, so wird entweder die Verbindung mit der kuerzesten Laenge oder die Verbindung mit der kuerzesten Fahrzeit (t=s/v) gesucht, je nach Einstellung. In der Praxis ist sowas natuerlich sehr komplex, ihr koennt ja mal ueberlegen wie viele Knoten so ein Graphenverbund fuer Europa haben muss ;)

Greetz
alcaeus

[Speedmaster]

Gabs hier im Forum schoneinmal,hier ist ein Tutorial wie sowas funktioniert!

[yankee]

oh man, vielen Dank für eure Antworten. Ich habe mir die Links noch nicht angesehen, aber das mache ich bald, heute ist mir das zu viel ;-).
Aber das scheint ja ganz vielversprechend :party:

[everdream]

Ich hätte dazu noch eine Frage, reine Neugier, programmiere also (im Moment) nichts in der Richtung.

Wenn eine Navi-Software z.B. die Daten für Deutschland hat und ich will von Hamburg nach Berlin, dann würde ja z.B. Dijkstra auch die Wege nach München oder Nürnberg beachten. Ich gehe mal davon aus, dass das in der praktischen Anwendung nicht geschieht, dass also der Graph eingegerenzt wird, bevor der kürzeste Weg gesucht wird.
Weiß jemand, nach welchem Prinzip diese Eingrenzung gemacht wird?