過大評価/過小評価という用語について混乱しています。A *アルゴリズムがどのように機能するかは完全に理解できますが、過大評価または過小評価するヒューリスティックを使用した場合の影響についてはよくわかりません。
あなたが直接の鳥の視点の線の二乗を取るとき、過大評価はありますか？そして、なぜそれがアルゴリズムを不正確にするのでしょうか？すべてのノードに同じヒューリスティックが使用されます。
直接バードビューラインの平方根を取るとき、過小評価されていますか？そして、なぜアルゴリズムはまだ正しいのですか？
わかりやすく説明している記事が見つからないので、ここの誰かが良い説明をしてくれることを願っています。
ウィキペディアA*の記事によると、アルゴリズムの説明の関連部分は次のとおりです。
アルゴリズムは、ゴールノードのf値がキュー内のどのノードよりも低くなるまで（またはキューが空になるまで）続行されます。
重要なアイデアは、過小評価では、パスの総コストが目標への既知のパスのコストを超えることがわかった場合にのみ、A*が目標への潜在的なパスの探索を停止するということです。パスのコストの見積もりは常にパスの実際のコスト以下であるため、A *は、見積もりされたコストが既知のパスの合計コストを超えるとすぐにパスを破棄できます。
過大評価すると、A *は、実際のコストは低いが推定コストが現在最もよく知られている目標へのパスよりも高いパスが存在する可能性があるため、潜在的なパスの探索をいつ停止できるかわかりません。
A* が正しく機能する (ただのソリューションではなく常に「最適な」ソリューションを見つける) ためには、推定関数がoptimisticである必要があります。
ここでの楽観主義とは、あなたの期待が常に現実よりも優れていることを意味します。
楽観主義者は、最終的には失望するかもしれない多くのことを試みますが、すべての良い機会を見つけます。
悲観主義者は悪い結果を期待し、多くのことを試みません。このため、彼らはいくつかの絶好の機会を逃す可能性があります。
したがって、A* にとって楽観的であることは、常にコストを過小評価することを意味します (つまり、「おそらくそれほど遠くない」)。そうすれば、道を見つけた後でも、いくつかの未踏のオプションにワクワクするかもしれません。つまり、最初の解決策にとどまらず、他の解決策を試すことになります。ほとんどはおそらくがっかりするでしょう (良くなるわけではありません) が、常に最善の解決策を見つけることが保証されます。もちろん、より多くのオプションを試すには、より多くの作業 (時間) がかかります。
悲観的なA * は、常にコストを過大評価します (たとえば、「そのオプションはおそらくかなり悪い」)。解決策が見つかり、パスの真のコストがわかると、他のすべてのパスはより悪いように見え (見積もりは常に現実よりも悪いため)、ゴールが見つかると、別の方法を試みることはありません。
最も効果的な A* は、決して過小評価しないものですが、完全にまたはわずかに楽観的に過大評価するものです。そうすれば、あなたは素朴ではなく、悪い選択肢をたくさん試してしまいます。
誰にとっても素敵なレッスンです。常に少し楽観的に！
私の知る限り、最短経路を見つけられるように、通常は過小評価する必要があります。過大評価することでより早く答えを見つけることができますが、最短経路を見つけることができない場合があります。したがって、過大評価が「不正確」であるのに対し、過小評価は依然として最良の解決策を提供できるのです。
バードビューラインについての洞察を提供できなくて申し訳ありません...