Búsqueda de punto de salto
En informática, el algoritmo de búsqueda de punto de salto (Jump Point Search) es una optimización del algoritmo A* para redes de costo uniforme. Reduce las simetrías en el proceso de búsqueda mediante la poda(del inglés pruning) del grafo, es decir, se eliminan algunos nodos con base en las suposiciones respecto a los vecinos del nodo actual, siempre y cuando las condiciones las condiciones generales impuestas a la red sean satisfechas.[1] El resultado es un algoritmo puede realizar "saltos" largos en los trayectos lineales (horizontales, verticales y diagonales) de la red, en lugar de dar pequeños pasos de una posición a otro como sucede en A*.[2]
El algoritmo de búsqueda de punto del salto preserva la heurística óptima de A*, pero ofrece una posible reducción de su tiempo de ejecución de hasta un orden de magnitud.[1]
Historia[editar]
La publicación de Harabor y Grastien mostró algoritmos para remoción de vecinos e identificación de sucesores.[1] El algoritmo original permite cortar esquinas, lo que restringe su uso a agentes de ancho nulo y limita su aplicación a cualquier agente de la vida real o simulación.
El año siguiente, los autores presentaron modificaciones de las reglas de poda que impiden cortar esquinas, además de un algoritmo de pre-procesado que permite reducir el tiempo de búsqueda en línea.[3]
Un número mayor de optimizaciones fue publicado en el 2014.[4] Éstas incluyen explorar columnas o filas de nodos en vez de nodos individuales, pre-procesamiento de "saltos" en la red, y más reglas de poda más severas.
Trabajo futuro[editar]
Este algoritmo está limitado a redes de costo uniforme y agentes de tamaño homogéneo, sin embargo, se propone investigación para aplicarlo en técnicas actuales de aceleración basadas en redes, como redes jerárquicas.[4][5]
- ↑ a b c . 25th National Conference on Artificial Intelligence. 2011.
- ↑ Witmer, Nathan (5 de mayo de 2013). «Jump Point Search Explained». zerowidth positive lookahead. Archivado desde el original el 10 de marzo de 2014. Consultado el 9 de marzo de 2014.
- ↑ . 26th National Conference on Artificial Intelligence. 2012.
- ↑ a b Harabor, Daniel. «Improving Jump Point Search». Australian National University College of Engineering and Computer Science. Association for the Advancement of Artificial Intelligence (www.aaai.org). Consultado el 11 de julio de 2015.
- ↑ Adi Botea (2004). «Near Optimal Hierarchical Path-Finding». University of Alberta. University of Alberta.