Tietojenkäsittelytieteessä Jump point -haku ( JPS ) on A * -hakualgoritmin optimointi yhtenäisiä kustannustaulukoita varten . Vähentää hakuproseduurin symmetriaa pienentämällä kuvaajaa [1] poistamalla tiettyjä solmuja ruudukosta perustuen oletuksiin, joita voidaan tehdä nykyisen solmun naapureista, jos tietyt ruudukkoon liittyvät ehdot täyttyvät. Tämän seurauksena algoritmi voi ottaa huomioon pitkiä hyppyjä pitkin ruudukon suoria (vaaka-, pysty- ja diagonaalisia) linjoja, eikä pieniä askelia ruudukon paikasta toiseen, kuten tavallinen A* [2] tekee .
Siirtymäkohdan löytäminen pitää A* optimaalisena , mikä saattaa lyhentää sen suoritusaikaa suuruusluokkaa [1] .
Haraborin ja Grastienin alkuperäinen julkaisu esittelee naapurin karsinnan ja seuraajan havaitsemisalgoritmit [1] . Alkuperäinen naapurileikkausalgoritmi salli kulman leikkaamisen, mikä tarkoitti, että algoritmia voitiin käyttää vain nollaleveyksien agenttien siirtämiseen, mikä rajoitti sen käytön joko oikeisiin agentteihin (esim. robotiikka) tai simulaatioihin (esim. monet pelit).
Kirjoittajat ovat toimittaneet muokatut leikkaussäännöt sovelluksiin, joissa kulmien leikkaus poistetaan käytöstä ensi vuonna [3] . Tässä artikkelissa esitellään myös mesh-esikäsittelyalgoritmi Internet-hakuajan minimoimiseksi.
Vuonna 2014 kirjoittajat julkaisivat useita lisäoptimointeja [4] . Nämä optimoinnit sisältävät solmusarakkeiden tai -rivien tarkastelemisen yksittäisten solmujen sijasta, verkon siirtymien esilaskentaa ja tiukemmat leikkaussäännöt.
Vaikka siirtymäpisteiden haku rajoittuu grideihin, joiden kustannukset ovat tasaiset, ja agenteihin, joilla on samankokoinen, kirjoittajat aikovat jatkossa käyttää PTP :itä olemassa olevien grid-pohjaisten kiihdytysmenetelmien, kuten hierarkkisten gridien, kanssa [4] [5] .
| Kaavion hakualgoritmit | ||
|---|---|---|
| Tietämättömät menetelmät | ||
| Tietoon perustuvat menetelmät | ||
| Pikanäppäimet | ||
| Vähintään ulottuva puu | ||
| Muut | ||