Joe*_*mel 6 performance artificial-intelligence a-star clojure
我已经实现了A*搜索算法,用于查找两个状态之间的最短路径.算法使用哈希映射来存储访问状态的最佳已知距离.并且一个哈希映射用于存储重建最短路径所需的子父关系.
这是代码.该算法的实现是通用的(状态只需要"可以"和"可比较"),但在这种特殊情况下,状态是整数的对(向量),[x y]它们代表给定高度图中的一个单元(跳转到相邻单元的成本取决于在高度上的差异).
问题是,是否可以提高性能以及如何提高性能？也许通过使用1.2或未来版本中的一些功能,通过改变算法实现的逻辑(例如,使用不同的方式来存储路径)或在这种特定情况下改变状态表示？
Java实现在此映射中立即运行,Clojure实现大约需要40秒.当然,有一些自然而明显的原因:动态类型,持久数据结构,原始类型的不必要(un)装箱......
使用瞬变没有太大的区别.
priority-map代替sorted-set我首先用于sorted-set存储开放节点（搜索前沿），后来切换到改进的性能：现在此地图priority-map需要 15-20 秒（之前需要 40 秒）。
这篇博文非常有帮助。“我的”新实现几乎是一样的。