4

私は多くのアプリケーションでA*（およびダイクストラのアルゴリズム）を使用しましたが、パスの長さは関係ありませんが、ターン数が最も少ないパスを見つけるのに行き詰まっています。対角線なしで、上下左右のグリッドを使用しています。

A *はを定義し、コストを追加して拡張しようとしました。これは、次のようなケースになるまで完全に機能します。Cost = DistanceFromStart + Heuristic(Manhattan)numTurns

| 0 0 0 0 0 * 0 0
| 0 0 1' 2' + 0 0 E
| 0 0 S 1 2 * 0 0
| 0 0 0 0 0 * 0 0
| 0 0 0 0 0 * 0 0 （*=壁、0=空、S=開始、E=終了）

S->1->2->+パスはと同じコストを与えることがわかりますs->1'->2'->+。どちらもこれまでのところ1ターン、同じ距離S、同じマンハッタンです。しかし、から、+私たちがプライム'ルートをとった場合、私たちは曲がる必要はありません。しかし、1 2ルートをとった場合、右に曲がる必要があります（+1コスト）。したがって、最初にに到着したとしても1 2、それは最小ターンのパスではありません。

同じ正方形の複数を一度に優先キューに入れて、両方がチャンス（ヒープ内で値が最小の場合）と他の「ハッキー」な解決策を得るようにするなどの調整を試みましたが、そうでないケースを取得し続けます。カバーされています。これを行う直感的な方法はありますか？

ありがとう！

4

2 に答える 2

3

新しい距離行列を作成します。位置 i と j が直線上にある (曲がっていない) 場合は、distance(i,j)=1 を設定します。残りの要素は無限大に設定されています。次に、任意の最短距離アルゴリズムを実行します。

于 2013-02-06T03:12:00.267 に答える
0

状態に「方向」を組み込む必要があると思います。1->2->+ から「+」に到達すると「上」を向き、1'->2'->+ から「+」に到達すると「右」を向いています。

次に、方向転換のコストを「コスト・トゥ・ゴー」に組み込むことができます。つまり、ある州から別の州に移動するための費用です。ここで、1->2->+ に進むと、右への移動を見積もるとき、方向を変えるコストが考慮されますが、1'->2'->+ は考慮されません。

A* の「子の生成」フェーズに到達すると、おそらく「これまでのコスト」を 1 ずつ増やしているだけです。これは、隣接するグリッドセルに移動するのにかかったグリッドセルの数です。現在の位置に対する隣人の方向が現在の方向に != である場合も、1 を追加する必要があります。

最初は、OMNIDIRECTIONAL などの特別な向きを使用できるため、開始位置から任意の正方形に移動してもコストが発生しません。

于 2013-02-06T03:11:56.450 に答える