啓發式被認爲是可接受的是什麼意思？

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

一個可接受的啓發式只是一個，如你所說，高估到目標的距離。允許低估，你給出的兩個例子確實是有效的，可接受的啓發式。

通常，在我們正在討論的這些啓發式算法（例如A *）中，如果啓發式算法儘可能接近真值，那麼它是有益的。所以，就像你已經注意到自己一樣，對於所有節點而言啓發式值爲0的最後一個例子不會很有用。通常，您希望啓發式值儘可能接近真實值，同時仍然可以接受（確保他們永不高估）