Busca de punt de bot
En informàtica, l'algoritme de busca de punt de bot (Jump Point Search) és una optimisació de l'algoritme A* para rets de cost uniforme. Reduïx les simetria en el procés de busca per mig de la poda(de l'anglés pruning) del grafo, és dir, s'eliminen alguns nodos en base en les suposicions respecte als veïns del nodo actual, sempre i quan les condicions les condicions generals impostes a la ret siguen satisfetes. El resultat és un algoritme pot realisar "bots" llarcs en els trayectes llineals (horisontals, verticals i diagonals) de la ret, en lloc de donar chicotets passos d'una posició a un atre com succeïx en A*.[1]
L'algoritme de busca de punt del bot preserva l'heurística òptima de A*, pero oferix una possible reducció del seu temps d'eixecució de fins a un orde de magnitut.
Història
La publicació de Harabor i Grastien va mostrar algoritmes per a removiment de veïns i identificació de successors. L'algoritme original permet tallar cantons, lo que restringix el seu us a agents d'ample nul i llimita la seua aplicació a qualsevol agent de la vida real o simulació.
L'any següent, els autors varen presentar modificacions de les regles de poda que impedixen tallar cantons, ademés d'un algoritme de pre-processat que permet reduir el temps de busca en llínea.
Un número major d'optimisacions va ser publicat en el 2014.[2] Estes inclouen explorar columnes o files de nodos en lloc de nodos individuals, pre-processament de "bots" en la ret, i més regles de poda més severes.
Treball futur
Este algoritme està llimitat a rets de cost uniforme i agents de tamany homogéneu, no obstant, es propon investigació per a aplicar-ho en tècniques actuals d'acceleració basades en rets, com a rets jeràrquiques.[2][3]
- ↑ Witmer (5 May 2013). «Jump Point Search Explained». zerowidth positive lookahead. Archivat des de l'original, el 10 de març de 2014. Consultat el 2014-03-09.
- ↑ 2,0 2,1 Harabor. «Improving Jump Point Search». Australian National University College of Engineering and Computer Science. Association for the Advancement of Artificial Intelligence (www.aaai.org). Consultat el 2015-07-11.
- ↑ Adi Botea (2004). «Near Optimal Hierarchical Path-Finding». University of Alberta. University of Alberta.
Referències
- Este artícul conté una traducció derivada de «Búsqueda de punto de salto» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.