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, 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.
Az ugrópontkeresés megőrzi az A* optimalitását, miközben potenciálisan nagyságrendekkel csökkenti annak futási idejét.
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. 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. 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. 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.
Irodalom
Fordítás
Kategória:Gráfalgoritmusok Kategória:Keresőalgoritmusok