3

私は自分で A* を書きました。これは非常にうまく機能し、そのパフォーマンスを評価する時が来ました (潜在的に他のソリューションと比較してパフォーマンスを確認します)。

視覚的なフィードバックと楽しみの両方を得るために、画像迷路ソルバーとして使用しています。まず、これが A* の本来の目的ではないことは承知していますが、これは (まだ唯一の方法ではありませんが) A* をテストするための非常に良い方法だと思います。同意 ？私はそれを非常にシンプルに保ちました.白いピクセルはノードで、他の色は壁です.

この迷路（大きな絵）を投げつけようと思ったけど、そうなるだろう

  • 3 000 000 を超えるエッジがあるため、明らかに時間がかかります (壁の半分以下ですが)。
  • 必ずしも良い指標ではない、過大な環境

要約すると、どのような環境が A* の適切なストレス テストになりますか? applicative A* (ゲームなど) のグラフの大きさの順序は?

4

2 に答える 2

5


適切なストレス テストは、 1) 大国の一部 (スペイン、フランス、ドイツなど)、
2) 国全体のデジタル道路ネットワークです。(数百万ノード)

OpenStreetMap はそのようなデータを提供しますが、それをグラフにインポートするのは大変な作業です。

于 2013-06-07T17:28:52.903 に答える
2

Parallel New Bidirectional A*のシリアル バージョンを、約 420 x 760 の六角形 (合計 325,000 を超える六角形) の地形マップに実装しました。このマップで最も難しい長い対角線のパスは、約 1080 ステップで、単一の i7 コアで約 0.45 秒の経過時間で完了し、完了時に 90,000 未満のクローズド セット要素を使用します。

Dijkstra と A* に関する限り、地形マップは迷路のような性質を持っていることに注意してください。これは、ステップ コストの範囲が広いため (このマップでは 0m 2 から 10+ まで)、許容されるすべてのヒューリスティックが非効率的であるためです。

于 2013-07-03T01:59:31.080 に答える