Grundlagen des A*-Algorithmus und Anwendung in der Routenplanung GIS Seminar WS 02/03 Christian Siemes

Grundlagen des A*-Algorithmusund

Anwendung in der Routenplanung

GIS Seminar WS 02/03

Christian Siemes

Übersicht

• Wiederholung– Dijkstra-Algorithmus

• Ableitung des A*-Algorithmus– Wichtigste Eigenschaften

• Adaption auf die Routenplanung• Vergleich mit Floyd-Algorithmus und

Dijkstra-Algorithmus

Problemvorstellung

1

2

3

4

5120

10

5

15

Problemvorstellung

Startknoten

Zielknoten

1

2

3

4

5120

10

5

15

1

2

3

4

5120

10

5

15

Problemvorstellung

Startknoten

Zielknoten

1

2

3

4

5120

10

5

15

kürzester Weg

Problemvorstellung

• Laufzeit

• Bestimmende Faktoren– Anzahl der untersuchten Knoten im Graphen– Rechenzeit für jeden Knoten

Datenstrukturen

• Graph G• Suchbaum T• Liste OPEN

• G(N)– Kosten des Pfades von S bis N– N ist der aktuell betrachtete Knoten


• Initialisieren– OPEN und T schaffen– S auf OPEN setzen mit G(N) = 0

10S

Z

1

2

3

4

51

205

15

OPEN G(N)T1 0


• Schleife– Falls OPEN leer, beende die Schleife

S

Z

1

2

3

4

51

20

10

5

15

T OPEN G(N)1 0


OPEN G(N)

S

Z

1

2

3

4

51

20

10

5

15

5



S

Z

1

2

3

4

51

20

10

5

15

T OPEN G(N)1 0

– Entferne den ersten Knoten aus OPEN und setze ihn in T



S

Z

1

2

3

4

51

20

10

5

15

T1

OPEN G(N)

– Entferne den ersten Knoten aus OPEN und setze ihn in T


S

Z

1

2

3

4

51

20

10

5

15

T1

OPEN G(N)

• Schleife– Falls OPEN leer, beende die Schleife– Entferne den ersten Knoten aus OPEN und

setze ihn in T

– Falls Z gefunden, rekonstruiere Pfad und beende die Schleife


S

Z

1

2

3

4

51

20

10

5

15

T1

OPEN G(N)

• Schleife– Falls Z gefunden, rekonstruiere Pfad und

beende die Schleife– Falls Z nicht gefunden, setze alle Nachfolger auf

OPEN und berechne deren Kosten G(N)


S

Z

1

2

3

4

51

20

10

5

15

T1

OPEN G(N)2 203 10





– Ordne OPEN bezüglich G(N) aufsteigend

S

Z

1

2

3

4

51

20

10

5

15

T1

OPEN G(N)2 203 10





S

Z

1

2

3

4

51

20

10

5

15

T1

OPEN G(N)

210320

– Ordne OPEN bezüglich G(N) aufsteigend





• Schleife– Wiederhole die Schleife

S

Z

1

2

3

4

51

20

10

5

15

T1

OPEN G(N)

210320


S

Z

1

2

3

4

51

20

10

5

15

T1

OPEN G(N)

210320

S

Z

1

2

3

4

51

20

10

5

15

T1

OPEN G(N)2 20

3


S

Z

1

2

3

4

51

20

10

5

15

T1

OPEN G(N)2 20

3

S

Z

1

2

3

4

51

20

10

5

15

T1

OPEN G(N)2 15

34 11


S

Z

1

2

3

4

51

20

10

5

15

T1

OPEN G(N)4 11

32 15

S

Z

1

2

3

4

51

20

10

5

15

T1

OPEN G(N)2 15

34 11


S

Z

1

2

3

4

51

20

10

5

15

T1

OPEN G(N)4 11

32 15

S

Z

1

2

3

4

51

20

10

5

15

T1

OPEN G(N)

3

2 15

4

1

3

4 G(4) = 11

Spezialisierungzu Algorithmus A

• Problem– Dijkstra-Algorithmus sucht in allen Richtungen

• Idee– Suche bevorzugt in Richtung des Zielknotens

SS Z Z

Gerichtete Suche Ungerichtete Suche


• Problem– Dijkstra-Algorithmus sucht in allen Richtungen

• Idee– Suche bevorzugt in Richtung des Zielknotens

• Umsetzung– Abschätzung der Kosten von N zu Z: H(N)– F(N) = G(N) + H(N) berechnen und OPEN

bezüglich F(N) aufsteigend sortieren


• F(N) schätzt die Kosten,

die der kürzeste Pfad von S zu Z,

der zwangsweise über N führt, besitzt.

1

2

3

4

5120

10

5

15

S

Z

NG(N)

H(N)

Algorithmus A*

• Notation– G(N), H(N) (geschätzte Kosten)– G*(N), H*(N) (wirkliche Kosten)

• Gilt H(N) H*(N), dann findet Algorithmus A immer den kürzesten Pfad zum Zielknoten.

• Algorithmus A wird zu Algorithmus A*.

Eigenschaften von A*

DefinitionEin Algorithmus ist zulässig, wenn er immer den kürzesten Pfad vom Startkonten zum Zielkonten findet, wenn dieser existiert.

Eigenschaft 4A* ist zulässig.

Eigenschaft 6• A1 und A2 sind zwei Versionen von A*• A2 ist besser informiert als A1, falls H1(N) < H2(N)• A2 erkundet höchstens die gleiche Anzahl von Knoten

wie A1


Nj

Nk

C(Nj ,Nk)

H(Nk)

H(Nj)

Monotonie-Einschränkung C(Nj ,Nk) H(Nj) - H(Nk), bzw.

H(Nk) + C(Nj ,Nk) H(Nj)


Eigenschaft 7Ist die Monotonie-Einschränkung erfüllt, dann hat der A*-Algorithmus den kürzesten Pfad zu jedem Knoten gefunden, der zur Erkundung ausgewählt wird.


1

H(2)=6

3

4

3

22

7

4

H(3)=1S

Z

OPEN

F(2)=3+6=9

F(3)=7+1=8


1

H(2)=6

3

4

3

22

7

4

H(3)=1S

Z

Widerspruch!C(2,3)=2 H(6)-H(3)=5

OPEN

F(2)=3+6=9

F(4)=11

Adaption des A*-Algorithmus auf die Routenplanung

• Graph besitzt Geometrie

• H(N) H*(N) muss erfüllt sein.

Luftlinie von N zu Z * höchste Geschwindigkeit

Adaption des A*-Algorithmus auf die Routenplanung

• Luftlinie = euklidischen Abstand– eukl(N) = Wurzel [(xZ - xN)² + (yZ - yN)²]

• Höchste Geschwindigkeit = maximale im Graph vorkommende Geschwindigkeit

– Vmax

• H(N) = Vmax * eukl(N)

Vergleich mit anderen Algorithmen

• Beispiele für die Größenordnung der Graphen:

# Knoten # Kanten Köln 31.011 67.490 NRW 457.124 1.046.087 Kalifornien 1.580.305 3.934.788

Laufzeit und Speicherplatz

Floyd Dijkstra A* Speicherplatz O(n²) O(n + e) O(n + e)

Laufzeit O(n³) O(e+n log n) O(e+n log n)

( n ... Anzahl der Knoten e ... Anzahl der Kanten)

• Floyd-Algorithmus einmal ausführen, um alle kürzesten Wege im Graphen zu finden

• Anwenden, wenn viele kürzeste Wege im Graphen gesucht werden

Dijkstra-Alogrithmus

• Unterschied zum A*-Algorithmus– Dijkstra-Algorithmus: F(N) = G(N)– A*-Algorithmus: F(N) = G(N) + H(N)

• Speicherplatz ist für beide Algorithmen gleich

• Laufzeitunterschiede wegen H(N)

Dijkstra-Alogrithmus

Empirische Untersuchungen von Stephan Hasselberg haben ergeben:

– A*-Algorithmus untersucht 2 bis 5 mal weniger Knoten

– Vorteil wird nahezu aufgehoben wegen H(N)

– Bei großen geometrischen Distanzen zwischen S und Z wird H(N) so rechenintensiv, dass der Dijkstra-Algorithmus schneller ist

Schlussbemerkung

War alles umsonst?

Overdo-Faktor:

F(N) = G(N) + fOV * H(N) mit fOV > 1

Bei guter Wahl– maximale Fehler in Grenzen– durchschnittliche Fehler klein

Vielen Dank für die Aufmerksamkeit!

Documents

Grundlagen des A*-Algorithmus und Anwendung in der Routenplanung GIS Seminar WS 02/03 Christian Siemes