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

Question

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

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

Answer 1

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

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

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

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

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

Answer 2

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

Взгляните на факты:

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

Если бы вы запустили потоковое приложение, вам понадобилось бы:

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

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