Deykstra mənbədən eyni məsafədə olan bütün düyünləri araşdırır, hədəfin harada olduğunu isə bilmir. A\* (A-star) hər düyün üçün hədəfə qalan məsafənin təxminini (evristikanı) da nəzərə alır və hədəfə yaxın görünən düyünləri əvvəl açır. Evristika düzgündürsə nəticə Deykstra qədər optimaldır, amma daha az düyün araşdırılır.
Prioritet f = g + h
g(n) — başlanğıcdan n-ə qədər artıq keçilmiş dəqiq məsafə; h(n) — n-dən hədəfə qalan məsafənin təxmini. Növbədən (heapq) f(n) = g(n) + h(n) ən kiçik olan düyün götürülür. h(n) = 0 olarsa alqoritm Deykstra ilə üst-üstə düşür, çəkisiz qrafda isə BFS-dir.
Məqbul və ardıcıl evristika
- Məqbul (admissible):
h(n)heç vaxt real qalan məsafədən böyük deyil. Onda A* optimal yol tapır. - Ardıcıl (consistent):
h(a) <= cost(a, b) + h(b)hər qövs üçün. Ardıcıl evristika həmişə məqbuldur və hər düyün yalnız bir dəfə açılır.
Dörd istiqamətli şəbəkədə vahid addımlarla standart seçim Manhetten məsafəsidir: o divarları nəzərə almır, ona görə real məsafədən böyük ola bilməz. Evklid məsafəsi də məqbuldur, amma daha zəifdir.
import math
def manhattan(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def euclid(a, b):
return math.hypot(a[0] - b[0], a[1] - b[1])