Java中A星(A*)算法的实现 [英] Implementation of A Star (A*) Algorithm in Java

问题描述

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

Disclaimer: I have little background in Java, since I am predominantly a C# developer.

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

Would like to have the java implementation of A* algorithm.
Yes, I saw many versions of the same online and I am unable to choose between them.

我正在寻找一种 A* 算法实现，它使用了 java 的所有新特性，使算法更快(即使有点).原因是我们正在实施它以在 MMO 上进行寻路，因此，性能是重中之重.

I am looking for an A* algorithm implementation that uses all new features of java that makes the algorithm faster(even if a tad bit). The reason is that we are implementing that for path-finding on an MMO and so, performance is the top priority.

任何指示(至少在哪里看)?

Any pointers ( on atleast where to look ) ?

推荐答案

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

Try several, measure, pick the fastest, adapt to your needs. Performance is mostly determined by the choice of heuristic function, which is independent of A* proper.

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

If the heuristic is fixed, the implementation of the priority queue is likely to become the bottleneck, so try pairing heaps. These are some of the fastest heap data structures in practice, and they have the advantage over binary heaps that they allow for O(1) insertion time + amortized O(log n) pop-min. This is important in the expected case of many A* loops, where the queue is filled, but never entirely emptied, i.e., the number of insertions is much greater than the number of pops.

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

If memory becomes an issue, switch to iterative-deepening A* (IDA*) or recursive best-first search (RBFS).

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

If nothing works, consider using an approximation algorithm (greedy search). Simply optimizing a decently written A* loop isn't going to give you tremendous speed-ups.

请参阅 Russell 和 Norvig，了解算法和对问题的深入讨论.

See Russell and Norvig for algorithms and a good discussion of the issues.

这篇关于Java中A星(A*)算法的实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！