nav*_*een 12 java algorithm a-star path-finding
免责声明:我没有Java的背景,因为我主要是C#开发人员.
想拥有java实现的A*算法.
是的,我在网上看到了很多相同的版本,我无法在它们之间做出选择.
我正在寻找一个A*算法实现,它使用java的所有新功能,使算法更快(即使有点).原因在于我们正在实施路径查找MMO,因此,性能是首要任务.
任何指针(至少在哪里看)？
Fre*_*Foo 22
尝试几种,测量,选择最快,适应您的需求.性能主要取决于启发式函数的选择,它与A*本身无关.
如果启发式修复,优先级队列的实现可能会成为瓶颈,所以尝试配对堆.这些是实践中最快的堆数据结构,它们比二进制堆具有优势,它们允许O(1)插入时间+摊销的O(log n)pop-min.这在许多A*循环的预期情况下很重要,其中队列被填充但从未完全清空,即插入的数量远远大于弹出的数量.
如果内存成为问题,请切换到迭代加深A*(IDA*)或递归最佳优先搜索(RBFS).
如果没有任何效果,请考虑使用近似算法(贪婪搜索).简单地优化一个体面的A*循环不会给你带来巨大的加速.
请参阅Russell和Norvig的算法以及对问题的良好讨论.
Rob*_*ert 10
如果表现是您的首要任务,A*可能不是您的最佳选择.A*提供了精确的解决方案,因此将继续处理,直到找到正确的答案.还有其他轻量级解决方案可以在更快的时间内提供足够好的解决方案:例如强制爬坡或最佳优先,甚至是简单的深度优先.