1

特定の開始点と終了点を持つ迷路で最短経路を探しています。迷路は、テーブル内の一部のセルを通過できない場合 (「壁」)、2D テーブル (行と列) として構築されます。 )、これまでのところ非常に良好で、A* アルゴリズムは正常に動作しますが、問題は、特定のセルの「重み」が他のセルよりも優れている場合に始まります..たとえば、3*3 迷路を考えてみましょう:

  • 出発点1*1
  • 終点 3*3
  • 1*3 のセルの重みは他のセルよりも優れています。つまり、最終的にルートが等しい場合は、このセルを通過することをお勧めします。

したがって、A* によって、1*3 のセルでさえ、重みが優れていることがわかりません!

その問題の解決策はありますか？

ありがとう！

4

1 に答える 1

4

迷路を表すグラフを作成しますG=(V,E)。

グラフのエッジの重み関数を使用して、新しい重み付きグラフを作成します。

w(u,v) = 1                if v is "not important"
         1-1/(n+1)        if v is important.
(n is the total number of vertices/cells in your maze).

vここで、通過するパスは、通過しないパスよりも「良い」(短い) ことに注意してください。ただし、それでも (距離が) 短いパスが常に優先されます。

修正されたヒューリスティック関数で A* を使用できるようになりました。

h'(v) = h(v)*[1-1/(n+1)]  [where h(v) is the original admissible heuristic you had]

注:コメントは無視してください。許容できるヒューリスティック関数がある場合、Dijsktra のアルゴリズムは A* よりも劣ります。

于 2014-02-16T13:24:57.147 に答える