在 Clojure 中实现的 A* 搜索的性能

Question

我已经实现了一个 A* search algorithm寻找两个状态之间的最短路径。
算法使用哈希映射来存储访问状态的最佳已知距离。还有一个哈希图，用于存储重建最短路径所需的父子关系。

Here是代码。算法的实现是通用的(状态只需要是“可散列的”和“可比较的”)，但在这种特殊情况下，状态是整数对(向量)[x y]并且它们代表给定高度图中的一个单元格( cost 用于跳转到 neighboring cell 取决于高度的差异)。

问题是是否可以提高性能以及如何提高？也许通过使用 1.2 或 future 版本中的一些功能，通过更改算法实现的逻辑(例如，使用不同的方式来存储路径)或在这种特殊情况下更改状态表示？

Java implementation瞬间运行 this map Clojure 实现大约需要 40 秒。当然，这有一些自然而明显的原因:动态类型、持久数据结构、原始类型的不必要(取消)装箱......

使用 transient 并没有太大区别。

Answer 1

使用 priority-map而不是 sorted-set
我第一次用 sorted-set用于存储开放节点(搜索边界)，切换到 priority-map 改进的性能:现在 this map 需要 15-20 秒(在需要 40 秒之前)。

此 blog post非常有帮助。 “我的”新实现几乎相同。

可以找到新的 a*-搜索 here .