6

2 つの状態間の最短経路を見つけるためのA* 検索アルゴリズムを実装しました。アルゴリズムは、訪問した状態の既知の最適な距離を格納するためにハッシュ マップを使用します。そして、最短経路の再構築に必要な親子関係を格納するための 1 つのハッシュマップ。

これがコードです。アルゴリズムの実装は一般的です (状態は「ハッシュ可能」および「比較可能」である必要があるだけです) が、この特定のケースでは、状態は int のペア (ベクトル) であり[x y]、特定のハイトマップ内の 1 つのセルを表します (隣接するセルにジャンプするためのコストは依存します)身長差について）。

質問は、パフォーマンスを向上させることが可能かどうか、そしてその方法は? おそらく、1.2 または将来のバージョンのいくつかの機能を使用したり、アルゴリズム実装のロジックを変更したり (たとえば、パスを格納する別の方法を使用する)、またはこの特定のケースで状態表現を変更したりすることでしょうか?

このマップのJava 実装は瞬時に実行され、Clojure 実装には約 40 秒かかります。もちろん、これにはいくつかの自然で明白な理由があります: 動的型付け、永続的なデータ構造、プリミティブ型の不要な (アン) ボックス化...

トランジェントを使用しても大きな違いはありませんでした。

4

2 に答える 2

4

priority-mapの代わりに使用sorted-set

最初はオープン ノード (検索フロンティア) の保存に使用していましたが、パフォーマンスの向上sorted-setに切り替えました。現在、このマップには 15 ～ 20 秒かかります(以前は 40 秒かかりました)。priority-map

このブログ投稿は非常に役に立ちました。そして、「私の」新しい実装はほとんど同じです。

新しい a*-search はここにあります。

于 2010-09-10T12:32:42.150 に答える
3

私は Clojure については知りませんが、Vanilla A* のパフォーマンスを改善するための一般的なアドバイスを提供できます。

  • ドメインに適している場合は、より少ないメモリを使用する A* のバリアントであるIDA*の実装を検討してください。

  • 別のヒューリスティックを試してください。優れたヒューリスティックは、必要なノード拡張の数に大きな影響を与える可能性があります。

  • 検索アルゴリズムで「転置テーブル」と呼ばれることが多いキャッシュを使用します。通常、検索グラフは有向非巡回グラフであり、真のツリーではないため、状態の検索を複数回繰り返すことになります。以前に検索されたノードを記憶するためのキャッシュは、ノードの拡張を減らします。

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

于 2010-09-11T23:47:26.870 に答える