Implementación de un algoritmo Star (A *) en Java

Question

Descargo de responsabilidad: Tengo poca formación en Java, dado que soy predominantemente un desarrollador de C#.

Me gustaría tener la implementación java del algoritmo A *.
Sí, vi muchas versiones del mismo en línea y no puedo elegir entre ellas.

Estoy buscando una implementación de algoritmo A * que use todas las características nuevas de java que hace que el algoritmo sea más rápido (aunque sea un poco). La razón es que estamos implementando eso para buscar rutas en un MMO y, por lo tanto, el rendimiento es la principal prioridad.

¿Alguna sugerencia (al menos dónde mirar)?

Answer 1

Pruebe varias, mida, elija la más rápida, adáptese a sus necesidades. El rendimiento está principalmente determinado por la elección de la función heurística, que es independiente de A * propiamente dicha.

Si la heurística es fija, es probable que la implementación de la cola de prioridad se convierta en el cuello de botella, así que intente pairing heaps. Estas son algunas de las estructuras de datos de montón más rápidas en la práctica, y tienen la ventaja sobre los montones binarios que permiten O (1) tiempo de inserción + O amortiguado (log n) pop-min. Esto es importante en el caso esperado de muchos bucles A *, donde se llena la cola, pero nunca se vacía por completo, es decir, el número de inserciones es mucho mayor que el número de estallidos.

Si la memoria se convierte en un problema, cambie a la profundización iterativa A * (IDA *) o la búsqueda recursiva de la mejor primera búsqueda (RBFS).

Si nada funciona, considere usar un algoritmo de aproximación (búsqueda codiciosa). Simplemente optimizando un bucle A * decentemente escrito no se obtendrán tremendas aceleraciones.

Consulte los algoritmos para obtener una buena discusión de los problemas y Russell and Norvig.

Answer 2

Si el rendimiento es su principal prioridad, A * probablemente no sea su mejor opción. A * proporciona una solución exacta, y como resultado seguirá procesando hasta que encuentre la respuesta correcta. Existen otras soluciones livianas que brindan soluciones lo suficientemente buenas en tiempos mucho más rápidos: por ejemplo, la escalada montada o la mejor primero, incluso una simple profundidad primero.