¿Hay una buena manera de hacer una búsqueda A * multiproceso? Single threaded es bastante fácil, como se da en (por ejemplo) Artificial Intelligence: A Modern Approach, pero no he encontrado una buena versión multiproceso.A multiprocesamiento A * Buscar en Java o Lisp o C#
Supongamos un lenguaje como Java o C# o Lisp donde tenemos grupos de hilos y bloques de trabajo, y por supuesto recolección de basura.
recomiendo la lectura de este documento:
"bidireccional paralelo búsqueda A * en un multiprocesador simetría"
También hay otro papel, también en IEEE llamada:
"búsqueda Astar paralelo en el mensaje -passing arquitecturas "
Ambos documentos encuentran métodos novedosos para ganar un poco de aceleración.
Los enlaces serían útiles. –
@StevenRoose Una simple búsqueda en Google de los títulos arrojará los dos artículos mencionados como el primer resultado de búsqueda. Aunque normalmente pongo enlaces cuando es apropiado, por cortesía. Sin embargo, mi mayor problema con el uso de documentos de IEEE como fuentes aquí es que, por lo general, no son gratuitos para aquellos que no están actualmente inscritos en una institución que está cubierta por los documentos de IEEE. – Gurgadurgen
Lo que haría que la respuesta sea discutible. – quimnuss
Escuché lo que está diciendo, pero no estoy seguro de que lo desee. 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.
vistazo a los hechos:
Si la aplicación roscada que se necesita:
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 de hacer. Espero que esto ayude.
Es cierto que podría hacer un trabajo extra, pero podría imaginarme un algoritmo en el que haga suficiente trabajo desperdiciado como para beneficiarse de los muchos hilos de hardware que existen actualmente, especialmente si su espacio de búsqueda es grande o tiene una heurística deficiente. –
Sí, pero todos los 'mejores' cuadrados están uno al lado del otro.Esto solo ayudaría si tu objetivo no fuera un solo punto. Si tu objetivo fuera llegar a cualquier pared de una sala, sería bueno enhebrarlo porque podrías hacer un hilo por cada pared para la habitación y correr hacia él y luego tomar el resultado del mejor hilo. Pero para búsqueda de punto único A * no es una buena idea. –
No solo se trata de trabajo desperdiciado, sino que también se incurre en los costos indirectos al coordinar los hilos. – meriton
¿Así que los lenguajes no recogidos de basura no son idiomas sanos? – BobbyShaftoe
¡No para hacer A *! –
No creo que la recolección de basura sea necesaria para A *. Secuencial A * es bastante simple. Paralelo A * tiene algunos problemas de carga de trabajo. – BobbyShaftoe