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?

[yankee]

Zitat:

Zitat von everdream

Weiß jemand, nach welchem Prinzip diese Eingrenzung gemacht wird?

Ja, das ist auch in dem Buch erklärt, dass ich mittlerweile natürlich längst gelesen habe (sehr emphelenswert nebenbei ^^).
Also es gibt da sicherlich noch andere Möglichkeiten, aber zumindest eine, die gerne angewandt wird:

Wenn du zwei Punkt hast und du kennst bereits eine mögliche Entfernung zwischen den beiden Punkten, dann kannst du die beiden Punkte als Mittelpunkte für eine Ellipse verwenden. Die Summe der Entfernung der Ellipsenaussenseite (wie heisst das richtig? ^^) zu den beiden Mittelpunkten ist dabei immer deine bekannte Entfernung. (Klingt kompliziert, das ist aber nur so, weil das mit etwas Grafik wesentlich einfacher zu erklären wäre *grr*).
Dann weisst du, dass jedes mal, wenn du die Ellipse verlässt die Wegsuche abbrechen kannst, weil der dir bekannte Weg in jedem Fall kürzer ist.

Fragt sich nur, was du als "bekannte Entfernung" verwendest. Vielleicht einfach Luftlinie*2 und wenn er dann nichts findet, dann langsam vergrößern? Oder man nimmt wirklich erstmal ein vereinfachtes Netz (ein vorberechnetes mit wesentlich weniger Knoten) anhand dessen man die Entfernung abschätzen kann.

[everdream]

Also veranshaulicht eine Ellipse, implementiert wird eine Ar Grenwert. Ist ja wirklich simpel, wenn man es so löst. xD

Vielen Dank, das war alles, was ich wissen wollte. :thumb:

[Nuclear-Ping]

Über genetische Algorithmen können Routenplaner auch gesteuert werden.

[stoxx]

vielleicht hilft Dir ja das Animationsprogramm zum Traveling salesman Problem weiter :-)

http://www.swisseduc.ch/informatik/g...nch/index.html

[everdream]

Hach, TSP. ich liebe solche Probleme... :coder:

[christian_r]

Zitat:

Zitat von Speedmaster

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

Bei dem Link gibt es 4 PHP-Warnungen, weil er die "white.html" nicht finden kann. Schade.

[toms]

Zitat:

Zitat von christian_r

Zitat:

Zitat von Speedmaster

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

Bei dem Link gibt es 4 PHP-Warnungen, weil er die "white.html" nicht finden kann. Schade.

Das Tutorial "pathfinding" gibt's im wiki:

http://wiki.delphigl.com/index.php/Tutorial_pathfinding

[Luckie]

Guck mal hier: http://www.michael-puff.de/Developer/Delphi/Demos/ Da habe ich eine Demo zum A*-Algorithmus

[christian_r]

Ich muss mich gerade an den Labyrinth-Algorhythmus erinnern. "Wie kommt man am sichersten aus einem Labyrinth heraus? Indem man immer an der linken Wand entlanggeht." Allerdings würde dieser u. U. für die Strecke Hamburg - Berlin auch über München führen.

Danke für das Tutorial und den Algorhythmus.

[yankee]

Zitat:

Zitat von christian_r

Ich muss mich gerade an den Labyrinth-Algorhythmus erinnern. "Wie kommt man am sichersten aus einem Labyrinth heraus? Indem man immer an der linken Wand entlanggeht." Allerdings würde dieser u. U. für die Strecke Hamburg - Berlin auch über München führen.

Interessant... Jeder sagt immer an der linken Wand :-D.

Das ganze funktioniert allerdings nur mit "2-Dimensionalen" Labyrinthen. Also wenn da Brücken und Tunnel drin vorkommen, wie es im Straßennetz der Fall ist, kann es sein, dass du nur im Kreis läufst.
So Algorithmen kann man natürlich auch nur anwenden, wenn man alle existierenden Straßen kennt. Bei einem Labyrinth ist das ja in der Regel nicht der Fall. Da hast du mit Dijkstra leider keine Chance ;-).

[everdream]

Bei Dijkstra reicht es doch die Straßen, die von der Kreuzung, an der man sich befindet, abgehen und die Straßen, in denen man schon war, zu kennen, oder sehe ich das grade falsch?

[yankee]

Zitat:

Zitat von everdream

Bei Dijkstra reicht es doch die Straßen, die von der Kreuzung, an der man sich befindet, abgehen und die Straßen, in denen man schon war, zu kennen, oder sehe ich das grade falsch?

Ja, das siehst du falsch. Es könnte schliesslich sein, dass du in eine Sackkasse läufst oder sowas. Das ist dann garantiert nicht der kürzeste Weg. Um den kürzesten Weg zu finden brauchst du in jedem Fall Kenntnis vom ganzen Graphen.
Mit A* wird das möglicherweise gehen, da A* mit Heuristik arbeitet. Das ist wesentlich schneller, liefert aber nicht unbedingt den kürzesten Weg. Aber so genau weiss ich das auch nicht, da ich mich mit A* nie genau beschäftigt habe ;-).

[everdream]

Dijkstra liefert doch von einem festen Starpunkt aus den kürzesten Weg zu jedem Knoten. Sackgassen bilden da keine Ausnahme. Und dabei geht der Algorithmus so vor, dass von einem Knoten aus alle Abzweigungen nimmt (nur die von der aktuellen Kreuzung ausgehenden Straßen) und wenn er eine kürzere Verbindung zu einem Knoten findet, dann wird die alter Verbindung (also ein schon bekannter Weg) gelöscht.

Dijkstra funktioniert meiner Meinung nach in einem Labyrinth.

[yankee]

Ja, das ist schon richtig. Wenn ich von der Frage ausgehe "wie komme ich am sichersten aus einem Lapyrinth", dann gehe ich davon aus, dass du dich in einem Lapyrinth befindest, dass du nicht kennst, sprich zu dem du keine Karte hast um dir den Weg zu berechnen.
Um Dijkstra anwenden zu könenn müsstest du dann erstmal das komplette Lapyrinth abgehen. Das Karte zeichenen und Weg berechnen könntest du dann natürlich in einem machen und dir somit einen Arbeitsschritt sparen, aber vermutlich hast du den Ausgang gefunden, bevor du dir sicher sein kannst den kürzesten Weg von deinem Ausgangspunkt gefunden zu haben. Da du dich jedoch ständig im Labyrinth fortbewegen musst, ändert sich dein Startknoten quasi die ganze Zeit und am Ende interessierst du dich sowieso nichtmehr für den Weg zu deinem ehemaligen Startknoten...

[everdream]

Den sichersten/kürzesten Weg aus einem Labyrinth kannst du mit keinem Algo sicher finden, ohne z.B. in Sackgassen zu laufen oder vershciedene Wege zu probieren. Das kann weder ein PC, noch ein Mensch. Und wenn ich richtig informiert bin, kannst du mit einer heuristischen Methode ohne globale Karte auch nichts anfangen,...