Primero, no se puede enfatizar con suficiente frecuencia que la búsqueda A * es solo una forma de modificar el algoritmo de Dijkstra para hacerlo un poco más inteligente. De hecho, el algoritmo de Dijkstra es exactamente equivalente a ejecutar una búsqueda A * con una función heurística que es cero en todas partes.
En segundo lugar, puede encontrar una descripción del algoritmo y su pseudocódigo en Wikipedia: algoritmo de búsqueda A *. Tenga en cuenta que el pseudocódigo proporcionado supone que tiene una heurística coherente (o monotónica). Esto parece un problema de tarea, por lo que no escribiré el código Java exacto para usted.
Las operaciones para nuestra lista abierta son agregar nuevos vértices con una distancia asociada a medida que descubrimos, y eliminar el vértice con la distancia más baja para poder explorarlo a continuación. Estas son exactamente las operaciones básicas soportadas por una cola prioritaria.
- Cómo hacer que el siguiente código sea mejor y más eficiente para el problema de invertir las palabras en la oración dada
- ¿Por qué se usa la compresión de backend?
- Cómo elegir la estructura de datos correcta
- ¿Hay algún proceso o conjunto de preguntas que uno debería hacer al resolver problemas tácticos de ajedrez?
- ¿Cuál es la diferencia entre binario, algoritmo y lenguaje de programación?
Las operaciones para nuestra lista cerrada son agregar nuevos vértices con una distancia dada, buscar la distancia para un vértice dado y posiblemente eliminar vértices. Estas son exactamente las operaciones básicas compatibles con un hashmap. (Aunque si las etiquetas en sus vértices son enteros de 1 a n, tendría más sentido usar una matriz).
Java proporciona ambas estructuras de datos, por lo que puede importarlas desde java.util y buscar allí la documentación sobre cómo se llama cada función.
¡Buena suerte! Avísame si quieres que explique algo de eso.
