Tip:
Highlight text to annotate it
X
さて、直感的にではありますが理由を説明しましょう。
なぜ楽観的ヒューリスティック関数 h が最小コスト経路を見つけるのでしょう。
処理を停止したとき、A はコスト c の経路 p を返します。
c は実際のコストでもあります。
ゴールにおける h 要素はゼロだからです。
従って、関数 f で見積もった総コストが経路コストです。
さて、フロンティアの中の他の全ての経路は
c よりも大きな見積もりコストを持っています。
我々はコストの低い順にフロンティアを探索しています。
h が楽観的なら、見積もりコストは
実際のコストより小さくなります。
つまり経路 p のコストは、フロンティア中のどの経路の
実際のコストよりも小さいのです。
フロンティアを超える全ての経路は
それよりも大きなコストを持ちます。
ステップコストは常に 0 以上だからです。
従って、経路 p は確実に最小コスト経路です。
さて、ここでは木探索のみを
議論していますが
グラフ探索ではもう少々複雑な議論になります。
とはいえ、基本的には一緒です。