algorithm - Water Jug 的启发式函数

Question

我在 Water Jug 问题的爬山算法中遇到问题:

Given two jugs, one of which can accommodate X liters of water and the other which can accommodate Y liters of water, determine the number of steps required to obtain exactly D liters of water in one of the jugs.

从起始状态，(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(.) )

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

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

---

考虑到“爬山”算法存在以下问题，不要抱太大期望:

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