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

Question

免责声明：我在Java方面的背景很少，因为我主要是C#开发人员。

想要获得A *算法的Java实现。
是的，我看了许多在线版本，但我无法在它们之间进行选择。

我正在寻找一个使用所有新功能的Java A*算法实现，使算法更快（即使只是略微）。原因是我们正在为大型多人在线游戏中的路径查找而实现它，因此性能是最重要的。

有任何指针（至少在哪里查找）？

- naveen

---

你能否给我们提供你已经找到的版本链接？顺便说一句，使用“Java的新特性”并不能使算法更快。 - darioo

链接又过期了，这是最新的链接，供像我这样的人使用： https://github.com/graphhopper/graphhopper/blob/master/core/src/main/java/com/graphhopper/routing/AStar.java - user1265486

@BattleBarnes 包含的双向A*算法甚至更快速 - Karussell

Answer 1

尝试几个算法，测试它们的性能并选择最快的，适应你的需求。性能大部分由启发式函数的选择决定，这与A *本身无关。

如果启发式函数固定，优先队列的实现可能会成为瓶颈，因此建议尝试配对堆。在实践中，这些是一些最快的堆数据结构，并且与二叉堆相比具有优势，允许O（1）插入时间+平摊O（log n）pop-min。这在预期的许多A *循环的情况下非常重要，其中队列已满但从未完全清空，即插入次数远大于弹出次数。

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

如果什么都行不通，请考虑使用近似算法（贪婪搜索）。简单优化一个写得不错的A *循环并不能带来巨大的速度提升。

请参阅Russell和Norvig以获取算法和有关问题的良好讨论。

- Fred Foo

---

应该使用什么数据结构来存储“closedList”？ - st0le

一个哈希表。或者红黑树。或者伸展树。或者任何最快的数据结构。@st0le，你说得对，但是根据我的经验，快速的集合比快速的优先队列更容易获得。 - Fred Foo

@if必要，就需要一个闭合集。 - Fred Foo

@Robert，谢谢。在SO上，如何实现A*算法经常被提及，而“阅读R＆N”几乎总是答案 ;) - Fred Foo

Answer 2

如果性能是您的首要考虑因素，那么 A* 可能不是最佳选择。 A* 提供精确的解决方案，因此会持续处理直到找到正确答案为止。还有其他轻量级的解决方案，可以在更短的时间内提供足够好的解决方案：例如强制爬山或最佳优先搜索，甚至简单的深度优先搜索。

- Robert

---

+1. 优化A*代码不会赢得OP的性能奖。 - Fred Foo

-0，是的，A*算法可能并不那么高效，但你需要的替代方案是针对路径规划的加速技术，例如收缩分层等类似方法。 - Karussell

为了准确起见，A*算法并不总是提供最优解。只有当启发式函数是可接受的时，它才能提供最优解。 - Pierre-Antoine