啓發式功能水壺

Question

我在爬山算法水壺問題一個問題：

給定兩個水罐，其中一個可容納水和可容納的水Ÿ升而另一條X升，確定在一個壺中準確獲得D升水所需的步驟數。

從開始狀態，（X，Y）=（0,0），它可以產生一些州：

• （X，Y）=（0，Y）
  或
• （X，Y）=（X，0）

而且從這些狀態時，它可以產生其它直到即結束狀態是（X，d）或（d，Y）。

那麼，我可以估計這個問題的啓發函數嗎？如何知道哪種狀態比其他狀態更好？

謝謝大家。

Answer 1

將狀態空間中的每個狀態表示爲（x，y）本身。啓發函數：h（s）對於每個s =（x，y）= | x-D | + | y - D | （假設你想最小化h（。））

請認爲這只是一個貪婪的決定，假設如果其中一個水壺含有過多的水太多D這是一個很好的狀態！很明顯，對於目標狀態來說這是正確的，但它不能保證達到最佳解決方案，因爲它根本不是來自HC的！

爲什麼這個h（。）？因爲它是可以接受，你可以使用它（可能當你的老師要求）A *它會給你最佳答案。

---

考慮「爬山」算法存在以下問題，不要抱太大的期望：

• 山麓問題
  局部峯值吸引過程的注意力從試圖達到「頂「
• 高原問題
  區域平坦，所以很少有吸引程序去往另一條路徑[R
• 嶺問題
  每一步都下來雖然沒有在當地最低