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
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
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
Fordítá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.