Algoritmul lui Dijkstra și Best-First-Search#
Algoritmul lui Dijkstra funcționează prin vizitarea vârfurilor din graf începând cu punctul de plecare al obiectului. Apoi, acesta examinează în mod repetat cel mai apropiat vârf care nu a fost încă examinat, adăugând vârfurile sale la setul de vârfuri care urmează să fie examinate. Acesta se extinde spre exterior de la punctul de plecare până când ajunge la obiectiv. Algoritmul lui Dijkstra este garantat că găsește cea mai scurtă cale de la punctul de plecare până la obiectiv, atât timp cât niciuna dintre muchii nu are un cost negativ. (Scriu „cea mai scurtă cale”, deoarece există adesea mai multe căi echivalente și mai scurte). În următoarea diagramă, pătratul roz este punctul de plecare, pătratul albastru este obiectivul, iar zonele de culoare verde arată ce zone a scanat Algoritmul lui Dijkstra. Cele mai deschise zone teal sunt cele mai îndepărtate de punctul de plecare și, prin urmare, formează „frontiera” de explorare:
Algoritmul Greedy Best-First-Search funcționează într-un mod similar, cu excepția faptului că are o anumită estimare (numită euristică) a distanței de la obiectiv pe care o are orice verigă. În loc să selecteze vertexul cel mai apropiat de punctul de plecare, acesta selectează vertexul cel mai apropiat de obiectiv. Nu se garantează că Greedy Best-First-Search va găsi cea mai scurtă cale. Cu toate acestea, se execută mult mai repede decât Algoritmul Dijkstra, deoarece utilizează funcția euristică pentru a se ghida foarte rapid spre obiectiv. De exemplu, dacă obiectivul se află la sud de poziția de pornire, Greedy Best-First-Search va tinde să se concentreze asupra căilor care duc spre sud. În următoarea diagramă, galbenul reprezintă nodurile cu o valoare euristică ridicată (cost ridicat pentru a ajunge la obiectiv), iar negrul reprezintă nodurile cu o valoare euristică scăzută (cost scăzut pentru a ajunge la obiectiv). Aceasta arată că Greedy Best-First-Search poate găsi căile foarte rapid în comparație cu Algoritmul lui Dijkstra:
Cu toate acestea, ambele exemple ilustrează cel mai simplu caz – atunci când harta nu are obstacole, iar cea mai scurtă cale este într-adevăr o linie dreaptă. Să luăm în considerare obstacolul concav, așa cum a fost descris în secțiunea anterioară. Algoritmul lui Dijkstra muncește mai mult, dar este garantat că găsește cea mai scurtă cale:
Greedy Best-First-Search, pe de altă parte, muncește mai puțin, dar calea sa nu este în mod clar la fel de bună:
Problema este că Greedy Best-First-Search este „lacom” și încearcă să se îndrepte spre obiectiv chiar dacă nu este calea corectă. Deoarece ia în considerare doar costul pentru a ajunge la obiectiv și ignoră costul drumului de până acum, continuă să meargă chiar dacă drumul pe care se află a devenit foarte lung.
Nu ar fi frumos să combinăm ce e mai bun din ambele? A* a fost dezvoltat în 1968 pentru a combina abordări euristice precum Greedy Best-First-Search și abordări formale precum Algoritmul lui Dijsktra. Este puțin neobișnuit în sensul că abordările euristice oferă, de obicei, o modalitate aproximativă de rezolvare a problemelor fără a garanta că veți obține cel mai bun răspuns. Cu toate acestea, A* este construit pe baza euristicii și, deși euristica în sine nu vă oferă o garanție, A* poate garanta cea mai scurtă cale.
.