En informática , la búsqueda de puntos de salto (JPS) es una optimización del algoritmo de búsqueda A* para cuadrículas de costo uniforme. Reduce las simetrías en el procedimiento de búsqueda mediante la poda de grafos, [1] eliminando ciertos nodos en la cuadrícula basándose en suposiciones que se pueden hacer sobre los vecinos del nodo actual, siempre que se cumplan ciertas condiciones relacionadas con la cuadrícula. Como resultado, el algoritmo puede considerar "saltos" largos a lo largo de líneas rectas (horizontales, verticales y diagonales) en la cuadrícula, en lugar de los pequeños pasos de una posición de cuadrícula a la siguiente que considera el algoritmo A* ordinario. [2]
La búsqueda de puntos de salto preserva la optimalidad de A*, al tiempo que reduce potencialmente su tiempo de ejecución en un orden de magnitud. [1]
La publicación original de Harabor y Grastien proporciona algoritmos para la poda de vecinos y la identificación de sucesores. [1] El algoritmo original para la poda de vecinos permitía que se produjeran cortes de esquina, lo que significaba que el algoritmo solo podía usarse para mover agentes con ancho cero, lo que limitaba su aplicación a agentes de la vida real (por ejemplo, robótica) o simulaciones (por ejemplo, muchos juegos).
Los autores presentaron reglas de poda modificadas para aplicaciones en las que no se permite el recorte de tareas al año siguiente. [3] Este artículo también presenta un algoritmo para preprocesar una cuadrícula con el fin de minimizar los tiempos de búsqueda en línea .
Los autores publicaron una serie de optimizaciones adicionales en 2014. [4] Estas optimizaciones incluyen la exploración de columnas o filas de nodos en lugar de nodos individuales, el precomputado de "saltos" en la cuadrícula y reglas de poda más estrictas.
Aunque la búsqueda de puntos de salto está limitada a cuadrículas de costos uniformes y agentes de tamaño homogéneo, los autores están dirigiendo investigaciones futuras hacia la aplicación de JPS con técnicas de aceleración basadas en cuadrículas existentes, como cuadrículas jerárquicas. [4] [5]