Búsqueda multiproceso A * en Java o Lisp o C #

Question

¿Hay una buena manera de hacer una búsqueda A * multiproceso? Un solo subproceso es bastante fácil, como se indica en (por ejemplo) Inteligencia artificial: un enfoque moderno, pero no he encontrado una buena versión multiproceso.

Asuma un lenguaje sensato como Java o C # o Lisp donde tenemos grupos de subprocesos y bloques de trabajo, y por supuesto, recolección de basura.

Answer 1

Recomiendo leer este documento:

" Búsqueda A * bidireccional paralela en un multiprocesador de simetría "

También hay otro documento, también en IEEE llamado:

" Búsqueda paralela de Astar en arquitecturas de paso de mensajes "

Ambos documentos encuentran métodos novedosos para ganar bastante velocidad.

Answer 2

Escucho lo que dices, pero no estoy seguro de que quieras hacerlo. En una búsqueda A *, desea tomar la ruta más óptima y no desea hacer ningún cálculo para la misma ruta dos veces.

Mira los hechos:

• Las 'mejores' casillas para elegir están todas juntas
• Calcular para cualquier otro cuadrado que no sea la 'mejor' opción es un cálculo prematuro. El punto de A * es que sus elecciones son eficientes.

Si enhebra la aplicación que necesitaría:

• a 'Waiter' para asegurarse de que ningún hilo toque el mismo cuadrado y para darles nuevos cuadrados para cacular. Todos estarían trabajando en un área tan unida que estarían luchando por los recursos del camino porque todos los 'mejores' cuadrados están uno al lado del otro.

Este problema es de procedimiento y no tiene una buena manera de dividirlo en partes separadas y, por lo tanto, no es una buena opción para enhebrar. En resumen, nadie lo ha hecho porque no es algo deseable. Espero que esto ayude.