Prüfungsfrage 04 – Tiefensuche, Breitensuche, Dijkstra, A-Star

 

Ein Land führt ein Mautsystem ein, in dem an jeder Autobahnanschlussstelle oder Kreuzung eine Mautstelle eingerichtet wird und Maut für die seit der letzten Mautstelle zurückgelegte Strecke zu zahlen ist. Je gefahrenem km wird 1 Cent verlangt, mindestens jedoch 10 Cent. Geben Sie die Idee zu einem Algorithmus an, mit dem möglichst effizient die kostengünstigste Strecke zwischen zwei Autobahnanschlussstellen A und B berechnet werden kann! Welche Varianten des Verfahrens ergeben sich, wenn man

  1. davon ausgeht, dass die Koordinaten der Anschlussstellen und Kreuzungen bekannt sind?
  2. davon ausgeht, dass nur das Netz und die Streckenlängen zwischen den Anschlussstellen gegeben sind?

Lösung

inf-a-star-algorithmus-1

Es handelt sich hierbei um ein Problem aus der Graphentheorie: „Finde den kürzesten Weg!“
Das Straßennetz muss also zunächst wie in der Abbildung links als Graph dargestellt werden, dessen Kanten als Gewichte die Mautkosten haben.
Der Graph muss anschließend möglichst zielgerichtet traversiert werden. Es gibt verschiedene Algorithmen zur Traversierung, die aber vom Grundlegenden Aufbau her alle gleich sind. Die Knoten werden zu Beginn in eine Menge U (unbekannt) geschrieben, der Startknoten wird in eine Menge A (aktiv) übernommen. Dann werden nach und nach die erreichbaren Knoten von U nach A geschoben und untersucht. Knoten, deren Nachbarn alle schon betrachtet wurden, wandern in die Menge F (fertig):

für alle Knoten v aus V
	v.status = unbesucht
A.einfügen(vstart)
solange A.anzahl() > 0 wiederhole
	v = A.entferneEinenKnoten()
	für alle Nachbarknoten w von v
		falls w.status == unbesucht
			w.status = aktiv
			A.einfügen(w)
	v.status = erledigt

inf-wegsuche-traversierung

Die verschiedenen Algorithmen unterscheiden sich nun vor allem in der Auswahl des Knotens beim Befehl „entferneEinenKnoten“ und bei der Reihenfolge der Knoten im Befehl danach.

Tiefensuche

Die Tiefensuche verwaltet die Menge A als einen Stapel. Der Knoten, der zuletzt gefunden wurde, wird also als erstes besucht („last in, first out“). Algorithmus:

für alle Knoten v aus V
	v.status = unbesucht
Stapel A.push(vstart)
solange A.anzahl() > 0 wiederhole
	v = A.pop()
	für alle Nachbarknoten w von v
		falls w.status == unbesucht
			w.status = aktiv
			A.push(w)
	v.status = erledigt

Breitensuche

Bei der Breitensuche wird die Menge A als Warteschlange verwaltet. Daraus resultiert, dass die Knoten in der Reihenfolge besucht werden, in der sie gefunden wurden (first in first out).
Der Algorithmus ist ansonsten der gleiche. Damit die Wege später nachvollzogen werden können, muss bei der Traversierung in jedem Knoten der Vorgänger gespeichert werden.
Sollen nicht alle Wege im Graphen, sondern nur ein bestimmter, gefunden werden, kann der Algorithmus vorzeitig abgebrochen werden.

Dijkstra

Um nun statt nur irgend einen Weg den kürzesten Weg zu finden, brauchen wir eine Steuerungsfunktion, die jeweils ein passendes Element aus der Menge A aussucht. Als Bewertungsfunktion nutzt man im Dijkstra-Verfahren die aufsummierten Kantengewichte der Kanten, die auf dem bisher zurückgelegten Weg liegen. Wir ordnen also jedem erreichbaren Knoten als „Abstand vom Startknoten“ den Abstand seines Vorgängers v vom Startknoten, zuzüglich des Gewichtes der Kante vw, zu. Das System funktioniert nur, wenn alle Kantengewichte größer oder gleich 0 sind (bei der Routensuche automatisch erfüllt). Wenn ein Knoten zum ersten Mal eine Bewertung erhält, ist noch nicht sicher, dass dies die minimal mögliche ist. Es könnte sein, dass der Knoten später noch auf einem kürzeren Weg vom Startknoten aus erreicht wird. Daher ist die Bewertungen der Knoten in der Menge A variabel:

für alle Knoten v aus V
	v.status = unbesucht
	v.vorgänger = NULL
	f(v) = INF
A.einfügen(vstart)
f(vstart) = 0
solange A.anzahl() > 0 wiederhole
	v = A.entferneKnotenF_min()
	für alle Nachbarknoten w von v
		falls w.status == unbesucht
			w.status = aktiv
			w.vorgänger = v
			f(w) = f(v)+KantenGewicht(v,w)
			A.einfügen(w)
		sonst // w schon bekannt
			falls f(v)+KantenGewicht(v,w) < f(w)
			w.vorgänger = v
			f(w) = f(v)+KantenGewicht(v,w)
	v.status = erledigt

A*-Algorithmus

inf-a-star-algorithmus-2

Der größte Nachteil des Dijkstra-Verfahrens ist, dass der Graph nicht zielgerichtet durchsucht wird. Wie bei der Breitensuche geht man sternförmig vom Startknoten aus. Eine Weiterentwicklung des Dijkstra-Algorithmus ist der A*-Algorithmus. Es handelt sich bei diesem um ein 1968 von Peter Hart, Nils Nilsson und Bertram Raphael entwickeltes „informiertes“ Suchverfahren. Im Gegensatz zu Dijkstra wird bei der Suche nicht der Knoten mit den geringsten Wegkosten zum Startknoten besucht, sondern der am günstigsten erscheinende.
Die Abbildung zeigt einen Graphen mit zehn von A bis J bezeichneten Knoten und elf ungerichteten gewichteten Kanten. Die Wegkosten entsprechen den grünen Zahlen, die blauen Zahlen repräsentieren zum Vergleich die Luftlinienentfernung zwischen den Knoten. In der linken unteren Ecke sind die Luftlinienentfernungen aller Knoten zu A angegeben.
Wenn wir als Mensch in diesem Graphen den kürzesten Weg von I nach A suchen sollten, würden wir spontan in Richtung F losgehen, weil es unlogisch erschiene, J oder G zu besuchen. Das liegt daran, dass F dem Zielknoten viel näher ist (32 Einheiten) als die beiden anderen Knoten (jeweils 60 Einheiten). Doch wie machen wir diese Logik dem Computer verständlich? Die Lösung ist eine so genannte Heuristik.

„Heuristik ist die Bezeichnung für ein Lösungsverfahren, das nur zum Teil auf wissenschaftlich gesicherten Erkenntnissen, sondern vorwiegend auf Hypothesen, Analogien oder Erfahrungen aufbaut. Die Güte solcher Verfahren ist deshalb meist nicht beweisbar, sondern wird durch wiederholte Experimente an typischen Problemstellungen nachgewiesen.“

Besonders wichtig ist der letzte Satz dieser Definition. Es ist nämlich nicht zu beweisen, dass durch die Verwendung der Luftlinie als Entscheidungsgrundlage für den als nächsten zu besuchenden Knoten der Weg schneller gefunden wird. Da die in der Informatik verwendeten Graphen allerdings meist nicht willkürlich gewählt werden, sondern Darstellungen realer Gegebenheiten sind, gehorchen sie denselben Gesetzen wie die zu modellierenden Objekte. Es ist logisch, dass in einem eine Landkarte darstellenden Graphen die meisten Kantengewichte stark von der Luftlinienentfernung abhängen, obwohl dies nicht zwingend notwendig ist.
Funktion für die Luftlinienentfernung zwischen einem Knoten u und dem Zielknoten:

h\left( u \right) = \sqrt {{{\left( {{x_{Ziel}}-{x_u}} \right)}^2}+{{\left( {{y_{Ziel}}-{y_u}} \right)}^2}}

Diese wird nun zu der schon bei Dijkstra verwendeten Funktion f\left( u \right) addiert, die einem Knoten u die bekannten Wegkosten vom Startknoten nach u zuordnet:

a\left( u \right) = f\left( u \right)+h\left( u \right)

f\left( u \right) muss nun als Kriterium für den jeweils als nächstes zu besuchenden Knoten benutzt werden. Das geschieht, indem dieser Knoten nach dem Kriterium f\left( u \right) = \min gewählt wird. Hier nun ein Beispiel, um die beschriebene Arbeitsweise zu verdeutlichen.

Beispiel: Berechnung des in der Abbildung gesuchten Weges

inf-a-star-algorithmus-3

inginf-a-star-table-1

Es werden zuerst von den drei an den Startknoten angrenzenden Knoten sowohl die Kantengewichte zum Startknoten I als auch die Luftlinien-entfernungen zum Zielknoten A bestimmt und jeweils die Summe daraus gebildet.
Der Dijkstra-Algorithmus würde nun als erstes Knoten J besuchen, da dieser die kleinsten Wegkosten zum Startknoten hat, und liefe damit genau in die falsche Richtung.
Beim A*-Algorithmus ist das Kriterium die berechnete Summe aus Wegkosten und Luftlinie. Daher wird im ersten Schritt Knoten F besucht. Im zweiten Schritt werden alle Knoten überprüft, die von einem der schon besuchten Knoten aus erreicht werden können (also von I oder von F). Das sind die Knoten B, E, G, H und J. Wieder werden die Summen aus Wegkosten und Luftlinienentfernung gebildet und verglichen:

inginf-a-star-table-2

Diese Summe ist bei Knoten B minimal, daher wird er im zweiten Schritt besucht. Im dritten Schritt steht der Algorithmus vor der Wahl zwischen den Knoten E, G, H, J und A. Da A der Zielknoten ist, könnte man meinen, er würde als nächstes besucht, so dass der Weg komplett wäre. Auch die Luftlinienentfernung von Knoten A zu sich selbst, nämlich 0, spricht dafür. Doch der Weg I-F-B-A wäre 75 Einheiten lang. Bei Betrachtung der folgenden Tabelle fällt auf, dass es einen potentiell kürzeren Weg gibt, nämlich über I-F-E. Dieser wäre im Optimalfall (der restliche Weg ab Knoten E entspricht der Luftlinienentfernung von E zu A) nur 63 Einheiten lang, also 12 Einheiten kürzer als der Weg über B.

inginf-a-star-table-3

Da allein die Summe das Kriterium für den als nächstes zu besuchenden Knoten ist, fällt die Wahl auf Knoten E.

inf-a-star-algorithmus-4

inginf-a-star-table-4

Der Weg über die Knoten E und D hat die geringste Summe aus Wegkosten nach I und Luftlinie nach A. Es gibt also einen potentiell kürzeren Weg von I nach A, der über diese beiden Knoten statt über B führt. Auch wenn der optimale Weg über E und D nun „nur noch“ zwei Einheiten kürzer ist als der schon sichere Weg über B, muss er weiter verfolgt werden. Im vierten Schritt wird D besucht.

inginf-a-star-table-5

Der kürzeste Weg ist gefunden. Es ist I-F-E-D-A mit der Länge 74, also genau eine Einheit weniger als der Weg über den Knoten B gehabt hätte. Hier wird deutlich, dass es wichtig ist, dass die Schätzfunktion die Länge des optimalen Weges von einem Knoten zum Ziel immer unterschätzt, da sonst vielleicht der Weg über B als kürzester gefunden worden wäre, obwohl er nicht optimal ist. Die Luftlinienentfernung als Heuristik zu benutzen ist zulässig, da der kürzeste Weg immer mindestens so lang oder länger als die Luftlinie sein muss.

inf-a-star-algorithmus-5

Optimalitätsbeweis

Ob die optimale Lösung gefunden wird, hängt zuerst einmal davon ab, ob die verwendete Heuristik zulässig ist, ob sie also wie schon beschrieben die Wegkosten immer unterschätzt. Wenn diese Bedingung erfüllt ist, kann bewiesen werden, dass die Lösung immer optimal ist.
Im Folgenden werden die folgenden Funktionen verwendet:

  • g\left( u \right) ordnet dem Knoten u die bisher vom Startknoten aus benötigten Wegkosten zu
  • h\left( u \right) schätzt die Wegkosten vom Knoten u zum Zielknoten
  • f\left( u \right) = g\left( u \right)+h\left( u \right) schätzt somit die Gesamtkosten vom Start- zum Zielknoten

Bedingt durch die Vorgehensweise des Algorithmus wird immer zuerst der Knoten u besucht, dem die Funktion f\left( u \right) den geringsten Funktionswert zuordnet. Wenn also zum Beispiel für einen Knoten a gilt: f\left( a \right) = 23, dann werden zuerst alle Knoten x weiter erkundet, für die gilt: f\left( x \right) < 23. Dadurch ist sichergestellt, dass kein Knoten bei der Wegfindung ausgelassen werden kann, über den ein kürzerer Weg zum Ziel möglich wäre. Hier wird auch klar, warum die Kantengewichte nicht negativ sein dürfen, denn sonst könnte nach einem weit vom Ziel entfernten und daher nicht weiter beachteten Knoten noch eine Kante mit einem hohen negativen Kantengewicht kommen, die den schlecht anmutenden Weg dann doch zum kürzesten macht. Aus diesen Überlegungen ergibt sich der formale Beweis:

Annahme: Der A*-Algorithmus findet eine suboptimale Lösung {G_2}, wobei die optimale Lösung {G_1} die Wegkosten {C_1} hat.
Für jeden vom Algorithmus gefundenen Zielknoten z gilt h\left( z \right) = 0, daraus folgt: h\left( {{G_2}} \right) = 0

Außerdem gilt:

f\left( {{G_2}} \right) = g\left( {{G_2}} \right)+h\left( {{G_2}} \right) = g\left( {{G_2}} \right){\text{ > }}{C_1}

Da für jeden beliebigen Knoten n gilt:

h\left( n \right) \leq {\text{Wegkosten}}\left( {n,Ziel} \right)

folgt für einen Knoten auf dem kürzesten Pfad zum optimalen Ziel {G_1}:

f\left( n \right) = g\left( n \right)+h\left( n \right) \leq {C_1}

Diese beiden Gleichungen kann man nun zu der folgenden zusammenfassen:

f\left( n \right) \leq {C_1} < f\left( {{G_2}} \right)

Das bedeutet aber, dass der Knoten {G_2} gar nicht besucht wird, bevor die optimale Lösung {G_1} gefunden wurde, es wird also zuerst {G_1} gefunden, das Verfahren ist optimal, q.e.d.

Ähnliche Artikel

1 Kommentar zu “Prüfungsfrage 04 – Tiefensuche, Breitensuche, Dijkstra, A-Star”

In der 2. und 3. Tabelle beim A*-Algorithmus hat sich jeweils in der Spalte “G” ein Fehler eingeschlichen. Meiner Meinung nach gehört da jeweils in die 1. Zeile der Wert 20 und die Zahl in der Spalte “J” sollte grün gefärbt sein.

Das ist aber nur eine Kleinigkeit – ich finde die Beschreibung super! Sehr anschaulich und verständlich erklärt. Genau das, was ich momentan gebraucht habe. DANKE!

mfg,
doris

Kommentar verfassen