ヒューリスティックが容認されるとはどういう意味ですか？

Question

私は、検索アルゴリズムの許容可能なヒューリスティックは、ゴールへの最短経路を決して過大評価するものではないと言われてきました。しかし、非ゴール状態ノードに0のヒューリスティック値を持たせることは有効ですか、あるいはゴール状態のみが0ヒューリスティック値を持つことができるという追加許容ルールです。次のように

例えばノードと目標状態Dとの間の最短経路である：

A = 5 
B = 4 
C = 3 
D = 0 

次のヒューリスティックが有効になります：

A = 4 
B = 4 
C = 0 
D = 0 

このヒューリスティックも有効だろう（一方また役に立たない）

A = 0 
B = 0 
C = 0 
D = 0 

Answer 1

許容ヒューリスティックは、あなたが言ったように、過大評価目標までの距離。 は、を過小評価することが許されています。あなたが与えた2つの例は、実際には有効な許容ヒューリスティックです。

一般に、これらのヒューリスティック（例えばA *）について説明しているアルゴリズムの種類では、ヒューリスティックが可能な限り真実に近い場合は有益です。だから、すでに気づいたように、すべてのノードのヒューリスティックな値が0である最後の例はあまり役に立たないでしょう。一般的には、ヒューリスティックな値を可能な限り真実に近いものにしたい（は絶対にを過大評価してください）