A *ヒューリスティック、過大評価/過小評価？

StackOverflow https://stackoverflow.com/questions/1012691

質問

過大評価/過小評価という用語について混乱しています。 A *アルゴリズムがどのように機能するかは完全にわかっていますが、過大評価または過小評価するヒューリスティックを使用した場合の効果は不明です。

直接の鳥瞰図の二乗をとると過大評価されますか？そして、なぜアルゴリズムが正しくないのでしょうか？同じヒューリスティックがすべてのノードに使用されます。

直接的なバードビューラインの平方根を取るとき、過小評価されていますか？そして、なぜアルゴリズムはまだ正しいのですか？

わかりやすく説明している記事が見つからないので、ここの誰かが良い説明を持っていることを願っています。

役に立ちましたか？

解決

ヒューリスティックの推定値が実際の最終パスコストよりも高い場合、過大評価しています。低くなると過小評価します（過小評価する必要はありません。過大評価しないでください。正しい推定値は問題ありません）。グラフのエッジコストがすべて1の場合、与えられた例は過大評価と過小評価を提供しますが、単純な座標距離はデカルト空間でも桃色になります。

過大評価しても、アルゴリズムが正確に「不正」になるわけではありません。つまり、A *が最適な動作を保証するための条件である許容可能なヒューリスティックがなくなったことです。許容できないヒューリスティックを使用すると、アルゴリズムは、無視すべきパスを調べ、それらを探索するために準最適なパスを見つける可能性のある余分な作業を大量に行うことができます。それが実際に発生するかどうかは、問題のスペースによって異なります。これは、パスコストが推定コストと「結合していない」ために発生します。これにより、アルゴリズムは本質的に、どのパスが他のパスよりも優れているかというアイデアを台無しにします。

見つけたかどうかはわかりませんが、ウィキペディアをご覧ください。 A *の記事。主にGoogleに言及（およびリンク）しているのは、Googleにとってほとんど不可能だからです。

他のヒント

Wikipedia A *の記事から、アルゴリズムの説明の関連部分は次のとおりです。

  

アルゴリズムは、目標ノードがキュー内のどのノードよりも f 値が低くなるまで（またはキューが空になるまで）続きます。

重要な考え方は、パスの総コストが目標への既知のパスのコストを超えることがわかった後、A *は過小評価で目標への潜在的なパスの探索を停止することです。パスのコストの見積もりは常にパスの実際のコスト以下であるため、A *は、見積もりコストが既知のパスの合計コストを超えるとすぐにパスを破棄できます。

過大評価の場合、A *は、実際の既知の目標パスよりも実際のコストは低いが推定コストが高いパスが存在する可能性があるため、潜在的なパスの探索を停止できるかどうかはわかりません。

私が知っている限りでは、最短経路を見つけられるように、通常は過小評価する必要があります。過大評価することで回答をすばやく見つけることができますが、最短経路を見つけることができない場合があります。したがって、過大評価が「不正」であるのに対し、過小評価は依然として最善の解決策を提供できるのです。

バードビューラインについての洞察を提供できないことをごめんなさい...

簡単な回答

@chaosの答えは少し誤解を招くようなものです（強調する必要があります）

  

過大評価しても、アルゴリズムが正確に「不正」になるわけではありません。つまり、許容可能なヒューリスティックがなくなったことです。これは、A *が最適な動作を保証するための条件です。許容できないヒューリスティックにより、アルゴリズムは大量の余分な作業を行う ことができます

@AlbertoPLが示唆しているように

  

過大評価することで回答をすばやく見つけることができますが、最短経路を見つけることができない場合があります。

最終的に（数学的最適以外に）、最適なソリューションは、コンピューティングリソース、ランタイム、特別な種類の「マップ」/状態空間などを考慮するかどうかに大きく依存します

ロングアンサー

例として、早めに開始することによる時間の優位性は最短経路をとるがこれを計算するのを長く待つことによる時間の優位性よりも大きいため、ロボットが過大評価のヒューリスティックを使用してターゲットにより速くなるリアルタイムアプリケーションを考えることができますソリューション。

より良い印象を与えるために、Pythonですばやく作成した模範的な結果をいくつか共有します。結果は同じA *アルゴリズムに由来し、ヒューリスティックのみが異なります。各ノード（グリッドセル）は、壁を除く8つのすべての隣接ノードにエッジを持っています。対角エッジのコストはsqrt（2）= 1.41

最初の図は、単純な例の場合に返されたアルゴリズムのパスを示しています。過大評価のヒューリスティック（赤とシアン）から最適ではないパスを確認できます。一方、複数の最適なパス（青、黄、緑）があり、どのパスが最初に見つかるかはヒューリスティックに依存します。

ターゲットに到達すると、さまざまな画像に展開されたすべてのノードが表示されます。色は、このノードを使用した推定パスコストを示します（開始からこのノードまでの「既に使用されている」パスも考慮します。数学的には、これまでのコストにこのノードのヒューリスティックを加えたものです）。アルゴリズムはいつでも、推定総コストが最小のノードを拡張します（前述）。

Paths

1。ゼロ（青）

  • ダイクストラアルゴリズムに対応
  • 展開されたノード：2685
  • パスの長さ：89.669

Zero

2。カラスが飛ぶとき（黄色）

3。理想的（緑）

  • 障害物のない最短経路（8つの指示に従う場合）
  • 過大評価せずに可能な限り高い推定値（したがって「理想的な」）
  • 展開されたノード：854
  • パスの長さ：89.669
  • https://i.stack.imgur.com/VqMtF.png

4。マンハッタン（赤）

  • 障害物のない最短経路（斜めに移動しない場合、言い換えると、「斜めに移動する」コストは2と推定されます）
  • 過大評価
  • 展開されたノード：562
  • パスの長さ：92.840
  • https://i.stack.imgur.com/gD9t4.png

5。カラスが10回飛ぶにつれて（シアン）

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top