我在尝试将水壶问题转化为启发式函数时遇到了一些问题。

有两个水壶，一个可以装5加仑(x)，另一个可以装3加仑(y)。目标是(y,x)=(0,4)。

我无法弄清楚如何将其转化为启发式函数，同时我对状态数量也有疑问。如果我承认以下操作（从水龙头装满一个水壶，向排水口倒空一个水壶，以及从一个水壶向另一个水壶倒水，直到接收的水壶装满或倒水的水壶变空），则有15种可能的状态，但如果我考虑所有关于加仑数的可能性，则有24种可能性。这是正确的吗？

(0,0)

(3,0)(0,5)

(0,3)(3,5)(3,2)

(3,3) (0,2)

(1,5) (2,0)

(1,0) (2,5)

(0,1) (3,4)

(0,4)

我认为这个问题的启发式函数可以定义为：

h(x,y) = (x * 5) + (y * 3)

但我在一个问题（水壶的启发式函数）中也找到了这个答案，现在我很困惑。能有人向我解释一下吗？

max(estimate_from_parent – action_cost, estimate_from_this_node)

回答：

状态数量和可达性：

关于理论上的状态数量你是正确的（假设水桶只能装整数加仑的水 – 否则是无限的）。因为水桶X可以装6种可能的加仑数，而水桶Y可以装4种可能的加仑数，所以总的状态数是6*4=24。

从技术上讲，(3,1)也是可达的，在你找到解决方案后，所以有16种可能的状态。

启发式函数：

关于启发式函数，你可能需要花点时间思考你的目标。你希望在水桶x中有四加仑水。所以你离在水桶x中有四加仑水越近，你就越接近你的目标，你的启发式函数的值应该越低（因为它是一个估计的成本）。因此，当水桶x中有四加仑水时，你的启发式函数的值应该最低。你在这里提出的启发式函数，h(x,y) = (x * 5) + (y * 3)，在(0,0)时是最低的。由于这不是你的目标节点，这不太可能是一个好的启发式函数。

在思考启发式函数时，找到一个使你的问题变得更难的约束然后放宽它通常是有用的。这有助于提出一个可接受且一致的启发式函数，因为你的启发式函数基本上是一个最佳情况的估计。对于这个问题，一个相当大的约束是只能向水桶x中添加某些量的水（即水桶y中的量，或者填满水桶x所需的量）。我们可以放宽这个约束，基本上得到h(x,y) = |X-4|（在链接的帖子中讨论的启发式函数，适应你的问题）。这绝对是可接受且一致的，因为它有效地表示了从那个节点一步达到目标的成本，如果这样一步是可能的话。如果你在目标节点，它将等于0。请注意，你的成本计算方式对于使这个启发式函数有用至关重要。

这是否解除了你的困惑？