Søk i hopppunkt - Jump point search

I informatikk er hopppunktssøk (JPS) en optimalisering av A* -søkealgoritmen for enhetlige kostnadsnett. Det reduserer symmetrier i søkeprosedyren ved hjelp av grafbeskjæring, og eliminerer visse noder i rutenettet basert på forutsetninger som kan gjøres om den nåværende nodens naboer, så lenge visse betingelser knyttet til nettet er oppfylt. Som et resultat kan algoritmen vurdere lange "hopp" langs rette (horisontale, vertikale og diagonale) linjer i rutenettet, i stedet for de små trinnene fra en rutenettposisjon til den neste som vanlig A* vurderer.

Hoppepunktsøk bevarer A*sin optimalitet, samtidig som den muligens reduserer kjøretiden med en størrelsesorden.

Historie

Harabor og Grastiens originale publikasjon gir algoritmer for naboskjæring og identifisering av etterfølgere. Den originale algoritmen for nabobeskjæring tillot hjørneskæring, noe som betydde at algoritmen bare kunne brukes til å flytte agenter med null bredde, og begrense anvendelsen til enten virkelige agenter (f.eks. Robotikk) eller simuleringer (f.eks. Mange spill).

Forfatterne presenterte endrede beskjæringsregler for applikasjoner der hjørneskæring ikke er tillatt året etter. Denne artikkelen presenterer også en algoritme for forbehandling av et rutenett for å minimere søketider på nettet.

En rekke ytterligere optimaliseringer ble publisert av forfatterne i 2014. Disse optimaliseringene inkluderer å utforske kolonner eller noderader i stedet for individuelle noder, forhåndsberegning av "hopp" på rutenettet og sterkere beskjæringsregler.

Fremtidig arbeid

Selv om hoppepunktsøk er begrenset til ensartede kostnadsnett og agenter i homogen størrelse, legger forfatterne framtidig forskning på å bruke JPS med eksisterende nettbaserte hastighetsteknikker som hierarkiske rutenett.

Referanser