Dijkstra algoritmusa és a Best-First-Search#
A Dijkstra algoritmusa úgy működik, hogy az objektum kezdőpontjával kezdve meglátogatja a gráf csúcsait. Ezután ismételten megvizsgálja a legközelebbi, még nem vizsgált csúcsot, és annak csúcsait hozzáadja a vizsgálandó csúcsok halmazához. A kiindulási ponttól kifelé haladva addig terjeszkedik, amíg el nem éri a célt. A Dijkstra-algoritmus garantáltan megtalálja a legrövidebb utat a kiindulópontból a célhoz, amennyiben egyik élnek sincs negatív költsége. (Azért írom, hogy “legrövidebb út”, mert gyakran több egyenértékűen rövid út létezik). Az alábbi ábrán a rózsaszín négyzet a kiindulópont, a kék négyzet a cél, a teáskék területek pedig azt mutatják, hogy a Dijkstra-algoritmus milyen területeket vizsgált. A legvilágosabb teal területek azok, amelyek a legtávolabb vannak a kiindulási ponttól, és így a feltárás “határát” képezik:
A mohó Best-First-Search algoritmus hasonlóan működik, azzal a különbséggel, hogy rendelkezik valamilyen becsléssel (úgynevezett heurisztikával) arról, hogy melyik csúcs milyen messze van a céltól. Ahelyett, hogy a kiindulási ponthoz legközelebbi csúcsot választaná ki, a célhoz legközelebbi csúcsot választja ki. A mohó Best-First-Search nem garantálja, hogy megtalálja a legrövidebb utat. Azonban sokkal gyorsabban fut, mint a Dijkstra-algoritmus, mivel a heurisztikus függvényt használja arra, hogy nagyon gyorsan a cél felé vezesse az utat. Ha például a cél a kiindulási helytől délre van, a Greedy Best-First-Search a dél felé vezető utakra fog összpontosítani. Az alábbi ábrán a sárga szín jelöli a magas heurisztikus értékkel rendelkező csomópontokat (a cél elérésének magas költségei), a fekete szín pedig az alacsony heurisztikus értékkel rendelkező csomópontokat (a cél elérésének alacsony költségei). Ez azt mutatja, hogy a mohó Best-First-keresés a Dijkstra-algoritmushoz képest nagyon gyorsan képes utakat találni:
Mindkét példa azonban a legegyszerűbb esetet szemlélteti – amikor a térképen nincsenek akadályok, és a legrövidebb út valóban egy egyenes. Tekintsük a homorú akadályt az előző szakaszban leírtak szerint. A Dijkstra-algoritmus nehezebben dolgozik, de garantáltan megtalálja a legrövidebb utat:
A Greedy Best-First-Search ezzel szemben kevesebb munkát végez, de az útja egyértelműen nem olyan jó:
A baj az, hogy a Greedy Best-First-Search “mohó”, és akkor is megpróbál a cél felé haladni, ha az nem a helyes út. Mivel csak a cél elérésének költségeit veszi figyelembe, és figyelmen kívül hagyja az eddigi út költségeit, akkor is továbbmegy, ha az út, amelyen halad, nagyon hosszú lett.
Nem lenne jó, ha a kettőből a legjobbat kombinálnánk? Az A*-ot 1968-ban fejlesztették ki, hogy egyesítse az olyan heurisztikus megközelítéseket, mint a Greedy Best-First-Search és az olyan formális megközelítéseket, mint a Dijsktra algoritmus. Ez egy kicsit szokatlan, mivel a heurisztikus megközelítések általában közelítő megoldást adnak a problémák megoldására anélkül, hogy garantálnák, hogy a legjobb választ kapjuk. Az A* azonban a heurisztikára épül, és bár maga a heurisztika nem ad garanciát, az A* garantálni tudja a legrövidebb utat.