[-] Der Weg ist das Ziel
-
So?
Die Sache mit der Effizienz - Heuristiken und der A*-Algorithmus
Schon in der Einleitung wurde beschrieben, dass die wichtigsten Kriterien für einen Wegfindalgorithmus die Effizienz und die Zuverlässigkeit sind.
- Wie wir lange zuvor klärten, ist der Dijkstra-Algorithmus absolut verlässlich.
- Wie wir ebenfalls klärten, ist er performancetechnisch alles andere als eine Leuchte.
Der Umstand, dass beim Dijkstra-Algorithmus eben vom Startpunkt ausgehend ringsum bis zum Ziel gesucht wird, erschien bei unseren bisherigen Graphen wenig kritisch. Dennoch ist es ganz offensichtlich, dass er äußerst redundant arbeitet, da er zahlreiche Felder abläuft und auf ihre Passierbarkeit überprüft, die absolut keinen Beitrag dazu leisten, zum Ziel zu führen … z.B. die in komplementäre Richtung Verlaufenden! Hätte der Algorithmus z.B. in der letztgezeigten Abbildung des letzten Abschnittes den Punkt ganz unten rechts durchsuchen müssen? Nein, hätte er nicht. Trotzdem hat er es getan, eben auf Grund des sich ringsum ausbreitenden Suchverlaufes.
Einen solchen Algorithmus, der wirklich blind auf einem Graphen von einem Startpunkt aus einen Zielpunkt sucht, nennt man einen „uninformierten Algorithmus“ – denn er macht keinerlei Annahmen über Startpunkt, Zielpunkt oder Graphen! Er sucht einfach blind sein Ziel, egal, wo dieses liegt, und egal, wie der Graph aussieht.
Diese Form der Suche war, wie bereits gesagt, bei unseren bisherigen Wegsuchen nicht wirklich kritisch, denn die weißen Bereiche machten nur einen marginalen Teil der Gesamtfläche aus, während die schwarzen nicht durchsucht wurden. Nun betrachten Sie jedoch einmal den folgenden Graphen:
Erwartungsgemäß würde der Algorithmus die gesamte weiße Fläche in einem Quadrat (oder einer Raute, falls wir diagonale Schritte verböten) um den Startpunkt absuchen. Auf Grund der Beschaffenheit der Wände würde auch hier der Algorithmus den kürzesten Weg zu P[Z] auf jeden Fall finden. Sonderlich performant wäre die Angelegenheit jedoch harmlos ausgedrückt nicht …
Für einen solchen Fall arbeiten kommerzielle Implementationen von Wegfindalgorithmen in Symbiose mit so genannten Heuristiken.
Der Dijkstra-Algorithmus ist ein uninformierter Algorithmus, da er keine Annahmen über seinen Weg macht. Da neben dem Startpunkt auch der Zielpunkt bekannt ist, kann eine Heuristik Annahmen über die Wahrscheinlichkeit machen, mit der ein passierbarer anliegender Punkt zum Ziel führen könnte. Anhand dieser Annahmen kann sie dann jedem dieser Punkte eine Gewichtung (oder besser Priorität) zuteilen: Ist es unwahrscheinlich, dass der Punkt zum Ziel führt, so wird ihm eine niedrige Priorität zugewiesen. Ist es wahrscheinlich, entsprechend eine höhere. Der Algorithmus wird nun die Punkte mit höherer Gewichtung vor denen mit niedrigerer Gewichtung abarbeiten. Da der Algorithmus anhand der Koordinaten des Start- und Zielpunktes ermitteln kann, dass der Zielpunkt rechts unten vom Starkpunkt liegt, kann die Heuristik alle Punkte mit niedriger Priorität (z.B. diejenigen, die links vom Startpunkt oder darüber liegen) sozusagen „vorerst aussortieren“. Mit einer Heuristik würde sich der vom Algorithmus bearbeitete Graph (unter der Voraussetzung, dass ein Ziel gefunden wird – denn falls nicht, würde der Algorithmus nach wie vor jeden passierbaren Punkt überprüfen) in etwa wie folgt verändern, was schon eine deutliche Verbesserung zur vorherigen Aussicht darstellt:
Diese Graphik soll nun darstellen, welche Punkte – die weißen – der Algorithmus überprüfen würde, denn seiner Heuristik getreu würde er immer zunächst diejenigen erproben, die näher in Richtung Zielpunkt liegen. Alle Anderen würde er zunächst zurückstellen und, da er seinen Zielpunkt erreichen würde, niemals nachträglich passieren.
Sollte nun trotzdem ein solcher (niedrig gewichteter) Punkt zum Ziel führen, so wird der Algorithmus den Weg immer noch finden, allerdings u.U. erst später, als wenn er ohne Heuristik gesucht hätte.
Wenn wir unseren Dijkstra-Algorithmus um eine Heuristik erweitern würden, könnten wir ihn ungemein beschleunigen! Dieser „neue“ Algorithmus (Dijkstra-Algorithmus + Heuristik) ist in der Informatik ebenfalls weit verbreitet und wird A*-Algorithmus (a star) genannt!
Der A*-Algorithmus behebt also das Performanceproblem des Dijkstra-Algorithmus in vielen Fällen (warum es „viele“ und nicht „alle“ sind, werden wir noch klären), doch er bringt einen äußerst hässlichen Nachteil mit sich!
Warum?
- Wenn Sie diese Frage nun beantworten können, haben Sie die Funktionsweise des Dijkstra-Algorithmus verstanden!
- Können Sie die Frage hingegen nicht beantworten, sollten Sie vor der weiteren Lektüre dieses Kapitels dasselbe noch einmal von vorne durchlesen!
Zuvor wurde immer wieder betont, dass der große Vorteil des Dijkstra-Algorithmus seine 100%ige Zuverlässigkeit ist. Soweit so gut. Der A*-Algorithmus bricht nun aber leider mit dieser Sicherheit, denn dadurch, dass er die höher priorisierten, anliegenden Punkte vor den niedriger gewichteten absucht, verläuft seine Suche nicht mehr quadrat- bzw. rautenförmig, sondern kann jede mögliche Form annehmen, abhängig von der Position des Zielpunktes in Relation zu der des Startpunktes.
Wir stellen fest:
*-
Wird eine Heuristik wie oben beschrieben verwendet, ist nicht mehr gewährleistet, dass der Algorithmus tatsächlich den kürzesten Weg findet!
Warum?
Stellen Sie sich vor, der Graph würde wie folgt aussehen:
- Der obere, gezackte Weg, läuft stetig nach rechts, also in Richtung Ziel.
- Zudem verläuft er ungefähr die Hälfte der Strecke nach oben, auch in Richtung Ziel.
- Die Streckenstücke, die er nach unten rechts verläuft (rechts ja nach wie vor in Richtung Ziel), hat er dem Weg ganz unten voraus, dass er näher am Ziel liegt.
Durch eine schlechte Heuristik könnte der Algorithmus also den gesamten oberen Weg durchlaufen, bevor er sich dem unteren widmen würde, denn die Wahrscheinlichkeit, dass der obere Weg zum Ziel führte, könnte (je nach Errechnungsart) größer sein als diejenige des Weges ganz unten – Manchmal viel größer, manchmal vielleicht nur ein (entscheidendes) Quäntchen.
Auf dem oberen Weg würde der Algorithmus irgendwann am Ziel ankommen und somit seinen Auftrag für erledigt halten. Wäre es unser Ziel, irgendeinen Weg zu finden, so würde das Verhalten des Algorithmus auch absolut legitim sein. Da wir aber den Anspruch an den A*-Algorithmus stellen, den kürztmöglichen Weg zu ermitteln, ist das Ergebnis schlichtweg inakzeptabel – denn streckenmäßig ist der untere der beiden Wege zweifelsohne wesentlich kürzer!Wir bräuchten eine Heuristik, die die obige Situation erkennen und entsprechend reagieren kann. Diese wäre aber ungemein schwer (oder zumindest für uns kaum realistisch) zu implementieren, äußerst umfangreich und selbst sie könnte kaum 100% aller Fälle erkennen.
Moderne Implementierungen kommen jedoch tatsächlich nahe an eine vernachlässigbar niedrige Fehlerkennungsrate heran. Dennoch ist ein solcher Algorithmus, so er die gleiche Verlässlichkeit besitzen soll wie der Dijkstra-Algorithmus, um einiges schwieriger zu implementieren, was in manchen Fällen ein entscheidendes Kriterium sein kann.Eine Heuristik, die sich dadurch auszeichnen, die Länge des kürzesten Weges nicht zu überschätzen, nennt man „monotone Heuristiken“. Ist gegeben, dass diese Heuristik den kürzesten Weg wirklich niemals überschätzt, so ist der kürzeste Weg garantiert.
Moderne Implementationen des A*-Algorithmus arbeiten meist mit so genannten „zulässigen Heuristiken“, welche zumindest den Weg von einer Koordinate zur nächsten nicht überschätzen. Dies fällt schwer, sich bei unserer zweidimensionalen Landkarte vorzustellen, doch in einer Verknotung von Punkten (z.B. einer verketteten Liste) könnten die einzelnen Koordinaten unterschiedlich weit voneinander entfernt sein.
Wir stellen also fest:
*-
Heuristiken können die Wegfindung ungemein beschleunigen.
-
Schlechte Heuristiken wirken sich kritisch negativ auf die Zuverlässigkeit des Algorithmus aus.
Ein letzter Aspekt des A*-Algorithmus ist der, dass er – auch wenn er den kürzesten Weg findet – tatsächlich länger brauchen könnte, als der Dijkstra-Algorithmus, wenn Erstgenannter eine schlechte Heuristik verwendete, da der A*-Algorithmus eben alle als weniger wichtig priorisierte Punkte erst einmal in seiner Warteschleife zurückschiebt. Trifft seine Heuristik dabei falsche Schätzungen, die ihn zunächst Wege abarbeiten lassen, auf denen er nicht zum Ziel kommt, so könnte der Dijkstra-Algorithmus, der ja einfach annahmslos und objektiv (man könnte im wahrsten Sinne des Wortes sagen „hirnlos“) in einer sich ausbreitenden Fläche um sich herum sucht, in dieser dem A*-Algorithmus verlorenen Zeit das Ziel finden. Dies ist äußerst unwahrscheinlich, bei einer schlechten Heuristik jedoch theoretisch möglich.
Auch verschlingt der A*-Algorithmus mehr Ressourcen auf einmal als der Dijkstra, da er eine priorisierte Warteliste für die verbleibenden Knoten führen muss. In der Praxis könnte dafür z.B. ein s.g. Fibonacci-Stack verwendet werden, welcher es ermöglicht, performant beliebig priorisierte Werte einzufügen, und ebenso performant immer den jeweils höchst priorisierten wieder zu entnehmen.
-
Ich schau's mir später an. Wenn Du Lust hast, ich bin oft im IRC, da können wir auch mal ne Runde drüber reden. Ich hab noch ein paar Kleinigkeiten entdeckt.
Ich hoffe Du hast nicht das Gefühl, dass ich Deinen Artikel schlechtmachen möchte.
-
Was mir nebenbei mal aufgefallen ist: Hast Du mal drüber nachgedacht, warum Dein Dijkstra wie ne normale Breitensuche aussieht?
-
Guter Artikel soweit
jedoch müssen da noch ein Paar Schlitzer raus :- Wegfindalgorithmen im realen Leben
Du redest von kürzestem Weg und meinst schnellsten. Dies ist schon ein Unterschied auf welchen man bei diesem Thema aufpassen sollte. - Voraussetzungen eines Wegfindalgorithmus'
Kannst du das Wort Graph nicht hier durch etwas anderes ersetzen? Beim Wort Graph denke ich immer direkt an Knoten und Kanten. Aussagen wie "wie der Graph über Achsen verfügt" ergeben dann gar keinen Sinn. Vielleicht Ebene oder Raum. Wieso nicht einfach bei Landkarte bleiben?
Hier eine Beispiel von dem was ich mir bei einem Graph vorstelle:
http://de.wikipedia.org/wiki/Dijkstra-Algorithmus#BeispielLeser die ganz neu sind und noch nicht wissen was ein Graph ist werden sich darunter eine Ebene vorstellen was falsch wäre und die Leser denen es bereits ein Begriff ist werden verwirrt sein.
- Das Prinzip des Dijkstra-Algorithmus
Dazu teilen wir unsere Landkarte zunächst in eine x- und eine y-Achse ein, welche wir anschließend jeweils in beliebig große, jedoch allesamt gleich große Teilstrecken unterteilen.
Tut mir leid aber bei dem Satz kann ich dir nicht folgen. Du gibst dir ein Koordinatensystem und was du mit den Teilstrecken meinst verstehe ich nicht.
Sollen die Farben im Hintergrund des Bildes vielleicht die Höhe des Bodens darstellen also wie auf einer topologischen Karte? Wäre dann vielleicht besser eine richtige Karte zu nehmen.
* Zwischen dem Start- und dem Zielpunkt liegen n weitere Punkte, von denen ebenfalls ein jeder mit einem Koordinatentupel eineindeutig beschrieben werden kann.
Du hast vorher gesagt, dass jeder Punkt eindeutig durch ein Koordinatentupel beschrieben werden kann. Dies ist keine besondere Eigenschaft der n Punkte. Welche n Punkte eigentlich?
- Man muss halt differenzieren …
Die Antwort ist natürlich die, dass uns der Algorithmus in etwa so zuverlässig den kürzesten Weg von A nach B berechnet kann, wie wir sagen können, ob Schrödingers Katze noch immer am Leben ist oder nicht
Du kannst nicht sagen, ob seine Katze lebt aber du kannst mit Sicherheit sagen, der kürzste Weg von A nach B die Luftlinie ist. Wieso ist der Algo also unzuverlässig? Du widersprichst dir übrigens selbst da du sagst der Algo würde immer den kürzten Weg finden.
- Von Feldern, Nullen und Einsen! Oder auch Arrays …
Unsere Datenstruktur weißt Ähnlichkeiten mit einer „Menge“ auf; entsprechend den Einflüssen des Englischen auf die Informatik bezeichnet man sie als „Array“ (engl. „Feld“, „Menge“).
ar·ray ['] I v/t 1. Truppen etc aufstellen.
2. (oneself sich) kleiden, (heraus)putzen.
II s
3. mil. Schlachtordnung f.
4. fig. Phalanx f, (stattliche) Reihe.
5. Kleidung f, Staat m.
2001 Langenscheidt KG, Berlin und MünchenDer Begriff kommt wahrscheinlich daher, dass man die Element im Speicher aufstellt. Mit Feld oder Menge hat es laut Langenscheidt nichts zu tun.
Eine Menge ist ein mathematischer Begriff der durch eine Vielzahl von Datenstrukturen dargestellt werden kann. Er ist selber aber keine Datenstruktur.
Wie wäre es wenn du einfach beim Begriff Landkarte bleibst dann ist ein Feld oder 2D-Array sehr nahe liegend?
(Hinweis zur Vollständigkeit: Natürlich können Graphen auch mit anderen Mitteln, z.B. Structs oder Klassen, verketteten Listen und mehr realisiert werden. Für uns reichte jedoch das Array völlig aus. Lassen Sie sich nur gesagt sein: Es stellt die Spitze des Eisberges dar.)
Structs oder Klassen sind ein Sprachmittel und keine Datenstrukturen. Verkettete Listen sind eine Datenstruktur werden aber soweit ich weiß nicht oft im Zusammenhang mit Graphen genutzt.
In der Formulierung des Algo wären Zeilenumbrüche nicht schlecht. Paragraphen helfen es dem Leser zusammenhängende Ideen besser zu erkennen.
- Zusammenfassende Beschreibung des Dijkstra-Algorithmus
1. Ermitteln des Startpunktes.
2. Ermitteln der Punkte, die am Punkt anliegen.
3. Prüfe nacheinander jeden der anliegenden Punkte, der noch nie zuvor betreten wurde, ob er 0 (begehbar) oder 1 (blockiert) ist.
4. Merken derjenigen der anliegenden Punkte, die 0 (begehbar) sind.
5. Mit jedem dieser anliegenden Punkte wieder bei 2. fortfahren, bis ein gefundener begehbarer Punkt gleich dem Zielpunkt ist; in dem Fall Berechnung abschließen, da Weg gefunden!Der Dijkstra Algo kann man auch als gewichtete Breitensuche bezeichnen. Die Beschreibung passt aber besser auf eine Tiefensuche was ein anderer Algo wäre.
Hab keine Zeit den Rest zu lesen. Mache ich vielleicht ein anderes Mal
- Wegfindalgorithmen im realen Leben
-
Danke für die Kritiken
Nun, insgesamt ist der Artikel so meiner Ansicht nach nicht wirklich veröffentlichbar. Ich werde wohl große Teile neuschreiben. Von daher lohnt ein Lesen der weiteren Teile des Artikels im Moment imho noch nicht.
Wartet bitte, bis ich eine korrigierte Version fertig gestellt habe (was aber noch dauern könnte, ich bin im Moment privat wieder sehr beschäftigt).
-
Setz den Artikel dann vielleicht auf [A] zurück. Wenn du ihn grundlegend überarbeitest dann würde ich den Namen Dijkstra nicht mehr verwenden. Sein Algo ist nun einmal ein standard Algo in der Graphentheorie und deine Version ist eher eine Variante und entspricht nicht gerade dem.
-
Zum Aufwand: Es fehlt noch, dass bei O(n) [oder eben T(n)] das n die eingabegroesse (z.B. Landkartengroesse) ist, sowie das in Klammern eine Funktion in abhaengigkeit von n ist. Also dass ein Algo der O(n) hat, bei der Verdoppelung des Input in etwa doppelt so lang laeuft, aber ein Algo der O(log n) hat, eben bei Verdoppelung nur etwas laenger (log(2) mal) braucht.
Zur Monotonie: Eigentlich heist Monotonie etwas mehr als "macht immer eine richtige Schaetzung". Die monotone Schaetzfunktion gibt umso hoehere Werte zurueck, desto weiter der Abstand ist (also eben z.b. Luftlinie bei "Weg"suche). Ist das nicht gewaehrleistet, so ist der Algo zwar nicht Optimal, terminiert aber (dank Backtracking) doch.
Etwas am Rande: Ich fand die Erklaerungen von Suchalgorithmen auf echten Graphen immer anschaulicher als auf solchen Bildern. Es lassen sich auch so schoen laengere Wege anzeigen.
Sonst aber ein schoenes Ding!
-
Ben04 schrieb:
Der Begriff kommt wahrscheinlich daher, dass man die Element im Speicher aufstellt. Mit Feld oder Menge hat es laut Langenscheidt nichts zu tun.
dict.leo.org sagt dass das schon ne gültige Übersetzung ist. Über die Wortabstammung sagtdas zwar nichts aus, aber die ist wohl hier nicht so interessant.
-
Naja, Menge würde ich eher mit set als mit Array übersetzen.
-
Der Artikel ist gecancelt.
Aber das hat sich vermutlich ohnehin jeder schon gedacht ...
-
Schade,
Falls jemand ihn zu Ende schreiben will, darf er das was du bereits hast verwenden oder nicht?
-
Inhaltlich darf gerne etwas übernommen werden, falls nötig. 1:1 kopierter Text oder die Graphiken bleiben jedoch mir vorbehalten.
Sonst möchte ich den Artikel vlt. mal auf meiner HP veröffentlichen (atm fiktiv, aber ja möglich) und bekäme dann rechtliche Probleme. Z.B. falls eine neue Regelung bezüglich der Nutzungsrechte der Artikel gefunden wird (was ja von Marc+uus schon mehrfach angesprochen wurde).
-
Schade.