[-] Der Weg ist das Ziel

Reyx

Der Weg ist das Ziel!

Automatisierte Wegfindung mit Hilfe des Dijkstra- und A*-Algorithmus

Theoretische Abhandlung für Neulinge auf dem Gebiet des Pathfinding

Reyx schrieb:

Wie schon gesagt ist der Artikel ausschließlich theoretischer Natur.

Zudem ist er extrem ausführlich und soll den absoluten Neuling im Gebiet des Pathfinding zum Denken anregen; er soll die Fragen "für sich selbst beantworten", bevor der Text ihm die Lösung präsentiert.

Entsprechend werden ihn alle etwas fortgeschritteneren Leser sehr langatmig und wenig anspruchsvoll. Sei's drum - Auf für Anfänger will mal ein Artikel geschrieben sein :p

Den Titel des Artikels habe ich bewusst gewählt, da er eben theoretischer Natur ist. Daher wäre der Name "Pathfinding mit Dijkstra" o.ä. imho falsch gewählt; es geht hier wirklich hauptsächlich darum, den Leser zum eigenen Nachdenken, eigenen erwägen der Pro- und Contras und der Herangehensweise anzuregen. Der Artikel will keine Anleitung sein, wie man einen Pathfinder implementiert.

Einleitung

Wegfindung ist ein komplexes Themengebiet der Informatik, welches sowohl auf unsere Gesellschaft, unsere Wirtschaft als auch auf unsere Freizeitaktivitäten einen häufig unterschätzten Einfluss ausübt. Doch was darf man sich konkret unter einer „Wegfindung“ vorstellen?
Ganz allgemein betrachtet wollen wir an dieser Stelle vorweg definieren:

Eine Wegfindung ist das Ermitteln eines passierbaren Weges von einem Punkt A auf einem beliebigen Graphen zu einem Punkt B. Man spricht hierbei auch von „Pathfinding“.
Ein Wegfindalgorithmus ist diejenige Handlungsvorschrift, die beschreibt, wie eben diese Ermittlung durchgeführt wird. Auf Grund des starken Einflusses des Englischen auf die moderne Informatik, wird hier auch häufig vom „Pathfinding-Algorithmus“ gesprochen, eine Verknüpfung des Deutschen mit dem Englischen, wie sie zunehmend Akzeptanz findet.

Im Allgemeinen stellt man an einen solchen Algorithmus den Anspruch, nicht nur den Weg vom Start- zum Zielpunkt zu finden, sondern man erwartet auch noch, dass der gefundene Weg der kürztmögliche ist.

*Als Beispiel:

Eine Wegfindung wäre es, wenn Sie von Berlin nach Bremen reisen wollten.
Der Wegfindalgorithmus wäre die abstrakte (= auf andere Städte 1:1 übernehmbare) Beschreibung dessen, was Sie tun müssten, um diesen Weg zu ermitteln (z.B. Landkarte aufschlagen, Routen durchgehen, Umleitungen evaluieren etc., Strecken messen).

Über Algorithmen

Womit wir uns in dieser Abhandlung beschäftigen werden, ist hauptsächlich – aber nicht ausschließlich – der in der Einleitung letztgenannte Punkt: Der Algorithmus! Es gibt zahlreiche Wegfindalgorithmen, welche sich in diversen Faktoren unterscheiden. Generell gibt es jedoch zwei Kritikpunkte, die einen Algorithmus ausmachen:

Einerseits betrachtet der Informatiker die Effizienz eines Algorithmus, gemessen an der s.g. O(n)-Laufzeit, welche die Anzahl der benötigten Operationen innerhalb des Algorithmus angibt. Unter der Optimierung eines Algorithmus versteht man das Reduzieren dieser O(n)-Laufzeit und somit die Steigerung der Effizienz der Berechnungen.
Beispiel: Sie haben einen Algorithmus, der in 100 Rechenschritten von jedem beliebigen Punkt der Erde die Distanz zu einem anderen ermittelt. Er hat somit eine Laufzeit von O(n) = 100. Wenn Sie die Laufzeit verringern, so dass er Algorithmus den Weg schon nach z.B. 90 Rechenschritten ermittelt und seine Laufzeit somit fortan O(n) = 90 beträgt, so haben Sie den Algorithmus optimiert.
Andererseits ist natürlich auch die Zuverlässigkeit von kritischer Bedeutung:
Findet der Algorithmus tatsächlich den kürzesten passierbaren Weg?
Welche Hindernisse in Form von unpassierbaren Stellen berücksichtigt er dabei?
Ist er in der Lage, zu erkennen, wenn es keinen Weg von Punkt A nach Punkt B gibt?
Bleiben seine Berechnung verlässlich, wenn er mit Zahlen rechnen muss, die gegen 0 streben?
Bleiben seine Berechnung verlässlich, wenn er mit Zahlen rechnen muss, die gegen ∞ streben?
Verfügt der Algorithmus über Lücken in seinen Definitions- oder Wertebereichen, die ihn zu ungewöhnlichem Verhalten bringen könnten (z.B. Divisionen durch Null, Buffer Overflows o.ä.)?

Wegfindalgorithmen im realen Leben

Wo begegnen uns solche Wegfindalgorithmen im realen Leben?

Stellen Sie sich z.B. vor, sie hätten eine Landkarte vor sich liegen und wollten (wieder einmal) von Berlin nach Bremen reisen. Die Kenntnis des direktesten Weges – der Luftlinie – ist für sie als Kraftwagenfahrer erfahrungsgemäß von nicht gar so großem Nutzen. Hingegen sehen Sie sich zahlreichen Zwischenstationen in Form von u.a. Städten und Autobahnrouten gegenüber, die es „abzuklappern“ gilt:

Fahren Sie über Schwerin und Hamburg?
Oder ist vielleicht doch der Weg durch Sachsen-Anhalt, also über Magdeburg und Hannover, der Kürzere?

Sie könnten nun mühselig die einzelnen Strecken auf der Karte abmessen und würden somit herausfinden, welche Route (rein streckenmäßig - Dinge wie Geschwindigkeitseinschränkungen und Umleitungen außer Acht gelassen) die Kürzeste ist. Dies unterliegt jedoch den Schwankungen Ihres Vermessungstalentes, ihrer Kopfrechenkompetenz und nicht zuletzt ist es eine einmalige Aktion: Sollten Sie sich umentscheiden, so dass nicht Bremen sondern vielleicht Stuttgart das Ziel sein soll, so beginnt der ganze Spaß von Neuem.

In einer solchen Situation ist ein Wegfindalgorithmus eine äußerst praktische Sache (abgesehen davon, dass ich grundsätzlich die zweite Route vorziehen würde – Magdeburg, weil es eine sehr schöne Stadt ist, und Hannover wegen der Cebit …).

Stellen Sie sich weiter vor, Sie seien Vorsitzender der Versandabteilung einer Speditionsgesellschaft. Sie können sich nun gewiss vorstellen, dass es für Sie von allerhöchstem Interesse ist, auf jeder Transportfahrt immer den wirklich absolut kürzesten Weg zu nehmen! Müssten Sie in dieser Branche jeden Weg manuell erwägen, würden Sie mehr Zeit beim Rechnen als beim Ausliefern der sehnlichst erwarteten Ware verbringen!

Auch im militärischen Sinne finden Wegfindalgorithmen (leider!) Verwendung, z.B. bei zielsuchenden Projektilen. Wenn diese ein bewegliches Ziel verfolgen, errechnet ein Wegfindalgorithmus in einem bestimmten Zeitintervall immer wieder den kürzesten Weg zum Zielobjekt, so dass das Geschoss seine Flugbahn entsprechend anpassen kann (wofür wiederum eine andere Gattung von Algorithmen zuständig ist, aber dies nur am Rande …).

Als letztes Beispiel seien die guten alten Computerspiele genannt:
Was wäre wohl das wohlüberlegteste Spiel, würden die anderen Charaktere (s.g. NPCs – Non Playable Characters) einfach wirr in der Gegend herum laufen? In der Praxis tun sie dies nicht – Vielmehr verfolgen sie den Hauptcharakter oder fliehen womöglich vor ihm. Was sie auch tun, ihre Bewegungen beziehen sich zumeist auf die Position des gespielten Charakters. Auch hier werkelt im Hintergrund tüchtig ein Wegfindalgorithmus.

Was ist der Dijkstra-Algorithmus?

Einer der grundlegenden weil primitivsten Wegfindalgorithmen in der Informatik ist der s.g. Dijkstra-Algorithmus (ˈdɛɪkˌstra). Er ist relativ einfach zu implementieren (= in einer Programmiersprache zu formulieren) und zeichnet sich insbesondere dadurch aus, dass er garantiert als einzigen potentiellen Weg den kürztmöglichen findet, unabhängig davon, wie viele andere (längere) Wege es noch gibt.

Sie können folglich davon ausgehen, dass der vom Dijkstra-Algorithmus errechnete Weg mit einer Wahrscheinlichkeit von exakt 100% der Kürzeste ist, den es gibt. Das ist nicht schlecht und meist wesentlich verlässlicher, als andere Wegfindalgorithmen!

Hingegen arbeitet er jedoch nicht wirklich performant (= schnell), wie wir noch sehen werden.

Sie können davon ausgehen, dass die Laufzeit des Dijkstra-Algorithmus oft über der Laufzeit anderer Wegfindalgorithmen liegt.
Er bietet mithin eine ausgewogene Gewichtsverteilung der Kriterien Effizienz und Zuverlässigkeit.

Voraussetzungen eines Wegfindalgorithmus'

Bevor wir nun beginnen, uns mit dem Eingemachten des Dijkstra-Algorithmus zu beschäftigen, führen wir zunächst einige Gedankengänge durch. Was braucht ein Algorithmus alles, um von einem Punkt zum Anderen zu kommen? Na, da haben wir doch schon gleich ganz intuitiv und wahrscheinlich unbewusst zwei Voraussetzungen genannt!

*Wir stellen fest:

Voraussetzung: Ein Startpunkt (im Folgenden P[S] genannt – Der Punkt mit den Indizes des Startpunktes).
Voraussetzung: Ein Zielpunkt (im Folgenden P[Z] genannt – Der Punkt mit den Indizes des Zielpunktes).

Sie mögen sich nun fragen, woher auf einmal der Begriff „Index“ (Plural: Indizes) kommt. Nun, genau daraus ergibt sich unsere
*

3. Voraussetzung: Ein Graph, auf welchem sowohl P[S] und P[Z] liegen, und auf dem der Algorithmus den kürzesten Weg finden soll.

Was wir uns unter diesem Graphen vorstellen dürfen?
Betrachten wir erneut unser Berlin->Bremen-Beispiel:

Die Landkarte ist unser Graph.
P[S] ist der Punkt auf dem Graphen, an dem wir starten. Dieser hat auf der Landkarte ein zweidimensionales Koordinatentupel (= ein Koordinatenpaar), das eineindeutig die Position des Punktes beschreibt. Dieses ist mit seinen „Indizes“ gemeint. Im Beispiel könnte der Punkt P[S] das Stadtzentrum von Berlin sein.
P[Z] ist der Punkt auf dem Graphen, zu dem wir gelangen möchten. Auch dieser verfügt über ein entsprechendes Koordinatentupel, mithin seine Indizes. Im Beispiel könnte der Punkt P[S] das Stadtzentrum von Bremen sein.

Wir stellen weiterhin fest:

Jeder beliebige Punkt auf dem Graphen verfügt über ein Koordinatentupel, das seine Position auf dem Graphen eineindeutig beschreibt. Stellen Sie sich diese Indizes wie die Achsenwerte in einem Koordinatensystem vor. Genau genommen sind sie exakt dies, nur dass ein Koordinatensystem i.d.R. auf zwei bzw. maximal drei Dimensionen beschränkt ist, ein Algorithmus hingegen mit theoretisch beliebig vielen Dimensionen rechnen kann.
Tatsächlich besitzt jeder Punkt genau so viele Indizes, wie der Graph über Achsen verfügt.
Bei unserer zweidimensionalen Landkarte verfügen Start- und Zielpunkt folglich über je 2 Indizes: Einen Index für die x-Koordinate, einen für die y-Koordinate.
Würden wir nun noch die Lufthöhe in unsere Landkarte übernehmen, so würde jeder Punkt zusätzlich über eine dritte Koordinate verfügen, nämlich die für die Z-Achse.

Der Einfachheit halber werden wir in dieser Abhandlung jedoch im zweidimensionalen Raum bleiben.

Das Prinzip des Dijkstra-Algorithmus

Übertragen wir nun unsere Erkenntnisse auf unser Vorhaben, die kürzeste Strecke von Berlin nach Bremen zu ermitteln. 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. Nun können wir die Position des Startpunktes, P[S](5; 3), ebenso angeben, wie die des Zielpunktes, P[Z](1; 2).

Betrachten wir nun unsere Karte, so erkennen wir:
*

Zwischen dem Start- und dem Zielpunkt liegen n weitere Punkte, von denen ebenfalls ein jeder mit einem Koordinatentupel eineindeutig beschrieben werden kann.

Diese Erkenntnis ist nicht neu, wir erfuhren sie bereits im letzten Abschnitt. Doch denken wir etwas genauer darüber nach, so stellen wir fest, das dies eine ganz wichtige Eigenschaft unserer Karte ist!
Aus ihr erkennen wir nämlich schon, was der Algorithmus letztlich tun muss, um uns den kürzesten Weg vom Start- zum Zielpunkt zu ermitteln:
*

Er muss sämtliche Punkte zwischen P[S] und P[Z] abarbeiten, bis er am Ziel angekommen ist.

Dies alleine reicht aber noch nicht, um unseren Algorithmus vernünftig arbeiten zu lassen. Warum? Nun, er verfügt über einen Startpunkt, einen Zielpunkt und einen Graphen. Das ist alles. Würden wir nun so den Algorithmus implementieren, würde er uns schlichtweg ein sehr ernüchterndes Resultat liefern – Nämlich die direkte Luftlinie!
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 Lektüre der weiteren Kapitel nochmals die vorherigen durchlesen, insbesondere das vorherige und dieses, bis Sie die Frage beantworten können!

Man muss halt differenzieren [e]hellip[/e]

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 (wobei man anmerken muss: Falls ja, Hut ab, Herr Schrödinger! Meine Katze wurde nicht so alt!). Um nämlich den kürzesten Weg zu ermitteln, muss der Algorithmus natürlich wissen, welche Wege für ihn tabu sind!

Wir können allgemein formulieren:
*

Beim Abarbeiten der Punkte auf dem Graphen muss der Algorithmus diejenigen Punkte unberücksichtigt lassen, die als nicht passierbar gelten.

Oder wie würden Sie es finden, wenn Ihr Navigationsgerät Sie während Ihrer Autofahrt geradewegs durch einen Fluss fahren lassen wollte (was in der Vergangenheit wohlgemerkt tatsächlich geschehen ist)?

Wie kann der Algorithmus nun aber entscheiden, welche Wege passierbar sind? Würden wir ihm nämlich tatsächlich einfach nur unsere Landkarte mitteilen, ohne ihn mit dieser so wichtigen Information auszustatten, so würde zwangsläufig eine der folgenden Situation eintreten:

Möglichkeit: Der Algorithmus nimmt an, dass alle Koordinaten passierbar sind. Was wäre das Ergebnis der Berechnung? Richtig! Die Luftlinie, wie wir schon im letzten Abschnitt feststellten. Denn wenn alle Wege passierbar sind, dann ist die Luftlinie natürlich zweifelsohne der direkteste wie kürzeste Weg zum Ziel.
Möglichkeit: Der Algorithmus nimmt an, dass alle Koordinaten nicht passierbar sind. In diesem Falle würde er das Ziel niemals erreichen und uns als Ergebnis (subjektiv korrekterweise) liefern, es gäbe keine beschreitbare Verbindung zwischen Start- und Zielpunkt.

Wir müssen unseren Graphen also irgendwie mit der Information ausstatten, welche Wege passierbar sind.
Betrachten wir unsere Karte, stellen wir fest, dass diese Information in ihr eigentlich enthalten ist.
Viel schlimmer jedoch: Wir erkennen dass unsere Landkarte äußerst redundante (=verschwenderische) Informationen enthält! Der Algorithmus muss nicht wissen, wo Autobahnen verlaufen! Er muss nicht wissen, wo Seen und Meere liegen! Und ebenso ist es im schnurzegal, wo welche Städte liegen! Er braucht wirklich nicht mehr zu wissen, als:

Punkt A ist passierbar.
Punkt B ist nicht passierbar.
Punkt C ist nicht passierbar.
Punkt D ist wiederum passierbar.
Usw. usf.

Der logische Schluss, den wir daraus ziehen?
Ganz klar! - Dass wir alle diese Informationen, die wir absolut nicht benötigen, aus dem Graphen entfernen!

Von Feldern, Nullen und Einsen! Oder auch Arrays [e]hellip[/e]

Wenn wir unseren Graphen auf das absolut Notwendigste reduzieren, dann enthält er zu jedem beliebigem (wir erinnern uns: eineindeutigem!) Koordinatentupel nur noch eine einzige Information:

Ist der Punkt passierbar?
Oder ist er es nicht?

In der Informatik differenziert man zwischen den Zuständen "Strom" und "kein Strom", bzw. in den modernen Hochsprachen lieber zwischen "wahr" (1, true) und "falsch" (0, false). Jedes Koordinatenpaar wird also auf exakt diese Information reduziert: Ob der Punkt passierbar ist, in dem Fall weisen wir dem Tupel eine 0 (da nicht blockiert) zu, oder ob er blockiert ist, in dem Fall weisen wir dem Tupel eine 1 (da eben blockiert) zu. Hier tangieren wir die s.g. Bool’sche Algebra …

Das, was wir erhalten, ist eine Datenstruktur, welche uns auf binäre (= 1 oder 0, wahr oder falsch, engl. "true" oder "false") Art und Weise das angibt, womit unser Algorithmus arbeiten kann! Für jedes beliebige Koordinatenpaar besitzt unser Graph nur noch einen von zwei Werten:

0 besagt, dass der Punkt am speziellen Koordinatenpaar passierbar ist.
1 besagt, dass der Punkt am speziellen Koordinatenpaar unpassierbar ist.

An dieser Stelle sei natürlich angemerkt, dass die Festlegung 0 = passierbar und 1 = unpassierbar reine Definitionssache ist. Wir könnten es z.B. auch anders herum definieren, wenn wir wollten.

Diese doppelten und dreifachen Ausführungen mögen Ihnen übertrieben erscheinen, aber es soll wirklich klar werden, wie wir diese Eigenschaften für unseren Algorithmus gewinnbringend (= uns dem Ziel näherbringend) verwenden können!

Unseren Algorithmus können wir anweisen:

Wenn P(0; 0) = 0, dann gehe weiter, wenn = 1, dann bleibe stehen.
Wenn P(0; 1) = 0, dann gehe weiter, wenn = 1, dann bleibe stehen.
Wenn P(1; 0) = 0, dann gehe weiter, wenn = 1, dann bleibe stehen.
Wenn P(1; 1) = 0, dann gehe weiter, wenn = 1, dann bleibe stehen.
Usw. usf.

Oder ganz allgemein:
*

Wenn P(x; y) = 0, dann gehe weiter, wenn = 1, dann bleibe stehen.

Hierbei bedeute "weiter gehen", dass der Punkt so vorgemerkt wird, dass der Algorithmus auch seine Nachbarn auf Passierbarkeit überprüfen wird, sobald er mit der Überprüfung der Nachbarspunkte des Ausgangspunktes fertig ist. "Bleibe stehen" sei ein Vormerken als "nicht passierbar": Der Punkt kann nicht begangen werden, scheidet somit als möglicher Wegpunkt unseres gesuchtes Weges aus. Da ein solches Vormerken als "nicht passierbar" jedoch bereits durch den Punkt selbst gegeben ist (er ist ja durch 1 als blockiert markiert), muss sich der Algorithmus um den Punkt gar nicht weiter kümmern.

Dies ist eine Instruktion (= Anweisung), mit der unser Algorithmus umgehen kann.

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“). Sie ist letztlich die digitale Repräsentation unseres Graphen, reduziert auf das Allerallernötigste. Ihre besondere Eigenschaft, die es dem Algorithmus ermöglicht, mit ihr zu arbeiten, ist, dass der Algorithmus nur zwei Werte kennen muss – nämlich die x- sowie die y-Koordinate –, um aus der Struktur abzulesen, ob der entsprechende Punkt begehbar ist oder nicht. Ist er das, setzt der Algorithmus seine Arbeit fort.
Ist er hingegen nicht passierbar, so braucht sich der Algorithmus in seiner Wegsuche nicht weiter um den Punkt kümmern. Denn ein Punkt, der nicht passierbar ist, kann logischerweise niemals ein Wegpunkt unseres gesuchten kürzesten Weges sein!
Wir haben also unseren Graphen in ein Array verpackt, das direkt unsere zweidimensionale Landkarte repräsentiert, reduziert auf die Wege, die wir begehen können (was in der Praxis z.B. alle Autobahnen sein könnten). Da das Array zwei Dimensionen hat, ist es ein s.g. zweidimensionales Array. Da wir nur mit numerischen Werten (0, 1, 2, 3 ...) hantieren, könnten wir es korrekter Weise als zweidimensionales numerisches Array bezeichnen.
Der Einfachheit halber werden wir im Folgenden jedoch bei der simplen Bezeichnung „Array“ bleiben.

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

Haben Sie nun Probleme, sich dieses Array vorzustellen, bzw. was wir genau in den letzten Ausführungen gemacht haben, so seien Sie nicht beunruhigt: Es ist an sich ganz einfach!

Stellen Sie sich vor, sie würden alle für Sie passierbaren Wege von Berlin nach Bremen auf der Landkarte markieren! Sie nehmen einen dicken, roten Stift, und markieren alle Autobahnen.

Genau das tun wir! Wir weisen allen Punkten, die auf der Landkarte Autobahnen darstellen, den Wert 0 – für begehbar – zu. Alle anderen Punkte markieren wir mit 1 als blockiert; z.B., weil wir nicht durch Stadtzentren fahren möchten, weil die Punkte auf Wasser liegen, oder warum auch immer.

Würde man dieses Array komplett durchlaufen, und den Wert jedes Punktes – 0 oder 1 – auf eine das Array repräsentierende Graphik
abbilden – weiß für 0 und schwarz für 1 –, so ergäbe sich nun folgendes Bild:

Anhand dieser Werte kann sich der Algorithmus nun unserer Aufgabe annehmen. Er startet beim Zielpunkt, wo er sich auf weißer – heißt: passierbarer – Fläche befindet. Nun sucht er sich ringsum die ihm naheliegendsten Punkte und prüft, ob diese weiß – also passierbar – oder aber schwarz – also blockiert – sind. Ist ein solcher Punkt schwarz, scheidet er als potentieller Wegpunkt für unseren kürzesten Weg aus. Ist er hingegen weiß, so merkt sich der Algorithmus den Punkt und bei ihm Punkt erneut seine Prüfroutinen an, sobald er alle weiteren anliegenden Punkte des Ausgangspunktes ebenfalls geprüft hat; ermittelt dann also wiederum, ob die umliegenden Punkte weiß oder schwarz sind. Dies führt er so lange fort, bis er auf den Zielpunkt trifft. Dann hat er den kürzesten Weg unzweifelhaft ermittelt, denn ein potentiell Kürzerer wäre ja vorher gefunden worden. Da dies aber nicht der Fall war, kann der Algorithmus mit 100%iger Gewissheit bestimmen, dass er den kürzesten Weg gefunden hat.
Visuell würde es so aussehen, als würde der Algorithmus schlichtweg die weißen Pfade abarbeiten, bis er auf das Ziel stößt. Tatsächlich tut der Algorithmus genau dies, doch für ihn gibt es kein „weiß“ oder „schwarz“, was ja nur eine Verdeutlichung zum Nachvollziehen für Sie als Leser sein soll. Der Algorithmus folgt einem Weg aus 0en. Stößt er auf eine 1, so ist sein Weg in diese Richtung beendet, stößt er auf eine 0, so setzt er ihn in die Richtung fort. So gelangt er sicher zum Ziel, und somit ist der Weg, den er findet, garantiert der Kürzeste. Schön, nicht?

Zusammenfassende Beschreibung des Dijkstra-Algorithmus

Alle unsere Erkenntnisse vereinend können wir nun den Dijkstra-Algorithmus ausformulieren. Dies ist letztlich reine Wiederholung, soll der Vollständigkeit halber jedoch nicht fehlen:

Ermitteln des Startpunktes.
Ermitteln der Punkte, die am Punkt anliegen.
Prüfe nacheinander jeden der anliegenden Punkte, der noch nie zuvor betreten wurde, ob er 0 (begehbar) oder 1 (blockiert) ist.
Merken derjenigen der anliegenden Punkte, die 0 (begehbar) sind.
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!

Zudem muss der Algorithmus nach jedem weiteren Schritt den bis dahin zurückgelegten Weg speichern; denn sonst ist er zwar irgendwann am Zielpunkt angelangt, kennt aber den eigentlich zurückgelegten Weg nicht. Dafür kann z.B. eine stapelähnliche Struktur (s.g. "Stack") verwendet werden, welche, sobald der Algorithmus den Zielpunkt erreicht hat, nur noch rückwärts ausgelesen werden muss. Das heißt im konkreten Fall eines Stacks, dass als erstes der zuletzt eingefügte Wert ausgelesen wird, dann der als Vorletzter eingefügte usw. usf., bis als letzter Wert derjenige ausgelesen wird, der als erstes eingefügt wurde.
Stellen Sie sich dies ganz wörtlich so vor, wie es die Bezeichnung „Stack“ verheißt: Sie legen zehn Handtücher auf einen Stapel. Nun nehmen Sie sie allesamt wieder von dem Stapel herunter.

Das Handtuch, das Sie als Letztes auf den Stapel gaben, werden Sie als erstes herunter nehmen.
Das Handtuch, das Sie als Vorletztes auf den Stapel gaben, werden Sie als zweites herunter nehmen, usw. usf.
Das Handtuch, das Sie als Erstes auf den Stapel gaben, als dieser also noch leer war, werden Sie entsprechend als letztes vom Stapel nehmen, worauf hin dieser wieder leer sein wird.

Auch muss der Algorithmus eine Liste bereits abgearbeiteter Punkte führen und diese bei Punkt drei der am Beginn dieses Kapitels aufgeführten Liste vollständig ignorieren, denn sonst kann er einerseits theoretisch in einer Endlosschleife verenden. Auf jeden Fall aber würde er redundanterweise Punkte weiter überprüfen und beschreiten, die er vielleicht schon zahlreiche Male zuvor überprüfte. Schlimmer noch: Dadurch wäre auch nicht mehr gewährleistet, dass der gefundene Weg der kürzeste ist.
Dieses „Protokollführen“ kann auch anders herum fungieren: Alle Punkte werden zunächst in eine Liste noch abzuarbeitender Punkte eingetragen, aus der dann nach und nach alle die Punkte entfernt werden, die bereits abgearbeitet wurden.

In der Praxis wird meist einfach jede passierbare Koordinate mit einer Eigenschaft versehen, die angibt, ob der Punkt bereits besucht wurde oder nicht: Jede begehbare Koordinate wird mit einer Ausrichtung versehen, also einem Wert, der die Richtung angibt, aus welcher der Algorithmus die Koordinate erreicht hat. Dies ist in sofern sinnvoll, als dass der Algorithmus, wenn er am Zielpunkt angekommen ist, nur noch die Ausrichtung des Punktes, von dem aus er den Zielpunkt erreichte, überprüfen muss. Dessen Ausrichtung nämlich gibt ihm wiederum den Punkt an, den der Algorithmus als vorletzten vor dem Zielpunkt erreicht hatte, usw. usf. So ist es dem Algorithmus ein Leichtes, den Weg vom Zielpunkt zum Startpunkt zurück zu verfolgen.
Auch hat er somit einen Anhaltspunkt, welche Punkte er nicht mehr überprüfen muss: Ist ein Punkt als 1 markiert, so ist er unpassierbar und wird als blockiert betrachtet. Hat ein mit 0 markierter Punkt nun jedoch eine Orientierung gesetzt, so weiß der Algorithmus, dass dieser Punkt zwar begehbar ist, jedoch bereits abgearbeitet wurde und somit ebenfalls als blockiert angesehen werden muss.
Der Algorithmus hat nun eine einfache aber effektive Möglichkeit, zu verhindern, bereits geprüfte Wegpunkte noch einmal abzuarbeiten und ihm eröffnet sich somit ebenfalls eine ganz simple Möglichkeit, seinen Weg - wenn er am Ziel angekommen ist - zurück verfolgen zu können!

Anwendungsabhängig könnte man den Dijkstra-Algorithmus noch um eine Kostenfunktion erweitern. In einem Flugplan hat beispielsweise jede Reise von einer Stadt in eine andere einen anderen Preis. Nun könnte der Algorithmus abwägen, welcher Weg der günstigste ist, und diesen vor dem teureren überprüfen. Dies kann einerseits angewandt werden, um die Laufzeit des Algorithmus zu verringern, andererseits jedoch auch, um z.B. nicht den kürzesten sondern einfach allgemein den geeignetsten Weg zu finden.

Theoretisch könnten Sie nun aufhören, diese Abhandlung zu lesen, denn viel mehr gibt das Thema „Dijkstra-Algorithmus“ in der blanken Theorie gar nicht her. Da es jedoch etwas ernüchternd erscheinen würde, an dieser Stelle bereits Schluss zu machen, habe ich mich entschlossen, noch ein wenig tiefer in die Materie einzusteigen, und auch, einige kleine Fallen zu besprechen.

Eine quadratförmige Suche?

Wenn Sie nun einmal versuchen, sich vorzustellen, wie die Suche des Algorithmus optisch verläuft, werden Sie womöglich bei der Idee eines sich ausdehnenden Quadrates landen: Denn wir haben einen Punkt A. Nun überprüft der Algorithmus alle Punkte, die an A anliegen, auf ihre Begehbarkeit. Dann überprüft der Algorithmus alle Punkte, die an den an A anliegenden Punkten anliegen, auf ihre Begehbarkeit usw. usf.

Graphisch ließe sich dies wie folgt darstellen:

jedes Kästen sei ein Koordinatentupel
gelb: im momentan Quadratbereich auf Begehbarkeit untersuchtes Koordinatentupel
grau: bereits untersuchtes Koordinatentupel
weiß: noch nicht untersuchtes Koordinatentupel

O() = 1:

O() = 9:

O() = 25:

Entsprechend würde sich die Suche immer weiter in Form dieses Quadrates ausdehnen. Nicht begehbare Flächen würden das Quadrat zerstören, aber grundsätzlich würde die abgesuchte Fläche sich weiterhin entsprechend ausbreiten.

Diese Vorstellung führt jedoch eine Problematik mit sich, die wir bisher nicht betrachteten! Würde der Algorithmus tatsächlich so, wie in den Abbildungen gezeigt, agieren, so würde er unter bestimmten Bedingungen (soll heißen: bei bestimmen Graphen) zu einem falschen Ergebnis führen!

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 Lektüre der weiteren Kapitel nochmals die vorherigen durchlesen, insbesondere das vorherige und dieses, bis Sie die Frage beantworten können!

Nun, ich gebe zu, die Frage hatte etwas von einer Fangfrage …
Wir haben bisher immer davon gesprochen, dass der Algorithmus bei einem Punkt „die anliegenden Punkte auf ihre Passierbarkeit prüft“. Dies ist insofern etwas missverständlich, als dass wir nicht eindeutig definierten, was denn die „anliegenden Punkte“ sind! In der gerade gezeigten Visualisierung würde der Algorithmus unter „anliegend“ auch die diagonal zum jeweiligen Punkt stehenden Punkte betrachten (daher ja die Quadratform). Dies würde aber die fatale Auswirkung auf unseren Algorithmus haben, diagonale Schritte zu erlauben! Betrachten wir folgenden Graphen:

Man würde erwarten, dass der gefundene Weg vom Startpunkt aus nach unten verläuft, die schwarze Wand umrundet und anschließend wieder nach oben hin zum Ziel führt. Würde unser Algorithmus nun aber mit der quadratförmigen Suche wie in den vorherigen Graphiken arbeiten (und somit diagonale Schritte erlauben), wäre der gefundene Weg der folgende, unerwartete:

Wir müssen unseren Algorithmus also in sofern einschränken, als dass er

entweder, wenn wir eine quadratförmig verlaufende Suche erlauben (was ja prinzipiell weder unmöglich noch ein Verbrechen ist), neben der Passierbarkeit der horizontal und vertikal anliegenden Punkte eines Punktes X zusätzlich noch bei den diagonal anliegenden Punkten überprüft, ob diese überhaupt aus Sicht von X zugänglich sind, oder
die quadratförmige Suche verbieten, indem wir als „anliegende Punkte“ ausschließlich die horizontal und vertikal den Punk X berührenden Punkte definieren.

Erst wenn wir dies getan haben, liefert uns unser Algorithmus auch bei obigem Graphen einen korrekten Weg! Jedoch unterscheiden sich beide Varianten in ihrem Resultat!

Wenn wir als „anliegende Punkte“ nur die horizontalen und vertikalen Nachbarn eines Punktes definieren, so erhalten wir folgendes Ergebnis:

Legitimieren wir hingegen (erlaubte, also nicht durch diagonal verlaufende Wände hindurch tretende) diagonale Schritte, so sieht unser Ergebnis wie folgt aus:

Hier ist es nun Ermessenssache bzw. es kommt auf den konkreten Anwendungszweck an, ob der Algorithmus korrekte diagonale Schritte durchführen können soll oder nicht. Ein allgemeines Richtig oder Falsch gibt es nicht.

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 die 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, würde immer größer sein als diejenige des Weges ganz unten – Manchmal viel größer, manchmal 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. Solche Heuristiken nennt man „monotone Heuristiken“. Moderne Implementierungen kommen tatsächlich nahe an eine vernachlässigbar niedrige Fehlerkennungsrate heran. Dennoch ist ein solcher Algorithmus nie so zuverlässig wie der Dijkstra-Algorithmus, was in manchen Fällen ein entscheidendes Kriterium sein kann.

Eine wirklich monotone Heuristik, die also niemals falsch läge, müsste den gesamten Weg vom momentanen Punkt zum Zielpunkt abarbeiten. Ferner müsste sie den kürzesten Weg ermitteln und anhand dessen die anliegenden Punkte priorisieren. Dann wäre der Weg zum Zielpunkt aber bereits gefunden, was ja eigentlich das Ziel des Algorithmus sein soll. Es würde also die Heuristik die Aufgabe des Algorithmus übernehmen, um diesem zu ermöglichen, seine Aufgabe durchzuführen, welche ja aber wiederum von der Heuristik abhängt. Somit würde die Heuristik ihrerseits eine Heuristik benötigen, um den Weg zu finden, womit sie keine Heuristik mehr wäre, sondern ein Algorithmus.
Wir sehen: Die Idee einer wirklich monotonen Heuristik führt sich selbst ad absurdum.
Was bliebe wäre eine Heuristik, die intelligent ohne den Weg zum Ziel zu kennen entscheiden könnte, welcher Punkt als nächstes am ehesten zum Ziel führte, und dabei immer richtig läge. Würden wir nun versuchen, eine solche Heuristik zu programmieren, müsste diese Abhandlung vielmehr den Titel „Künstliche Intelligenz“ denn „Wegfindalgorithmen“ tragen.

Moderne Implementationen des A*-Algorithmus arbeiten mit so genannten „zulässigen Heuristiken“, welche (wie so oft in der Informatik) eine Gradwanderung zwischen verlässlichem Arbeiten und dem (Alp-)Traum der perfekten Heuristik darstellt.

Wir stellen also fest:
*

Heuristiken können die Wegfindung ungemein beschleunigen.
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.

Schlussworte

Das ist sie also, die Abhandlung über den Dijkstra-Algorithmus mit einigen weiteren Vertiefungen der Materie und einem Abstecher in die Welt der Heuristiken und damit verbunden des A*-Algorithmus.

Wie Sie nun sehen bleibe ich Ihnen Quellcodeausschnitte in dieser Abhandlung vorläufig schuldig; dies tue ich bewusst, da die Thematik meiner Ansicht nach ohnehin recht komplex ist. Zudem wollte ich mich nicht auf eine Sprache festlegen, um den Artikel so allgemein wie möglich zu halten. Vielleicht folgen diese ja irgendwann in Form einer weiteren Abhandlung …

Ich hoffe, ich konnte Sie während des Lesens auch zum Mitdenken und Vorauserkennen vieler der Umstände anregen! Auch die häufigen Wiederholungen tätigte ich in der Absicht, dass Sie viele Erkenntnisse wirklich selbst erschließen konnten und nicht blank den Text durchlasen.

Vielen Dank für das Lesen meiner Arbeit!
Ich hoffe, sie war Ihnen informativ und auch ein wenig unterhaltsam!

GPC

Wow, der ist aber umfangreich
Wusste gar nicht, dass du was in Planung hast
Anyways,

(Zum Lesen hab' ich grad keine Zeit, wird aber definitiv vorgemerkt)

Reyx

http://www.c-plusplus.net/forum/viewtopic-var-t-is-173051.html

GPC

Oha, mein Gedächtnis hat definitv die Form eines Siebs

Jester

Der Artikel sieht echt gut aus. Sehr umfangreich und sehr anschaulich. Muß ich mir demnächst mal im Detail anschaun. Aber eines ist mir direkt ins Auge gestochen:

Reyx schrieb:

[list][*]Einerseits betrachtet der Informatiker die Effizienz eines Algorithmus, gemessen an der s.g. O(n)-Laufzeit, welche die Anzahl der benötigten Operationen innerhalb des Algorithmus angibt. Unter der Optimierung eines Algorithmus versteht man das Reduzieren dieser O(n)-Laufzeit und somit die Steigerung der Effizienz der Berechnungen.

Beispiel: Sie haben einen Algorithmus, der in 100 Rechenschritten von jedem beliebigen Punkt der Erde die Distanz zu einem anderen ermittelt. Er hat somit eine Laufzeit von O(n) = 100. Wenn Sie die Laufzeit verringern, so dass er Algorithmus den Weg schon nach z.B. 90 Rechenschritten ermittelt und seine Laufzeit somit fortan O(n) = 90 beträgt, so haben Sie den Algorithmus optimiert.

Das geht garnicht. Wenn schon O-Kalkül, dann richtig. Wenn Du lieber mit echten Zahlen Beispiele machen willst, dann zähl die Anzahl der Rechenschritte (und nenne die dann zum Beispiel T(n)) oder ähnliches, aber O(n) = 90/100/sonstwas ist unsinnig.

Reyx

Was hälst du von folgender Formulierung?

Einerseits betrachtet der Informatiker die Effizienz eines Algorithmus, zumeist gemessen an der s.g. O(n)-Laufzeit, welche die Anzahl der benötigten Operationen innerhalb des Algorithmus angibt. Unter der Optimierung eines Algorithmus versteht man das Reduzieren dieser O(n)-Laufzeit und somit die Steigerung der Effizienz der Berechnungen.

Beispiel: Sie haben einen Algorithmus, der in 100 Rechenschritten von jedem beliebigen Punkt der Erde die Distanz zu einem anderen ermittelt. Er hat somit eine Laufzeit von 100 Rechenschritten. Wenn Sie die Laufzeit verringern, so dass er Algorithmus den Weg schon nach z.B. 90 Rechenschritten ermittelt, so haben Sie den Algorithmus optimiert.

Jester

Hm, auf jeden Fall besser. Es heißt aber nicht O(n)-Laufzeit, eher Laufzeit im O-Kalkül. Aber die misst ja nur die asymptotische Laufzeit... und die zu verbessern würde ich nicht unbedingt als typische Optimierung bezeichnen. Das ist dann eher Algorithmenkonstruktion. Im O-Kalkül verzichtet man ja auf Konstante Faktoren und sowas. Das Tuning der Implementierung eines Algorithmus so dass diese Konstanten klein sind würde ich als Optimierung bezeichnen.

Letztlich wirds nie ganz korrekt sein, wenn Du mit konkreten Zahlen ein Beispiel zur Asymptotik machen willst. Ist halt die Frage, ob Du Dir die Erklärung des O-Kalkül auch noch aufhalsen willst...

Ich denk noch ein bißchen drüber nach. Es gibt sicher ne einfache und gute Lösung. Jetzt muß ich aber wirklich los.

Reyx

Okay, dann ein Versuch ganz ohne O-Kalkül:

Einerseits betrachtet der Informatiker die Effizienz eines Algorithmus, z.B. gemessen an der seiner Laufzeit T(n), welche die Anzahl der benötigten Operationen innerhalb des Algorithmus angibt. Unter der Optimierung eines Algorithmus kann man u.a. das Reduzieren seiner Laufzeit und somit die Steigerung der Effizienz der Berechnungen verstehen.

Beispiel: Sie haben einen Algorithmus, der in 100 Rechenschritten von jedem beliebigen Punkt der Erde die Distanz zu einem anderen ermittelt. Er hat somit eine Laufzeit von T(n) = 100. Wenn Sie die Laufzeit verringern, so dass der Algorithmus den Weg schon nach z.B. 90 Rechenschritten ermittelt, so haben Sie die Laufzeit auf T(n) = 90 reduziert und den den Algorithmus somit optimiert.

Das ist jetzt so, denke ich, relativ unverfänglich, oder?

Jester

Ja, das liest sich gut. So klappt auch das Beispiel prima!

Reyx

1. Einige inhaltliche Fehler korrigiert
2. Einige Rechtschreibfehler korrigiert
3. Einige weitere Ergänzungen vorgenommen
4. Design strikter an die Magazinvorgabe angepasst

Der Weg ist das Ziel!

Automatisierte Wegfindung mit Hilfe des Dijkstra- und A*-Algorithmus

Theoretische Abhandlung für Neulinge auf dem Gebiet des Pathfinding

Reyx schrieb:

Wie schon gesagt ist der Artikel ausschließlich theoretischer Natur.

Zudem ist er extrem ausführlich und soll den absoluten Neuling im Gebiet des Pathfinding zum Denken anregen; er soll die Fragen "für sich selbst beantworten", bevor der Text ihm die Lösung präsentiert.

Entsprechend werden ihn alle etwas fortgeschritteneren Leser sehr langatmig und wenig anspruchsvoll. Sei's drum - Auf für Anfänger will mal ein Artikel geschrieben sein :p

Den Titel des Artikels habe ich bewusst gewählt, da er eben theoretischer Natur ist. Daher wäre der Name "Pathfinding mit Dijkstra" o.ä. imho falsch gewählt; es geht hier wirklich hauptsächlich darum, den Leser zum eigenen Nachdenken, eigenen erwägen der Pro- und Contras und der Herangehensweise anzuregen. Der Artikel will keine Anleitung sein, wie man einen Pathfinder implementiert.

Einleitung

Wegfindung ist ein komplexes Themengebiet der Informatik, welches sowohl auf unsere Gesellschaft, unsere Wirtschaft als auch auf unsere Freizeitaktivitäten einen häufig unterschätzten Einfluss ausübt. Doch was darf man sich konkret unter einer „Wegfindung“ vorstellen?
Ganz allgemein betrachtet wollen wir an dieser Stelle vorweg definieren:

Eine Wegfindung ist das Ermitteln eines passierbaren Weges von einem Punkt A auf einem beliebigen Graphen zu einem Punkt B. Man spricht hierbei auch von „Pathfinding“.
Ein Wegfindalgorithmus ist diejenige Handlungsvorschrift, die beschreibt, wie eben diese Ermittlung durchgeführt wird. Auf Grund des starken Einflusses des Englischen auf die moderne Informatik, wird hier auch häufig vom „Pathfinding-Algorithmus“ gesprochen, eine Verknüpfung des Deutschen mit dem Englischen, wie sie zunehmend Akzeptanz findet.

Im Allgemeinen stellt man an einen solchen Algorithmus den Anspruch, nicht nur den Weg vom Start- zum Zielpunkt zu finden, sondern man erwartet auch noch, dass der gefundene Weg der kürztmögliche ist.

*Als Beispiel:

Eine Wegfindung wäre es, wenn Sie von Berlin nach Bremen reisen wollten.
Der Wegfindalgorithmus wäre die abstrakte (= auf andere Städte 1:1 übernehmbare) Beschreibung dessen, was Sie tun müssten, um diesen Weg zu ermitteln (z.B. Landkarte aufschlagen, Routen durchgehen, Umleitungen evaluieren etc., Strecken messen).

Über Algorithmen

Womit wir uns in dieser Abhandlung beschäftigen werden, ist hauptsächlich – aber nicht ausschließlich – der in der Einleitung letztgenannte Punkt: Der Algorithmus! Es gibt zahlreiche Wegfindalgorithmen, welche sich in diversen Faktoren unterscheiden. Generell gibt es jedoch zwei Kritikpunkte, die einen Algorithmus ausmachen:

Einerseits betrachtet der Informatiker die Effizienz eines Algorithmus, z.B. gemessen an der seiner Laufzeit T(n), welche die Anzahl der benötigten Operationen innerhalb des Algorithmus angibt. Unter der Optimierung eines Algorithmus kann man u.a. das Reduzieren seiner Laufzeit und somit die Steigerung der Effizienz der Berechnungen verstehen.
Beispiel: Sie haben einen Algorithmus, der in 100 Rechenschritten von jedem beliebigen Punkt der Erde die Distanz zu einem anderen ermittelt. Er hat somit eine Laufzeit von T(n) = 100. Wenn Sie die Laufzeit verringern, so dass der Algorithmus den Weg schon nach z.B. 90 Rechenschritten ermittelt, so haben Sie die Laufzeit auf T(n) = 90 reduziert und den den Algorithmus somit optimiert.
Andererseits ist natürlich auch die Zuverlässigkeit von kritischer Bedeutung:
Findet der Algorithmus tatsächlich den kürzesten passierbaren Weg?
Welche Hindernisse in Form von unpassierbaren Stellen berücksichtigt er dabei?
Ist er in der Lage, zu erkennen, wenn es keinen Weg von Punkt A nach Punkt B gibt?
Bleiben seine Berechnung verlässlich, wenn er mit Zahlen rechnen muss, die gegen 0 streben?
Bleiben seine Berechnung verlässlich, wenn er mit Zahlen rechnen muss, die gegen ∞ streben?
Verfügt der Algorithmus über Lücken in seinen Definitions- oder Wertebereichen, die ihn zu ungewöhnlichem Verhalten bringen könnten (z.B. Divisionen durch Null, Buffer Overflows o.ä.)?

Wegfindalgorithmen im realen Leben

Wo begegnen uns solche Wegfindalgorithmen im realen Leben?

Stellen Sie sich z.B. vor, sie hätten eine Landkarte vor sich liegen und wollten (wieder einmal) von Berlin nach Bremen reisen. Die Kenntnis des direktesten Weges – der Luftlinie – ist für sie als Kraftwagenfahrer erfahrungsgemäß von nicht gar so großem Nutzen. Hingegen sehen Sie sich zahlreichen Zwischenstationen in Form von u.a. Städten und Autobahnrouten gegenüber, die es „abzuklappern“ gilt:

Fahren Sie über Schwerin und Hamburg?
Oder ist vielleicht doch der Weg durch Sachsen-Anhalt, also über Magdeburg und Hannover, der Kürzere?

Sie könnten nun mühselig die einzelnen Strecken auf der Karte abmessen und würden somit herausfinden, welche Route (rein streckenmäßig - Dinge wie Geschwindigkeitseinschränkungen und Umleitungen außer Acht gelassen) die Kürzeste ist. Dies unterliegt jedoch den Schwankungen Ihres Vermessungstalentes, ihrer Kopfrechenkompetenz und nicht zuletzt ist es eine einmalige Aktion: Sollten Sie sich umentscheiden, so dass nicht Bremen sondern vielleicht Stuttgart das Ziel sein soll, so beginnt der ganze Spaß von Neuem.

In einer solchen Situation ist ein Wegfindalgorithmus eine äußerst praktische Sache (abgesehen davon, dass ich grundsätzlich die zweite Route vorziehen würde – Magdeburg, weil es eine sehr schöne Stadt ist, und Hannover wegen der Cebit …).

Stellen Sie sich weiter vor, Sie seien Vorsitzender der Versandabteilung einer Speditionsgesellschaft. Sie können sich nun gewiss vorstellen, dass es für Sie von allerhöchstem Interesse ist, auf jeder Transportfahrt immer den wirklich absolut kürzesten Weg zu nehmen! Müssten Sie in dieser Branche jeden Weg manuell erwägen, würden Sie mehr Zeit beim Rechnen als beim Ausliefern der sehnlichst erwarteten Ware verbringen!

Auch im militärischen Sinne finden Wegfindalgorithmen (leider!) Verwendung, z.B. bei zielsuchenden Projektilen. Wenn diese ein bewegliches Ziel verfolgen, errechnet ein Wegfindalgorithmus in einem bestimmten Zeitintervall immer wieder den kürzesten Weg zum Zielobjekt, so dass das Geschoss seine Flugbahn entsprechend anpassen kann (wofür wiederum eine andere Gattung von Algorithmen zuständig ist, aber dies nur am Rande …).

Als letztes Beispiel seien die guten alten Computerspiele genannt:
Was wäre wohl das wohlüberlegteste Spiel, würden die anderen Charaktere (s.g. NPCs – Non Playable Characters) einfach wirr in der Gegend herum laufen? In der Praxis tun sie dies nicht – Vielmehr verfolgen sie den Hauptcharakter oder fliehen womöglich vor ihm. Was sie auch tun, ihre Bewegungen beziehen sich zumeist auf die Position des gespielten Charakters. Auch hier werkelt im Hintergrund tüchtig ein Wegfindalgorithmus.

Was ist der Dijkstra-Algorithmus?

Einer der grundlegenden weil primitivsten Wegfindalgorithmen in der Informatik ist der s.g. Dijkstra-Algorithmus (ˈdɛɪkˌstra). Er ist relativ einfach zu implementieren (= in einer Programmiersprache zu formulieren) und zeichnet sich insbesondere dadurch aus, dass er garantiert als einzigen potentiellen Weg den kürztmöglichen findet, unabhängig davon, wie viele andere (längere) Wege es noch gibt.

Sie können folglich davon ausgehen, dass der vom Dijkstra-Algorithmus errechnete Weg mit einer Wahrscheinlichkeit von exakt 100% der Kürzeste ist, den es gibt. Das ist nicht schlecht und meist wesentlich verlässlicher, als andere Wegfindalgorithmen!

Hingegen arbeitet er jedoch nicht wirklich performant (= schnell), wie wir noch sehen werden.

Sie können davon ausgehen, dass die Laufzeit des Dijkstra-Algorithmus oft über der Laufzeit anderer Wegfindalgorithmen liegt.
Er bietet mithin eine ausgewogene Gewichtsverteilung der Kriterien Effizienz und Zuverlässigkeit.

Voraussetzungen eines Wegfindalgorithmus'

Bevor wir nun beginnen, uns mit dem Eingemachten des Dijkstra-Algorithmus zu beschäftigen, führen wir zunächst einige Gedankengänge durch. Was braucht ein Algorithmus alles, um von einem Punkt zum Anderen zu kommen? Na, da haben wir doch schon gleich ganz intuitiv und wahrscheinlich unbewusst zwei Voraussetzungen genannt!

*Wir stellen fest:

Voraussetzung: Ein Startpunkt (im Folgenden P[S] genannt – Der Punkt mit den Indizes des Startpunktes).
Voraussetzung: Ein Zielpunkt (im Folgenden P[Z] genannt – Der Punkt mit den Indizes des Zielpunktes).

Sie mögen sich nun fragen, woher auf einmal der Begriff „Index“ (Plural: Indizes) kommt. Nun, genau daraus ergibt sich unsere
*

3. Voraussetzung: Ein Graph, auf welchem sowohl P[S] und P[Z] liegen, und auf dem der Algorithmus den kürzesten Weg finden soll.

Was wir uns unter diesem Graphen vorstellen dürfen?
Betrachten wir erneut unser Berlin->Bremen-Beispiel:

Die Landkarte ist unser Graph.
P[S] ist der Punkt auf dem Graphen, an dem wir starten. Dieser hat auf der Landkarte ein zweidimensionales Koordinatentupel (= ein Koordinatenpaar), das eineindeutig die Position des Punktes beschreibt. Dieses ist mit seinen „Indizes“ gemeint. Im Beispiel könnte der Punkt P[S] das Stadtzentrum von Berlin sein.
P[Z] ist der Punkt auf dem Graphen, zu dem wir gelangen möchten. Auch dieser verfügt über ein entsprechendes Koordinatentupel, mithin seine Indizes. Im Beispiel könnte der Punkt P[S] das Stadtzentrum von Bremen sein.

Wir stellen weiterhin fest:

Jeder beliebige Punkt auf dem Graphen verfügt über ein Koordinatentupel, das seine Position auf dem Graphen eineindeutig beschreibt. Stellen Sie sich diese Indizes wie die Achsenwerte in einem Koordinatensystem vor. Genau genommen sind sie exakt dies, nur dass ein Koordinatensystem i.d.R. auf zwei bzw. maximal drei Dimensionen beschränkt ist, ein Algorithmus hingegen mit theoretisch beliebig vielen Dimensionen rechnen kann.
Tatsächlich besitzt jeder Punkt genau so viele Indizes, wie der Graph über Achsen verfügt.
Bei unserer zweidimensionalen Landkarte verfügen Start- und Zielpunkt folglich über je 2 Indizes: Einen Index für die x-Koordinate, einen für die y-Koordinate.
Würden wir nun noch die Lufthöhe in unsere Landkarte übernehmen, so würde jeder Punkt zusätzlich über eine dritte Koordinate verfügen, nämlich die für die Z-Achse.

Der Einfachheit halber werden wir in dieser Abhandlung jedoch im zweidimensionalen Raum bleiben.

Das Prinzip des Dijkstra-Algorithmus

Übertragen wir nun unsere Erkenntnisse auf unser Vorhaben, die kürzeste Strecke von Berlin nach Bremen zu ermitteln. 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. Nun können wir die Position des Startpunktes, P[S](5; 3), ebenso angeben, wie die des Zielpunktes, P[Z](1; 2).

Betrachten wir nun unsere Karte, so erkennen wir:
*

Zwischen dem Start- und dem Zielpunkt liegen n weitere Punkte, von denen ebenfalls ein jeder mit einem Koordinatentupel eineindeutig beschrieben werden kann.

Diese Erkenntnis ist nicht neu, wir erfuhren sie bereits im letzten Abschnitt. Doch denken wir etwas genauer darüber nach, so stellen wir fest, das dies eine ganz wichtige Eigenschaft unserer Karte ist!
Aus ihr erkennen wir nämlich schon, was der Algorithmus letztlich tun muss, um uns den kürzesten Weg vom Start- zum Zielpunkt zu ermitteln:
*

Er muss sämtliche Punkte zwischen P[S] und P[Z] abarbeiten, bis er am Ziel angekommen ist.

Dies alleine reicht aber noch nicht, um unseren Algorithmus vernünftig arbeiten zu lassen. Warum? Nun, er verfügt über einen Startpunkt, einen Zielpunkt und einen Graphen. Das ist alles. Würden wir nun so den Algorithmus implementieren, würde er uns schlichtweg ein sehr ernüchterndes Resultat liefern – Nämlich die direkte Luftlinie!
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 Lektüre der weiteren Kapitel nochmals die vorherigen durchlesen, insbesondere das vorherige und dieses, bis Sie die Frage beantworten können!

Man muss halt differenzieren [e]hellip[/e]

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 (wobei man anmerken muss: Falls ja, Hut ab, Herr Schrödinger! Meine Katze wurde nicht so alt!). Um nämlich den kürzesten Weg zu ermitteln, muss der Algorithmus natürlich wissen, welche Wege für ihn tabu sind!

Wir können allgemein formulieren:
*

Beim Abarbeiten der Punkte auf dem Graphen muss der Algorithmus diejenigen Punkte unberücksichtigt lassen, die als nicht passierbar gelten.

Oder wie würden Sie es finden, wenn Ihr Navigationsgerät Sie während Ihrer Autofahrt geradewegs durch einen Fluss fahren lassen wollte (was in der Vergangenheit wohlgemerkt tatsächlich geschehen ist)?

Wie kann der Algorithmus nun aber entscheiden, welche Wege passierbar sind? Würden wir ihm nämlich tatsächlich einfach nur unsere Landkarte mitteilen, ohne ihn mit dieser so wichtigen Information auszustatten, so würde zwangsläufig eine der folgenden Situation eintreten:

Möglichkeit: Der Algorithmus nimmt an, dass alle Koordinaten passierbar sind. Was wäre das Ergebnis der Berechnung? Richtig! Die Luftlinie, wie wir schon im letzten Abschnitt feststellten. Denn wenn alle Wege passierbar sind, dann ist die Luftlinie natürlich zweifelsohne der direkteste wie kürzeste Weg zum Ziel.
Möglichkeit: Der Algorithmus nimmt an, dass alle Koordinaten nicht passierbar sind. In diesem Falle würde er das Ziel niemals erreichen und uns als Ergebnis (subjektiv korrekterweise) liefern, es gäbe keine beschreitbare Verbindung zwischen Start- und Zielpunkt.

Wir müssen unseren Graphen also irgendwie mit der Information ausstatten, welche Wege passierbar sind.
Betrachten wir unsere Karte, stellen wir fest, dass diese Information in ihr eigentlich enthalten ist.
Viel schlimmer jedoch: Wir erkennen dass unsere Landkarte äußerst redundante (=verschwenderische) Informationen enthält! Der Algorithmus muss nicht wissen, wo Autobahnen verlaufen! Er muss nicht wissen, wo Seen und Meere liegen! Und ebenso ist es im schnurzegal, wo welche Städte liegen! Er braucht wirklich nicht mehr zu wissen, als:

Punkt A ist passierbar.
Punkt B ist nicht passierbar.
Punkt C ist nicht passierbar.
Punkt D ist wiederum passierbar.
Usw. usf.

Der logische Schluss, den wir daraus ziehen?
Ganz klar! - Dass wir alle diese Informationen, die wir absolut nicht benötigen, aus dem Graphen entfernen!

Von Feldern, Nullen und Einsen! Oder auch Arrays [e]hellip[/e]

Wenn wir unseren Graphen auf das absolut Notwendigste reduzieren, dann enthält er zu jedem beliebigem (wir erinnern uns: eineindeutigem!) Koordinatentupel nur noch eine einzige Information:

Ist der Punkt passierbar?
Oder ist er es nicht?

In der Informatik differenziert man zwischen den Zuständen "Strom" und "kein Strom", bzw. in den modernen Hochsprachen lieber zwischen "wahr" (1, true) und "falsch" (0, false). Jedes Koordinatenpaar wird also auf exakt diese Information reduziert: Ob der Punkt passierbar ist, in dem Fall weisen wir dem Tupel eine 0 (da nicht blockiert) zu, oder ob er blockiert ist, in dem Fall weisen wir dem Tupel eine 1 (da eben blockiert) zu. Hier tangieren wir die s.g. Bool’sche Algebra …

Das, was wir erhalten, ist eine Datenstruktur, welche uns auf binäre (= 1 oder 0, wahr oder falsch, engl. "true" oder "false") Art und Weise das angibt, womit unser Algorithmus arbeiten kann! Für jedes beliebige Koordinatenpaar besitzt unser Graph nur noch einen von zwei Werten:

0 besagt, dass der Punkt am speziellen Koordinatenpaar passierbar ist.
1 besagt, dass der Punkt am speziellen Koordinatenpaar unpassierbar ist.

An dieser Stelle sei natürlich angemerkt, dass die Festlegung 0 = passierbar und 1 = unpassierbar reine Definitionssache ist. Wir könnten es z.B. auch anders herum definieren, wenn wir wollten.

Diese doppelten und dreifachen Ausführungen mögen Ihnen übertrieben erscheinen, aber es soll wirklich klar werden, wie wir diese Eigenschaften für unseren Algorithmus gewinnbringend (= uns dem Ziel näherbringend) verwenden können!

Unseren Algorithmus können wir anweisen:

Wenn P(0; 0) = 0, dann gehe weiter, wenn = 1, dann bleibe stehen.
Wenn P(0; 1) = 0, dann gehe weiter, wenn = 1, dann bleibe stehen.
Wenn P(1; 0) = 0, dann gehe weiter, wenn = 1, dann bleibe stehen.
Wenn P(1; 1) = 0, dann gehe weiter, wenn = 1, dann bleibe stehen.
Usw. usf.

Oder ganz allgemein:
*

Wenn P(x; y) = 0, dann gehe weiter, wenn = 1, dann bleibe stehen.

Hierbei bedeute "weiter gehen", dass der Punkt so vorgemerkt wird, dass der Algorithmus auch seine Nachbarn auf Passierbarkeit überprüfen wird, sobald er mit der Überprüfung der Nachbarspunkte des Ausgangspunktes fertig ist. "Bleibe stehen" sei ein Vormerken als "nicht passierbar": Der Punkt kann nicht begangen werden, scheidet somit als möglicher Wegpunkt unseres gesuchtes Weges aus. Da ein solches Vormerken als "nicht passierbar" jedoch bereits durch den Punkt selbst gegeben ist (er ist ja durch 1 als blockiert markiert), muss sich der Algorithmus um den Punkt gar nicht weiter kümmern.

Dies ist eine Instruktion (= Anweisung), mit der unser Algorithmus umgehen kann.

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“). Sie ist letztlich die digitale Repräsentation unseres Graphen, reduziert auf das Allerallernötigste. Ihre besondere Eigenschaft, die es dem Algorithmus ermöglicht, mit ihr zu arbeiten, ist, dass der Algorithmus nur zwei Werte kennen muss – nämlich die x- sowie die y-Koordinate –, um aus der Struktur abzulesen, ob der entsprechende Punkt begehbar ist oder nicht. Ist er das, setzt der Algorithmus seine Arbeit fort.
Ist er hingegen nicht passierbar, so braucht sich der Algorithmus in seiner Wegsuche nicht weiter um den Punkt kümmern. Denn ein Punkt, der nicht passierbar ist, kann logischerweise niemals ein Wegpunkt unseres gesuchten kürzesten Weges sein!
Wir haben also unseren Graphen in ein Array verpackt, das direkt unsere zweidimensionale Landkarte repräsentiert, reduziert auf die Wege, die wir begehen können (was in der Praxis z.B. alle Autobahnen sein könnten). Da das Array zwei Dimensionen hat, ist es ein s.g. zweidimensionales Array. Da wir nur mit numerischen Werten (0, 1, 2, 3 ...) hantieren, könnten wir es korrekter Weise als zweidimensionales numerisches Array bezeichnen.
Der Einfachheit halber werden wir im Folgenden jedoch bei der simplen Bezeichnung „Array“ bleiben.

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

Haben Sie nun Probleme, sich dieses Array vorzustellen, bzw. was wir genau in den letzten Ausführungen gemacht haben, so seien Sie nicht beunruhigt: Es ist an sich ganz einfach!

Stellen Sie sich vor, sie würden alle für Sie passierbaren Wege von Berlin nach Bremen auf der Landkarte markieren! Sie nehmen einen dicken, roten Stift, und markieren alle Autobahnen.

Genau das tun wir! Wir weisen allen Punkten, die auf der Landkarte Autobahnen darstellen, den Wert 0 – für begehbar – zu. Alle anderen Punkte markieren wir mit 1 als blockiert; z.B., weil wir nicht durch Stadtzentren fahren möchten, weil die Punkte auf Wasser liegen, oder warum auch immer.

Würde man dieses Array komplett durchlaufen, und den Wert jedes Punktes – 0 oder 1 – auf eine das Array repräsentierende Graphik
abbilden – weiß für 0 und schwarz für 1 –, so ergäbe sich nun folgendes Bild:

Anhand dieser Werte kann sich der Algorithmus nun unserer Aufgabe annehmen. Er startet beim Zielpunkt, wo er sich auf weißer – heißt: passierbarer – Fläche befindet. Nun sucht er sich ringsum die ihm naheliegendsten Punkte und prüft, ob diese weiß – also passierbar – oder aber schwarz – also blockiert – sind. Ist ein solcher Punkt schwarz, scheidet er als potentieller Wegpunkt für unseren kürzesten Weg aus. Ist er hingegen weiß, so merkt sich der Algorithmus den Punkt und bei ihm Punkt erneut seine Prüfroutinen an, sobald er alle weiteren anliegenden Punkte des Ausgangspunktes ebenfalls geprüft hat; ermittelt dann also wiederum, ob die umliegenden Punkte weiß oder schwarz sind. Dies führt er so lange fort, bis er auf den Zielpunkt trifft. Dann hat er den kürzesten Weg unzweifelhaft ermittelt, denn ein potentiell Kürzerer wäre ja vorher gefunden worden. Da dies aber nicht der Fall war, kann der Algorithmus mit 100%iger Gewissheit bestimmen, dass er den kürzesten Weg gefunden hat.
Visuell würde es so aussehen, als würde der Algorithmus schlichtweg die weißen Pfade abarbeiten, bis er auf das Ziel stößt. Tatsächlich tut der Algorithmus genau dies, doch für ihn gibt es kein „weiß“ oder „schwarz“, was ja nur eine Verdeutlichung zum Nachvollziehen für Sie als Leser sein soll. Der Algorithmus folgt einem Weg aus 0en. Stößt er auf eine 1, so ist sein Weg in diese Richtung beendet, stößt er auf eine 0, so setzt er ihn in die Richtung fort. So gelangt er sicher zum Ziel, und somit ist der Weg, den er findet, garantiert der Kürzeste. Schön, nicht?

Zusammenfassende Beschreibung des Dijkstra-Algorithmus

Alle unsere Erkenntnisse vereinend können wir nun den Dijkstra-Algorithmus ausformulieren. Dies ist letztlich reine Wiederholung, soll der Vollständigkeit halber jedoch nicht fehlen:

Ermitteln des Startpunktes.
Ermitteln der Punkte, die am Punkt anliegen.
Prüfe nacheinander jeden der anliegenden Punkte, der noch nie zuvor betreten wurde, ob er 0 (begehbar) oder 1 (blockiert) ist.
Merken derjenigen der anliegenden Punkte, die 0 (begehbar) sind.
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!

Zudem muss der Algorithmus nach jedem weiteren Schritt den bis dahin zurückgelegten Weg speichern; denn sonst ist er zwar irgendwann am Zielpunkt angelangt, kennt aber den eigentlich zurückgelegten Weg nicht. Dafür kann z.B. eine stapelähnliche Struktur (s.g. "Stack") verwendet werden, welche, sobald der Algorithmus den Zielpunkt erreicht hat, nur noch rückwärts ausgelesen werden muss. Das heißt im konkreten Fall eines Stacks, dass als erstes der zuletzt eingefügte Wert ausgelesen wird, dann der als Vorletzter eingefügte usw. usf., bis als letzter Wert derjenige ausgelesen wird, der als erstes eingefügt wurde.
Stellen Sie sich dies ganz wörtlich so vor, wie es die Bezeichnung „Stack“ verheißt: Sie legen zehn Handtücher auf einen Stapel. Nun nehmen Sie sie allesamt wieder von dem Stapel herunter.

Das Handtuch, das Sie als Letztes auf den Stapel gaben, werden Sie als erstes herunter nehmen.
Das Handtuch, das Sie als Vorletztes auf den Stapel gaben, werden Sie als zweites herunter nehmen, usw. usf.
Das Handtuch, das Sie als Erstes auf den Stapel gaben, als dieser also noch leer war, werden Sie entsprechend als letztes vom Stapel nehmen, worauf hin dieser wieder leer sein wird.

Auch muss der Algorithmus eine Liste bereits abgearbeiteter Punkte führen und diese bei Punkt drei der am Beginn dieses Kapitels aufgeführten Liste vollständig ignorieren, denn sonst kann er einerseits theoretisch in einer Endlosschleife verenden. Auf jeden Fall aber würde er redundanterweise Punkte weiter überprüfen und beschreiten, die er vielleicht schon zahlreiche Male zuvor überprüfte. Schlimmer noch: Dadurch wäre auch nicht mehr gewährleistet, dass der gefundene Weg der kürzeste ist.
Dieses „Protokollführen“ kann auch anders herum fungieren: Alle Punkte werden zunächst in eine Liste noch abzuarbeitender Punkte eingetragen, aus der dann nach und nach alle die Punkte entfernt werden, die bereits abgearbeitet wurden.

In der Praxis wird meist einfach jede passierbare Koordinate mit einer Eigenschaft versehen, die angibt, ob der Punkt bereits besucht wurde oder nicht: Jede begehbare Koordinate wird mit einer Ausrichtung versehen, also einem Wert, der die Richtung angibt, aus welcher der Algorithmus die Koordinate erreicht hat. Dies ist in sofern sinnvoll, als dass der Algorithmus, wenn er am Zielpunkt angekommen ist, nur noch die Ausrichtung des Punktes, von dem aus er den Zielpunkt erreichte, überprüfen muss. Dessen Ausrichtung nämlich gibt ihm wiederum den Punkt an, den der Algorithmus als vorletzten vor dem Zielpunkt erreicht hatte, usw. usf. So ist es dem Algorithmus ein Leichtes, den Weg vom Zielpunkt zum Startpunkt zurück zu verfolgen.
Auch hat er somit einen Anhaltspunkt, welche Punkte er nicht mehr überprüfen muss: Ist ein Punkt als 1 markiert, so ist er unpassierbar und wird als blockiert betrachtet. Hat ein mit 0 markierter Punkt nun jedoch eine Orientierung gesetzt, so weiß der Algorithmus, dass dieser Punkt zwar begehbar ist, jedoch bereits abgearbeitet wurde und somit ebenfalls als blockiert angesehen werden muss.
Der Algorithmus hat nun eine einfache aber effektive Möglichkeit, zu verhindern, bereits geprüfte Wegpunkte noch einmal abzuarbeiten und ihm eröffnet sich somit ebenfalls eine ganz simple Möglichkeit, seinen Weg - wenn er am Ziel angekommen ist - zurück verfolgen zu können!

Anwendungsabhängig könnte man den Dijkstra-Algorithmus noch um eine Kostenfunktion erweitern. In einem Flugplan hat beispielsweise jede Reise von einer Stadt in eine andere einen anderen Preis. Nun könnte der Algorithmus abwägen, welcher Weg der günstigste ist, und diesen vor dem teureren überprüfen. Dies kann einerseits angewandt werden, um die Laufzeit des Algorithmus zu verringern, andererseits jedoch auch, um z.B. nicht den kürzesten sondern einfach allgemein den geeignetsten Weg zu finden.

Theoretisch könnten Sie nun aufhören, diese Abhandlung zu lesen, denn viel mehr gibt das Thema „Dijkstra-Algorithmus“ in der blanken Theorie auf dem Level, auf dem wir ihn hier behandeln, gar nicht her. Da es jedoch etwas ernüchternd erscheinen würde, an dieser Stelle bereits Schluss zu machen, habe ich mich entschlossen, noch ein wenig tiefer in die Materie einzusteigen, und auch, einige kleine Fallen zu besprechen.

Eine quadratförmige Suche?

Wenn Sie nun einmal versuchen, sich vorzustellen, wie die Suche des Algorithmus optisch verläuft, werden Sie womöglich bei der Idee eines sich ausdehnenden Quadrates landen: Denn wir haben einen Punkt A. Nun überprüft der Algorithmus alle Punkte, die an A anliegen, auf ihre Begehbarkeit. Dann überprüft der Algorithmus alle Punkte, die an den an A anliegenden Punkten anliegen, auf ihre Begehbarkeit usw. usf.

Graphisch ließe sich dies wie folgt darstellen:

jedes Kästen sei ein Koordinatentupel
gelb: im momentanen Quadrat um den Ursprungspunkt auf Begehbarkeit untersuchtes Koordinatentupel
grau: bereits untersuchtes Koordinatentupel
weiß: noch nicht untersuchtes Koordinatentupel

O() = 1:

O() = 9:

O() = 25:

Entsprechend würde sich die Suche immer weiter in Form dieses Quadrates ausdehnen. Nicht begehbare Flächen würden das Quadrat zerstören, aber grundsätzlich würde die abgesuchte Fläche sich weiterhin entsprechend ausbreiten.

Diese Vorstellung führt jedoch eine Problematik mit sich, die wir bisher nicht betrachteten! Würde der Algorithmus tatsächlich so, wie in den Abbildungen gezeigt, agieren, so würde er unter bestimmten Bedingungen (soll heißen: bei bestimmen Graphen) zu einem falschen Ergebnis führen!

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 Lektüre der weiteren Kapitel nochmals die vorherigen durchlesen, insbesondere das vorherige und dieses, bis Sie die Frage beantworten können!

Nun, ich gebe zu, die Frage hatte etwas von einer Fangfrage …
Wir haben bisher immer davon gesprochen, dass der Algorithmus bei einem Punkt „die anliegenden Punkte auf ihre Passierbarkeit prüft“. Dies ist insofern etwas missverständlich, als dass wir nicht eindeutig definierten, was denn die „anliegenden Punkte“ sind! In der gerade gezeigten Visualisierung würde der Algorithmus unter „anliegend“ auch die diagonal zum jeweiligen Punkt stehenden Punkte betrachten (daher ja die Quadratform). Dies würde aber die fatale Auswirkung auf unseren Algorithmus haben, diagonale Schritte zu erlauben! Betrachten wir folgenden Graphen:

Man würde erwarten, dass der gefundene Weg vom Startpunkt aus nach unten verläuft, die schwarze Wand umrundet und anschließend wieder nach oben hin zum Ziel führt. Würde unser Algorithmus nun aber mit der quadratförmigen Suche wie in den vorherigen Graphiken arbeiten (und somit diagonale Schritte erlauben), wäre der gefundene Weg der folgende, unerwartete:

Wir müssen unseren Algorithmus also in sofern einschränken, als dass er

entweder, wenn wir eine quadratförmig verlaufende Suche erlauben (was ja prinzipiell weder unmöglich noch ein Verbrechen ist), neben der Passierbarkeit der horizontal und vertikal anliegenden Punkte eines Punktes X zusätzlich noch bei den diagonal anliegenden Punkten überprüft, ob diese überhaupt aus Sicht von X zugänglich sind, oder
die quadratförmige Suche verbieten, indem wir als „anliegende Punkte“ ausschließlich die horizontal und vertikal den Punk X berührenden Punkte definieren.

Erst wenn wir dies getan haben, liefert uns unser Algorithmus auch bei obigem Graphen einen korrekten Weg! Jedoch unterscheiden sich beide Varianten in ihrem Resultat!

Wenn wir als „anliegende Punkte“ nur die horizontalen und vertikalen Nachbarn eines Punktes definieren, so erhalten wir folgendes Ergebnis:

Legitimieren wir hingegen (erlaubte, also nicht durch diagonal verlaufende Wände hindurch tretende) diagonale Schritte, so sieht unser Ergebnis wie folgt aus:

Hier ist es nun Ermessenssache bzw. es kommt auf den konkreten Anwendungszweck an, ob der Algorithmus korrekte diagonale Schritte durchführen können soll oder nicht. Ein allgemeines Richtig oder Falsch gibt es nicht.

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.