algorithm - 水壶的启发式函数

Question

我在爬山算法中遇到了水壶问题的问题：

给定两个水壶，其中一个可以容纳 X 升水，另一个可以容纳 Y 升水，确定在其中一个水壶中准确获得 D 升水所需的步骤数。

从开始状态，(X,Y) = (0,0)，它可以产生一些状态：

• (X,Y) = (0,Y)
  或
• (X,Y) = (X,0)

从这些状态中，它可以生成其他状态，直到最终状态为 (X,D) 或 (D,Y)。

那么，我可以估计这个问题的启发式函数吗？如何知道哪个状态比其他状态更好？

谢谢大家。

Answer 1

将状态空间中的每个状态表示为 (x,y) 本身。

启发式函数：每个 s = (x,y) = |xD| 的 h(s) + |y - D| （假设你想最小化 h(.) ）

请考虑这只是一个贪婪的决定，它假设如果其中一个水罐中的水量太近 D 这是一个很好的状态！显然，这对于目标状态是正确的，但它不能保证达到最佳解决方案，因为它根本不是 HC 所期望的！

为什么这个 h(.)？因为它是可接受的，您可以将它（可能在您的老师要求时）用于A*，它会给您最佳答案。

---

考虑到“爬山”算法的以下问题，不要期望太高：

• 山麓问题
  局部山峰吸引程序的注意力远离试图到达“顶部”</li>
• 高原问题
  区域平坦，因此几乎没有什么可以将程序吸引到一条路径而不是另一条路径
• 岭问题
  每一步都在下降，尽管不是局部最小值