Recherche multithread A * en Java, Lisp ou C #

Question

Existe-t-il un bon moyen d'effectuer une recherche A * multithread? Single Thread est assez facile, comme indiqué dans (par exemple) Intelligence artificielle: une approche moderne, mais je n’ai pas trouvé de bonne version multithread.

Supposons un langage sain tel que Java, C # ou Lisp où nous avons des pools de threads et des blocs de travail, et bien sûr un garbage collection.

Answer 1

Je recommande de lire ce document:

"Recherche A * bidirectionnelle parallèle sur un multiprocesseur de symétrie"

Il existe également un autre document, également appelé à l'IEEE:

"Recherche parallèle en astar sur les architectures de transmission de messages"

Les deux articles trouvent de nouvelles méthodes pour gagner un peu plus d’accélération.

Answer 2

J'entends ce que vous dites, mais je ne suis pas sûr que vous vouliez le faire. Dans une recherche A *, vous voulez choisir le chemin optimal et ne faire aucun calcul pour le même chemin deux fois.

Regardez les faits:

• Les "meilleurs" carrés à choisir sont tous côte à côte
• Le calcul pour tout autre carré que le "meilleur" choix est un calcul prématuré. Le point A * est que ses choix sont efficaces.

Si vous avez fileté l'application, vous aurez besoin de:

• un 'Waiter' afin de s'assurer qu'aucun fil ne touche le même carré et pour leur donner de nouveaux carrés à cacluler. Ils travailleraient tous dans une région si soudée qu'ils se disputeraient les ressources du chemin, car toutes les meilleures places sont côte à côte.

Ce problème est procédural et n’a aucun moyen agréable de le diviser en plusieurs parties et n’est donc pas un bon choix pour le filetage. En bref, personne ne l’a fait parce que ce n’est pas souhaitable. J'espère que cela aide.