Algoritmul A*

[•Mishu91]

Am citit pe wikipedia despre Algoritmul A*. Dar nu am inteles exact ce reprezinta f(x), g(x), h(x) cu exactitate. Si mai exact care este diferenta dintre acest algoritm si Dijkstra?

[•alexthero]

Sa zicem ca vrei sa gasesti drumul minim de la A la B. Pornesti algoritmul A* din sursa A, si te vei opri cand scoti din heap nodul B (ca si Dijkstra).
Diferenta o face o functie estimativa, h(x). H(x) e o functie care-ti spune un cost estimat de la x la B. In loc sa scoti din heap nodul x cu min. d[ x ] vei scoate nodul x care are d[ x ] + h(x) minim. E foarte important ca h(x) sa fie <= decat costul actual din x pana la B. Cred ca explica pe wiki de ce.

Exemplu: Ai niste puncte in plan (coordonate x si y) si un graf definit pe acestea. Vrei sa gasesti drumul minim intre 2 puncte A si B. Ai putea defini h(x) ca distanta in plan de la x la B.

Diferenta intre A* si Dijkstra in implementare e doar faptul ca vei tine un heap cu d[ x ] + h(x) in loc de d[ x ].