Algorytmy i struktury danych · Senior · Pytanie 3 z 75
Czym A* różni się od algorytmu Dijkstry?
- ✓Poprawna odpowiedź: Dodaje oszacowanie pozostałej odległości
- 2Szuka od celu z powrotem do startu
- 3Ignoruje wagi krawędzi i idzie w kolejności BFS
Wyjaśnienie
A* porządkuje wierzchołki według g + h: znany koszt plus oszacowanie do celu, np. odległość w linii prostej na mapie. Jeśli h nigdy nie przeszacowuje (heurystyka dopuszczalna), ścieżka nadal jest optymalna, a odwiedza się dużo mniej wierzchołków.