algorithm - 如何为水壶定义启发式函数？

Question

我试图将水壶问题放入启发式函数中，但我发现了一些问题。

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

我不知道如何将它放入启发式函数中，而且我对状态的数量也有疑问。如果我承认这些 Action (从水龙头注满一个，将一个倒入下水道，然后从一个倒到另一个直到接收 jar 已满或倾倒 jar 为空)，则有 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)

但我也找到了这个问题的答案 ( Heuristic function for Water Jug )现在我很困惑。谁能给我解释一下？

max(estimate_from_parent - action_cost, estimate_from_this_node)

Answer 1

状态数和可达性:

您关于状态的理论数量是正确的(假设桶只能有整数加仑 - 否则它是无限的)。由于桶 X 可以容纳 6 种可能的加仑数，而桶 Y 可以容纳 4 种可能的加仑数，因此状态总数为 6*4=24。

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

启发式函数:

就启发式函数而言，您可能需要花点时间考虑一下您的目标。你想在桶 x 中装四加仑。所以你越接近桶 x 中有 4 加仑，你就越接近你的目标，你的启发式函数的值应该越低(因为它是一个估计成本)。那么，您的启发式函数的最低值应该出现在桶 x 中有四加仑时。您在此处提出的启发式函数 h(x,y) = (x * 5) + (y * 3) 在 (0,0) 处最低。由于这不是您的目标节点，因此这不太可能是一个好的启发式函数。

在考虑启发式函数时，找到使您的问题更难的约束条件然后放松它通常很有用。这有助于提出可接受且一致的启发式方法，因为您的启发式方法基本上是最佳案例估计。对于这个问题，一个相当大的限制是您只能向桶 x 中添加一定量的水(即桶 y 中的水量，或填充桶 x 所需的水量)。我们可以放宽此约束，基本上以 h(x,y) = |X-4|(链接帖子中讨论的启发式函数，适用于您的问题)结束。这绝对是可以接受和一致的，因为如果可能采取这样的步骤，它实际上是从该节点一步到达目标所花费的金额。如果您位于目标节点，它将等于 0。请注意，成本的计算方式对于使其成为有用的启发式方法至关重要。

这是否消除了您的困惑？