0

許容できないヒューリスティックで A* を使用すると、結果として最適でないパスが得られることがあります。

しかし、ゼロコストのパスを持つことが許可されている場合、私の頭に浮かぶ唯一の許容できるヒューリスティックはh(x) = 0、 A* を「単純な」ダイクストラのアルゴリズムに変えることです。

私は正しいですか？これは唯一の許容可能なヒューリスティックですか? 許容可能なヒューリスティックを使用しないことの実際の損失は何ですか? ゼロコストパスでよりうまく機能する他のパス検索アルゴリズムはありますか?

例：

次のグラフを想定します (端の上の数字はコストを示します)。

   1      1      0      1      1
S --> V1 --> V2 --> V3 --> V4 --> G

どこ：

  • S は開始頂点を意味します
  • V は内側の頂点を意味します
  • G はゴール頂点を意味します

グラフを見ると、C(S) = 4.

どのヒューリスティック関数h(x)を使用できますか? ユークリッド距離を使用すると、次のようになりました。

f(S) = g(S) + h(S)
f(S) = 0 + 5 = 5

このヒューリスティックが実際の距離を過大評価していることがわかります。したがって、より複雑なグラフでは、最適な解が見つからない可能性があります。

4

1 に答える 1

2

違います。ヒューリスティック関数には、現在の検索状態で構成されるh(x)引数があります。ゴールxまでの推定距離を返します。x単純なグラフでxは、グラフ ノードです。

許容性は、過小評価(または目標距離と等しい)h(x)のみである必要があります。この条件は、特定の x ごとに適用されます。(条件が可能なすべての xであると推測しているようですが、これは強すぎます。これが必要な場合、 A* は役に立ちません。)

あなたが提案するケースに関する正しいステートメントは、がゴールまでの距離がゼロの状態である場合にのみh(x) = 0必要です。それ以外の値は過大評価になります。ただし、目標に到達するために総コストが最小の遷移を必要とする (同じ状態空間内の)他のものについては、そのようなものをすべて持つことができます。xxC>0hh(x)<=C

もちろん、xのゴールまでの距離がゼロの場合、x はゴール状態であり、探索は完了です。したがって、あなたの懸念は空虚です-それが興味深い場合はありません。

構築する情報h(x)は、検索空間に関する知識 (グラフの特性など) から得られます。むき出しの一般的なグラフだけでは、何の役にも立ちません。あなたができる最善のことはh(x) = cost of min weight outgoing edge of x、非ゴール ノードと、既に説明h(x) = 0したようにゴールに対してです。繰り返しますが、これはゴールまでの距離の下限です。それはあなたにダイクストラを与えます！

うまくやるには、グラフの構造について知っておく必要があります。

編集

あなたの例では、詳細な知識を提供しているので、良いものを作るのhは簡単です. 使用できます

        /  4   if x == S
       |   3   if x == V1 
h(x) = {   2   if x == V2 or V3 
       |   1   if x == V4
        \  0   if x == G

または、 for allh'(x)などの他の関数を使用できます。たとえば、これは許容されます。h'(x) <= h(x)x

         /  3   if x == S
        |   2   if x == V1 
h'(x) = {   2   if x == V2 or V3 
        |   1   if x == V4
         \  0   if x == G

添加

h(x)OPは、多くの問題で選択が難しいことを指摘しています! これは正確に正しいです。許容できる優れたヒューリスティックが見つからない場合、A* は間違ったアルゴリズムです! それにもかかわらず、A* はヒューリスティックを見つけることができる問題に対して非常に効果的です。私が自分で試した例：

  1. ユークリッド距離が任意の 2 つのノード間の可能な距離の適切な下限であるグラフ。たとえば、都市 A と B の各ペアは距離 D だけ離れていますが、A から B までの道路の長さは少なくとも D であり、おそらくそれ以上です。つまり、そのコスト C は、 D に等しい。この場合、D は推定値が低いため、優れたヒューリスティックを作成します。

  2. 勝利状態までの「距離」がゲーム ピースの移動を伴うパズル。この場合、勝利状態に対して現在位置がずれているピースの数は、優れたヒューリスティックです。例としては、7 番目のゲストからの 8 ビショップの問題 (まだ最終的な位置にないビショップの数) と魔方陣問題 (すべてのピースの現在の位置から勝利状態での正しい位置までのマンハッタン距離の合計) があります。

于 2013-07-07T02:23:34.707 に答える