|
Titlul: Algoritmul A* Scris de: Andrei Misarca din Aprilie 21, 2009, 22:12:56 Am citit pe wikipedia despre Algoritmul A* (http://en.wikipedia.org/wiki/A*_search_algorithm). 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?
Titlul: Răspuns: Algoritmul A* Scris de: Tandrau Alexandru din Aprilie 22, 2009, 08:31:03 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 ]. |