Graph Visualisierung

A* ist ein Suchalgorithmus, der wie Dijkstra den kürzesten Pfad sucht, dabei aber zusätzlich eine Heuristik verwendet, um gezielter in Richtung Ziel zu suchen.

Um A* durchzuführen, werden für die Priorisierung eines Knoten n drei Metriken verwendet:

Beispiel 1 - Heuristik mit Anzahl Knotensprüngen

Wir eine Heuristik, die die Anzahl der verbleibenden Sprünge zum Ziel schätzt. Dazu wird vom Ziel aus für jeden Knoten gezählt, wie viel Sprünge bis zum Ziel notwendig sind.

Übungen 1

Wenden Sie A* ohne Pruning an und zeichnen Sie den Baum bis zur Tiefe 3, welcher daraus resultiert. In welcher Reihenfolge werden die verschiedenen Pfade abgesucht?

Mit dem A*-Algorithmus werden die Knoten in steigender Reihenfolge der f(n)-Werte geöffnet:
1. S, da f = 2
2. B (von S), da f = 3
3. A (von S,B), da f = 3
4. A (von S), da F = 4
5. S (von S,B), da F = 4
6. B (von S,B,A), da F = 5
7. B (von S,A), da F = 6
8. G (von S,B,A), da F = 6
9. A (von S,B,S), da F = 6
10. G (von S,A), da F = 7
11. S (von S,B,A), da F = 7
12. B (von S,B,S), da F = 7
13. A (von S,A,B), da F = 7
14. S (von S,A,B), da F = 7
15. S (von S,A), da F = 8
16. B (von S,A,S), da F = 9
17. A (von S,A,S), da F = 10