免责声明:我在Java方面的背景很少,因为我主要是C#开发人员。
想要获得A *算法的Java实现。
是的,我看了许多在线版本,但我无法在它们之间进行选择。
我正在寻找一个使用所有新功能的Java A*算法实现,使算法更快(即使只是略微)。原因是我们正在为大型多人在线游戏
中的路径查找而实现它,因此性能是最重要的。
有任何指针(至少在哪里查找)?
免责声明:我在Java方面的背景很少,因为我主要是C#开发人员。
想要获得A *算法的Java实现。
是的,我看了许多在线版本,但我无法在它们之间进行选择。
我正在寻找一个使用所有新功能的Java A*算法实现,使算法更快(即使只是略微)。原因是我们正在为大型多人在线游戏
中的路径查找而实现它,因此性能是最重要的。
有任何指针(至少在哪里查找)?
尝试几个算法,测试它们的性能并选择最快的,适应你的需求。性能大部分由启发式函数的选择决定,这与A *本身无关。
如果启发式函数固定,优先队列的实现可能会成为瓶颈,因此建议尝试配对堆。在实践中,这些是一些最快的堆数据结构,并且与二叉堆相比具有优势,允许O(1)插入时间+平摊O(log n)pop-min。这在预期的许多A *循环的情况下非常重要,其中队列已满但从未完全清空,即插入次数远大于弹出次数。
如果内存成为问题,请切换到迭代加深A *(IDA *)或递归最佳优先搜索(RBFS)。
如果什么都行不通,请考虑使用近似算法(贪婪搜索)。简单优化一个写得不错的A *循环并不能带来巨大的速度提升。
请参阅Russell和Norvig以获取算法和有关问题的良好讨论。
如果性能是您的首要考虑因素,那么 A* 可能不是最佳选择。 A* 提供精确的解决方案,因此会持续处理直到找到正确答案为止。还有其他轻量级的解决方案,可以在更短的时间内提供足够好的解决方案:例如强制爬山或最佳优先搜索,甚至简单的深度优先搜索。