performance - Clojure 中实现的 A* 搜索的性能

Question

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

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

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

此地图的 Java 实现会立即运行，而 Clojure 实现大约需要 40 秒。当然，这有一些自然而明显的原因：动态类型、持久数据结构、对原始类型进行不必要的（取消）装箱......

使用瞬变并没有太大的区别。

score 4 · Accepted Answer

使用`priority-map`代替`sorted-set`

我首先用于sorted-set存储开放节点（搜索边界），切换到priority-map改进的性能：现在这张地图需要 15-20 秒（之前需要 40 秒）。

这篇博文很有帮助。而“我的”新实现几乎是一样的。

新的 a*-search 可以在这里找到。

score 3 · Accepted Answer

我不知道 Clojure，但我可以给你一些关于提高 Vanilla A* 性能的一般性建议。

考虑实现IDA*，它是 A* 的变体，如果它适合您的域，则使用更少的内存。
尝试不同的启发式方法。一个好的启发式可以对所需的节点扩展数量产生重大影响。
使用缓存，在搜索算法中通常称为“转置表”。由于搜索图通常是有向无环图而不是真正的树，因此您最终可能会多次重复搜索状态；用于记住先前搜索过的节点的缓存可减少节点扩展。

Jonathan Schaeffer 博士有一些关于这个主题的幻灯片：