Java、Lisp 或 C# 中的多线程 A* 搜索

Question

有没有好的方法来进行多线程 A* 搜索？单线程相当简单，如（例如）人工智能中所示：一种现代方法，但我还没有遇到一个好的多线程版本。

假设像 Java、C# 或 Lisp 这样的正常语言，我们有线程池和工作块，当然还有垃圾收集。

Answer 1

我建议阅读本文：

“对称多处理器上的并行双向A *搜索”

另一篇论文也在IEEE上发表：

“在消息传递架构上进行并行Astar搜索”

两篇论文都找到了获得相当多加速的新方法。

Answer 2

我听到你在说什么，但我不确定你是否愿意。在 A* 搜索中，您希望采用最佳路径，并且不想对同一路径进行两次计算。

看看事实：

• 可供选择的“最佳”方块都彼此相邻
• 计算除“最佳”选择之外的任何其他平方都是过早的计算。A*的要点在于它的选择是有效的。

如果您对应用程序进行线程化，您将需要：

• A '服务员' 以确保没有线程接触同一个方块并为它们提供新的方块进行计算。他们都将在一个紧密结合的区域中工作，以至于他们会争夺路径资源，因为所有“最佳”方块都彼此相邻。

这个问题是程序性的，没有很好的方法将其分解为单独的部分，因此对于线程来说不是一个好的选择。简而言之，没有人这样做，因为这不是一件可取的事情。我希望这有帮助。