h5 =（h1 + h2 + h3）/ 3是否可以接受？

Question

我對啓發式函數的「數學」無菌感到非常難過。我今天在AI課上夢到了3分鐘，我錯過了解釋。有人可以向我解釋，如果啓發式功能可以接受，我可以如何計算？我發佈了這一個（是h5 =（h1 + h2 + h3）/ 3可以接受嗎？）但是說實話，我不一定是這個問題。我只是通過例子更好地理解。

另外，我有「AI：現代方法」書，但我找不到一個例子。如果你知道我能找到哪一個，我會很感激。

Answer 1

首先，我們記得，如果啓發函數永遠不會高估實現目標的成本，那麼它就是可接受的。這是什麼意思？

總之這意味着，如果一個啓發式函數的狀態x返回一個值h有與x更低的成本沒有真正的溶液。例如，對於尋路，當前點與目的地之間的歐式距離是可接受的，因爲沒有路徑可以縮短成直線！換句話說，可接受的啓發式是總是樂觀。

現在，我們可以回到您的問題。我們有三種可接受的啓發式方法h1,h2和h3，我們希望找出這三個函數的平均值是否可接受。現在我們可以撥打X(s)從狀態s到目的地（換句話說就是最優解決方案的成本）的最佳可能成本。 X的價值顯然是未知的，但它是有用的。

因爲h1，h2和h3是容許的，我們知道，對於任何國家s：

• h1(s) < X(s)（記住：H1從來沒有高估性價比最優）
• h2(s) < X(s)
• h3(s) < X(s)

然後，因爲h5是我們知道的其他三個函數的平均值，對於每個狀態，它都在min(h1(s),h2(s),h3(s))和max(h1(s),h2(s),h3(s))之間。因此，我們可以說，每個國家s：

h5(s) <= max(h1(s),h2(s),h3(s)) <= X(s) 

所以也h5受理。