Многопоточный A * Поиск в Java или Lisp или C #

Question

Есть ли хороший способ сделать многопоточный поиск A *? Однопоточная довольно проста, как указано, например, в «Искусственном интеллекте: современный подход», но я не сталкивался с хорошей многопоточной версией.

Предположим, что нормальный язык, такой как Java, C # или Lisp, где у нас есть пулы потоков и рабочие блоки, и, конечно, сборщик мусора.

Answer 1

Я рекомендую прочитать эту статью:

«Параллельный двунаправленный поиск A * на мультипроцессоре симметрии»

Существует также еще одна статья, также в IEEE, которая называется:

"Параллельный поиск Astar на архитектурах передачи сообщений"

Обе статьи находят новые методы ускорения.

Answer 2

Я слышу, что вы говорите, но я не уверен, что вы захотите. В поиске A * вы хотите выбрать наиболее оптимальный путь и не хотите делать какие-либо вычисления для одного и того же пути дважды.

Посмотрите на факты:

• 'Лучшие' квадраты для выбора находятся рядом друг с другом
• Вычисление для любого другого квадрата, кроме «лучшего» выбора, является преждевременным вычислением. Суть A * в том, что выбор эффективен.

Если вы работаете с приложением, вам понадобится:

• a 'Официант' , чтобы убедиться, что ни одна нить не коснулась того же квадрата, и дать им новые квадраты для накопления. Все они будут работать в такой тесной области, что будут бороться за ресурсы пути, потому что все «лучшие» квадраты находятся рядом друг с другом.

Эта проблема носит процедурный характер и не имеет хорошего способа разбить ее на отдельные части и, следовательно, не является хорошим выбором для многопоточности. Короче говоря, никто не сделал этого, потому что это нежелательно. Надеюсь, это поможет.