ヒューリスティックが常に過小評価するときに、A* アルゴリズムが常に目標状態への最適なパスを提供する理由は理解していますが、その正式な証明を作成することはできません。
私が理解している限り、各パスが深くなるにつれて、f(n)100% 正確な目標状態までの精度が向上します。また、見積もりは実際のコストよりも少ないため、誤ったパスが無視されることはありません。したがって、最適なパスにつながります。しかし、その証拠をどのように作成すればよいでしょうか。
質問する
20831 次
2 に答える
6
証明の主な考え方は、A* がパスを見つけるとき、他の可能なパスの推定値よりも低い推定値を持つパスを見つけたということです。見積もりは楽観的であるため、他のパスは無視しても問題ありません。
また、A* は次の 2 つの条件が満たされた場合にのみ最適です。
コストを過大評価することはないため、ヒューリスティックは許容されます。
ヒューリスティックは単調です。つまり、h(n i ) < h(n i + 1 )の場合、real-cost(n i ) < real-cost(n i + 1 )です。
反対のことを仮定し、含意を拡張することで、最適性が正しいことを証明できます。
A* によって与えられるパスが、許容できる単調なヒューリスティックでは最適ではないと仮定し、それが含意の観点から何を意味するかを考えます (すぐに矛盾に到達することに気付くでしょう)。 .
このことから、元の仮定が間違っていたと結論付けることができます。つまり、A* は上記の条件で最適です。QED
于 2012-04-17T17:22:00.620 に答える
3
最適なパスを完成させる最後のステップを考えてみましょう。
なぜ A* はその道を選ばなければならないのでしょうか? あるいは、別の言い方をすれば、なぜ A* は目標に到達する次善の経路を選択することを避けなければならないのでしょうか?
ヒント: これが、ヒューリスティックが許容可能である必要がある理由です。パスを完成させない限り、次善のパスを選択しても問題ないことに注意してください (なぜですか?)。
これにより、証明を作成する方法についてある程度のアイデアが得られるはずです。
于 2012-04-17T17:17:56.953 に答える