14

次のA*検索の例に関して何か明確にしたいと思います。

A*検索例

赤い楕円で強調表示されているセクションは、私が理解していない領域です。（上記）{S,B} f=2+6=8から取得/移動/コピーされ、で使用されているようです。また、から取得/移動/コピーされ、で使用されているようです。Expand SExpand A{S,A,X} f=(1+4)+5=10Expand AExpand B

なぜこれが起こるのか誰かが親切に説明できますか？私はグラフを完全に読むことができ、それを解釈するのに問題はありません-それは、前述のパス/ルートが他の場所で複製された理由がわからないという事実にすぎません。

ありがとうございました。

4

2 に答える 2

9

これは、現在の最良のアイテムを取得し、それを削除して、拡張に置き換えます（新しいアイテムをリストの適切な位置に挿入します）。このように考えてください：

Sを展開：

  • {S,A} f = 1+5 = 6
  • {S,B} f = 2+6 = 8

Aを展開：

  • {S,A} f = 1+5 = 6
  • {S,B} f = 2+6 = 8
  • {S,A,X} f = (1+4)+5 = 10
  • {S,A,Y} f = (1+7)+8 = 16

Bを展開：

  • {S,B} f = 2+6 = 8
  • {S,A,X} f = (1+4)+5 = 10
  • {S,B,C} f = (2+7)+4 = 13
  • {S,A,Y} f = (1+7)+8 = 16
  • {S,B,D} f = (2+1)+15 = 18
于 2011-05-01T16:48:52.883 に答える
2

パスは複製されず、アルゴリズムがまだ調査していないパスとして残ります。A *は、オープンセットを維持することによって機能します。これは、アルゴリズムが到達方法（およびコスト）をすでに知っているノードのコレクションですが、まだそれらを拡張しようとはしていません。

各反復で、アルゴリズムは開集合から展開するノードを選択します（f関数が最も低いノード-f関数は、ノードに到達するためにアルゴリズムがすでに知っているコスト（g）とアルゴリズムのノードからゴールに到達するのにかかる費用の見積もり（h、ヒューリスティック）。

http://en.wikipedia.org/wiki/A*_search_algorithm

オープンセットが使用されていることがわかるように、そこにある擬似コードを見てください。つまり、アルゴリズムがパスまたはノードをある反復から別の反復に複製\コピー\移動することによって機能するのではなく、同じノードのコレクションで機能するだけです（もちろん、ノードはコレクションに追加されたり、コレクションから削除されたりします）。

お役に立てれば...

于 2011-05-01T16:48:10.220 に答える