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 costes uniformes. Reduce la simetría en el procedimiento de búsqueda al reducir el gráfico [1] mediante la eliminación de ciertos nodos en la cuadrícula en función de las suposiciones que se pueden hacer sobre los vecinos del nodo actual si se cumplen ciertas condiciones relacionadas con la cuadrícula. Como resultado, el algoritmo puede tener en cuenta saltos largos a lo largo de líneas rectas (horizontales, verticales y diagonales) en la cuadrícula, en lugar de pequeños pasos de una posición de cuadrícula a otra, como lo hace A* [2] normal .
Encontrar un punto de transición mantiene A* óptimo , reduciendo potencialmente su tiempo de ejecución en un orden de magnitud [1] .
La publicación original de Harabor y Grastien presenta algoritmos de detección de sucesores y poda de vecinos [1] . El algoritmo de recorte de vecinos original permitía el corte de esquinas, lo que significaba que el algoritmo solo podía usarse para mover agentes de ancho cero, limitando su uso a agentes reales (por ejemplo, robótica) o simulaciones (por ejemplo, muchos juegos).
Los autores han presentado reglas de recorte modificadas para aplicaciones en las que el recorte de esquinas se desactivará el próximo año [3] . Este artículo también presenta un algoritmo de preprocesamiento de malla para minimizar el tiempo de búsqueda en Internet.
En 2014, los autores publicaron varias optimizaciones adicionales [4] . Estas optimizaciones incluyen examinar columnas o filas de nodos en lugar de nodos individuales, transiciones de cálculo previo en la malla y reglas de recorte más estrictas.
Aunque la búsqueda de puntos de transición se limita a cuadrículas con costos uniformes y agentes con tamaño uniforme, en el futuro los autores planean utilizar PTP con métodos de aceleración basados en cuadrículas existentes, como las cuadrículas jerárquicas [4] [5] .