Java中A Star（A *）算法的实现

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

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

我正在寻找一个A *算法实现，它使用java的所有新function，使算法更快（即使有点）。 原因是我们正在实施MMO上的路径寻找，因此，性能是首要任务。

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

Answer 1

尝试几种，测量，选择最快，适应您的需求。 性能主要取决于启发函数的选择，启发函数与A *本身无关。

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

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

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

请参阅Russell和Norvig的算法以及对问题的良好讨论。

Answer 2

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