私は、2D グリッドといくつかの障害物がある A-star アルゴリズムを使用しています。今、私は垂直方向と水平方向の障害物しか持っていませんが、それらは密に変化する可能性があります.
現在、A スターはうまく機能します (つまり、ほとんどの場合に見つかった最短経路) が、左上隅から右下に到達しようとすると、経路が最短ではないことが時々わかります。つまり、不器用さがあります。パスで。
パスは、最短パスがどうあるべきかから逸脱しているようです。
これが私のアルゴリズムでやっていることです。ソースから開始し、近隣の値を計算しながら外側に移動します。ソースからの距離 + 目的地からの距離について、最小のセルを選択し続け、遭遇したセルが目的地になるまで繰り返し続けます。止まる。
私の質問は、なぜ A-star が最短経路を提供すると保証されないのかということです。またはそれは？私は何か間違ったことをしていますか？
ありがとう。
A-star は、ヒューリスティックが「許容可能」であり、残りの距離を過大評価しないことを意味する場合、メトリック関数に従って最短パスを提供することが保証されます (必ずしも「鳥が飛ぶように」ではありません)。
このリンクを確認してください: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
実装エラーの特定を支援するために、メトリックとヒューリスティックの両方の詳細が必要になります。
更新:
OP のメトリック関数は、直交移動の場合は 10、対角線移動の場合は 14 です。
OPのヒューリスティックは直交する動きのみを考慮しているため、「許容できない」。より安価な対角移動を無視することで過大評価します。
過度に保守的なヒューリスティックの唯一のコストは、最小パスを見つける前に追加のノードを訪問することです。過度に積極的なヒューリスティックのコストは、最適でないパスが返される可能性です。OP は次のヒューリスティックを使用する必要があります。
7 * (deltaX + deltaY)
これは、直接斜めのパスの可能性をわずかに過小評価しているため、パフォーマンスも高くなるはずです。
更新 #2:
パフォーマンスを実際に絞り出すために、これは非常に高速でありながら最適に近いものです。
7 * 分 (デルタ X、デルタ Y) + 10 * ( 最大 (デルタ X、デルタ Y) - 最小 (デルタ X、デルタ Y) )
更新 #3:
上記の7は 14/2 から派生したもので、14 はメトリックの対角コストです。
ヒューリスティックな変更のみ。メトリックは「ビジネス ルール」であり、残りのすべてを駆動します。六角形グリッドの A-star に興味がある場合は、ここで私のプロジェクトをチェックしてください: http://hexgridutilities.codeplex.com/
更新 #4 (パフォーマンスについて):
A-star に対する私の印象は、O(N^2) パフォーマンスの領域とほぼ O(N) パフォーマンスの領域の間でずれているということです。しかし、これはグリッドまたはグラフ、障害物の配置、開始点と終了点に大きく依存するため、一般化するのは困難です。既知の特定の形状またはフレーバーのグリッドおよびグラフには、より効率的なさまざまなアルゴリズムがありますが、多くの場合、より複雑になります。タンスターフル。