Porównać algorytm A* z algorytmem Dijkstry

Question

Witam, mam problem z algorytmami A* oraz Dijkstry. Nie zostały one dobrze wytłumaczone i teraz mam z nimi kłopot. Czy ktoś mógłby je porównać ze sobą ? Oraz najprościej wytłumaczyć A* ? Grupa 185IC będzie wdzięczna !

Answer 1

Bardzo prosto:

A* to jest to samo co Dijkstry, ale z dodatkową heurystyką ("jak daleko ten punkt jest od celu?") pomagającą w priorytetyzowaniu węzłów do sprawdzenia.

Innymi słowy:

Dijkstry to szczególny przypadek A*, gdzie heurystyka zawsze zwraca 0 (lub jest niedostępna - ale na to samo wychodzi).

Comments

Dzięki wielkie !

Answer 2

Algorytm A*, jest zachlanny,  ten został zastosowany w grze PACMAN (archaiczny co nie). Wszystko jest w wikipedii

https://pl.wikipedia.org/wiki/Algorytm_A* i https://pl.wikipedia.org/wiki/Algorytm_Dijkstry wystarczy poczytac i wyciagnać winoski....

Answer 3

Algorytm Djikstry to algorytm dokładny wyznaczający najkrótszą trasę. To niby prosty algorytm, ale wykorzystuje całkiem zaawansowane mechanizmy i struktury danych. Pracuje na grafie i kolejce priorytetowej, wykorzystuje programowanie dynamiczne i zachłanne. Z kolejki priorytetowej jest pobierany wierzchołek do którego jest obecnie najbliżej. Z tego wierzchołka są budowane kolejne trasy i dodawane do kolejki i tak aż dojdzie do węzłą docelowego. W praktyce jest kilka pułapek implementacyjnych.

https://pl.wikipedia.org/wiki/Algorytm_Dijkstry
https://www.youtube.com/watch?v=XzPzaPQJsiY

 

Co do A-STAR to nie czuję się na siłach aby wytłumaczyć.

https://pl.wikipedia.org/wiki/Algorytm_A*