java - 在 Java 中实现 A Star (A*) 算法

Question

免责声明：我几乎没有 Java 背景，因为我主要是 C# 开发人员。

想要A*算法的java实现。
是的，我在网上看到了很多相同的版本，我无法在它们之间进行选择。

我正在寻找一种 A* 算法实现，它使用 java 的所有新功能，使算法更快（即使有点）。原因是我们正在实现路径查找MMO，因此性能是重中之重。

任何指针（至少在哪里看）？

Answer 1

尝试几个，测量，选择最快的，适应您的需求。性能主要取决于启发式函数的选择，它独立于 A* 本身。

如果启发式是固定的，优先队列的实现很可能会成为瓶颈，所以尝试pairing heaps。这些是实践中最快的堆数据结构，它们比二进制堆具有优势，它们允许 O(1) 插入时间 + 摊销 O(log n) pop-min。这在许多 A* 循环的预期情况下很重要，其中队列已填满，但从未完全清空，即插入次数远大于弹出次数。

如果内存成为问题，请切换到迭代加深 A* (IDA*) 或递归最佳优先搜索 (RBFS)。

如果没有任何效果，请考虑使用近似算法（贪婪搜索）。简单地优化写得体面的 A* 循环不会给你带来巨大的加速。

请参阅Russell 和 Norvig了解算法和对这些问题的良好讨论。

Answer 2

如果性能是您的首要任务，A* 可能不是您的最佳选择。A* 提供了一个精确的解决方案，因此将继续处理，直到找到正确的答案。还有其他轻量级解决方案可以在更快的时间内提供足够好的解决方案：例如强制爬山或最佳优先，甚至是简单的深度优先。