Szakkörök‎ > ‎Algoritmus szakkör‎ > ‎2012-2013‎ > ‎

3. óra

A kupac adatszerkezet megvalósításával töltöttük az időt, majd szó esett az A* algoritmusról. A kupac a prioritási sor megvalósításához használható.

A* algoritmus

Az előző szakkörön megbeszélt naiv algoritmus egy lehetséges javítása volt a téma. Legrövidebb út illetve leggyorsabb megoldás megtalálásához használható az A* algoritmus. Hasonlóan a naiv algoritmushoz egy sorban tároljuk a felfedezett csomópontokat. Az újdonság abban van, hogy nem egyszerű sort, hanem prioritási sort használunk. 

Út hosszának becslése

A prioritási sor rendezési kulcsa két tételből adódik össze:
  • az adott állapotba vezető út hossza;
  • egy alsó becslés (heurisztika) arra nézve, hogy az adott állapotból még hány lépés kell a cél eléréséhez.
Az algoritmus a prioritási sorból mindig a legkisebb kulcsú csomópontot veszi ki, vagyis abból az állapotból próbál továbbhaladni, amiről pillanatnyilag úgy látszik, hogy rajta keresztül vezet a legrövidebb út a célba.

Körök kezelése

A ciklikusság kizárására két módszer került szóba:
  • tárolhatjuk egy halmazban a már bejárt állapotokat
  • illetve ha tudjuk, hogy van út a célba, akkor elég, ha a triviális A -> B -> A alakú köröket zárjuk ki, hiszen a hosszabb körök a prioritási sor rendezése miatt nem kerülnek be a felépített útba. A rövid körök kizárásához csak annyi kell, hogy mindig tároljuk az előző állapotot, és azt nem rakjuk be újra a sorba, rögtön a következő lépésben.