Ugrópontkeresés
A számítástechnikában az ugrópontkeresés (jump point search, JPS) az A* keresési algoritmus optimalizálása az egységes súlyú (költségű) vagy súlyozatlan gráfokhoz. Úgy csökkenti a szimmetrikus utak miatti többletkeresést az eljárásban, hogy úgynevezett ugrópontokat azonosít,[1] metszési szabályok segítségével lemetszi az új csúcsnak a természetes szomszédait, és azokat ugrópontokkal helyettesíti mindaddig, amíg a gráfra vonatkozó bizonyos feltételek teljesülnek. Ennek eredményeként az algoritmus figyelembe veheti a hosszú "ugrásokat" a gráf egyenes (vízszintes, függőleges és átlós) vonalai mentén, nemcsak az egyik pozíciótól a másikig tartó, a rendes A* által figyelembe vett kis lépéseket.[2]
Az ugrópontkeresés megőrzi az A* optimalitását, miközben potenciálisan nagyságrendekkel csökkenti annak futási idejét.[1]
Történet[szerkesztés]
Harabor és Grastien eredeti publikációja algoritmusokat szolgáltatott a szomszédos csúcsok metszéséhez és következő csúcsok azonosításához.[1] A szomszédos csúcsok metszésének eredeti algoritmusa lehetővé tette a sarokvágást, ami azt jelentette, hogy az algoritmust csak nulla szélességű mozgó ágensekre lehetett használni, korlátozva bármelyik való életbeli ágensre (pl. robotika) vagy akár szimulációkra (pl. játékok) való alkalmazhatóságát.
A szerzők módosított metszési szabályokat mutattak be olyan alkalmazásokra, ahol a sarokvágás nem megengedett.[3] Ez a cikk egy gráf előfeldolgozására is bemutat egy algoritmust az online keresési idő minimalizálása érdekében.
A szerzők számos további optimalizálást tettek közzé 2014-ben.[4] Ezek az optimalizálások magukban foglalják oszlopok vagy sorok feltárását az egyedi csúcsok helyett, az előzetes számításokon alapuló ugrásokat a gráfon és az erősebb metszési szabályokat.
Jövőbeli munka[szerkesztés]
Noha az ugrópontkeresés az egységes súlyú (költségű) gráfokra és egységes méretű ágensekre korlátozódik, a szerzők jövőbeli kutatásokat indítanak a JPS alkalmazásáról a meglévő gráf alapú gyorsítási technikákkal, például a hierarchikus gráfokkal.[4] [5]
Irodalom[szerkesztés]
- ↑ a b c D. Harabor. „Online Graph Pruning for Pathfinding on Grid Maps”..
- ↑ Witmer: Jump Point Search Explained. zerowidth positive lookahead, 2013. május 5. [2014. március 10-i dátummal az eredetiből archiválva]. (Hozzáférés: 2014. március 9.)
- ↑ (2012) „The JPS Pathfinding System”. 26th National Conference on Artificial Intelligence, AAAI. [2020. november 9-i dátummal az eredetiből archiválva]. Hozzáférés: 2020. május 14.
- ↑ a b Harabor: Improving Jump Point Search. Australian National University College of Engineering and Computer Science. Association for the Advancement of Artificial Intelligence (www.aaai.org). (Hozzáférés: 2015. július 11.)
- ↑ Adi Botea: Near Optimal Hierarchical Path-Finding. University of Alberta. University of Alberta, 2004
Fordítás[szerkesztés]
Ez a szócikk részben vagy egészben a Jump point search című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.