我已经实现了一个 A* 搜索算法来查找最短两个状态之间的路径。
算法使用哈希映射来存储访问过的状态的最佳已知距离。以及一个哈希映射，用于存储重建最短路径所需的子父关系。
这里是代码。该算法的实现是通用的（状态只需“可散列”和“可比较”），但在这种特殊情况下，状态是整数对（向量）[xy]，它们代表一个单元格中的一个单元格。给定高度图（跳转到的成本 相邻小区取决于高度）。
问题是是否可以提高性能以及如何提高性能？也许通过使用 1.2 或未来版本中的一些功能，通过改变算法实现的逻辑（例如使用不同的方式来存储路径）或在这种特殊情况下改变状态表示？
Java 实现< /a> 立即运行此地图并且Clojure 实现大约需要 40 秒。当然，这有一些自然而明显的原因：动态类型、持久数据结构、不必要的原始类型装箱……
使用瞬态并没有多大区别。
I have implemented an A* search algorithm for finding a shortest path between two states.
Algorithm uses a hash-map for storing best known distances for visited states. And one hash-map for storing child-parent relationships needed for reconstruction of the shortest path.
Here is the code. Implementation of the algorithm is generic (states only need to be "hashable" and "comparable") but in this particular case states are pairs (vectors) of ints [x y] and they represent one cell in a given heightmap (cost for jumping to neighboring cell depends on the difference in heights).
Question is whether it's possible to improve performance and how? Maybe by using some features from 1.2 or future versions, by changing logic of the algorithm implementation (e.g. using different way to store path) or changing state representation in this particular case?
Java implementation runs in an instant for this map and Clojure implementation takes about 40 seconds. Of course, there are some natural and obvious reasons for this: dynamic typing, persistent data structures, unnecessary (un)boxing of primitive types...
Using transients didn't make much difference.
发布评论
评论（2）
使用
priority-map而不是sorted-set我首先使用
sorted-set来存储开放节点（搜索前沿），切换到 <代码> priority-map 改进了性能：现在 这张地图（之前花了 40 秒）。这篇博客文章非常有帮助。 “我的”新实现几乎是一样的。
新的 a*-search 可以在此处< /a>.
Using
priority-mapinstead ofsorted-setI first used
sorted-setfor storing open nodes (search frontier), switching topriority-mapimproved performance: now it takes 15-20 seconds for this map (before it took 40s).This blog post was very helpful. And "my" new implementation is pretty much the same.
New a*-search can be found here.
我不了解 Clojure，但我可以为您提供一些有关提高 Vanilla A* 性能的一般建议。
考虑实现 IDA*，它是 A* 的变体，使用更少的内存，如果它适合您的域。
尝试不同的启发式。良好的启发式可以对所需的节点扩展数量产生重大影响。
使用缓存，在搜索算法中通常称为“换位表”。由于搜索图通常是有向无环图而不是真正的树，因此您最终可能会重复搜索超过一次的国家；记住以前搜索过的节点的缓存可以减少节点扩展。
Jonathan Schaeffer 博士有一些关于此主题的幻灯片：
http://webdocs.cs.ualberta.ca/~jonathan/Courses/657/Notes/10.Single-agentSearch.pdf
http://webdocs.cs.ualberta.ca/~jonathan/Courses/657/Notes/11.Evaluations.pdf< /a>
I don't know Clojure, but I can give you some general advice about improving the performance of Vanilla A*.
Consider implementing IDA*, which is a variant of A* that uses less memory, if it's suitable for your domain.
Try a different heuristic. A good heuristic can have a significant impact on the number of node expansions required.
Use a cache, Often called a "transposition table" in search algorithms. Since search graphs are usually Directed Acyclic Graphs and not true trees, you can end up repeating the search of a state more than once; a cache to remember previously-searched nodes reduces node expansions.
Dr. Jonathan Schaeffer has some slides on this subject:
http://webdocs.cs.ualberta.ca/~jonathan/Courses/657/Notes/10.Single-agentSearch.pdf
http://webdocs.cs.ualberta.ca/~jonathan/Courses/657/Notes/11.Evaluations.pdf