A* 搜索中水壶问题的启发式函数

Question

我对启发式价值有疑问。所以，这就是我的难题：

volume of the 3 jugs = (10,6,5) initial state = (10,0,0) goal state = (8,3,0)

我选择使用 A* 搜索来搜索此谜题。是不是类似于

h(x,y,z)=(x*a)+(y*b)+(z*c)

，因为 x y z 是每个罐子中的水的体积，而 a b c 是罐子是否是空的。如果为空则等于0，如果不为空则等于1。因为我在通过互联网搜索时感到困惑。你们能帮我指导一下吗？我也是人工智能新手。谢谢。

Answer 1

A* 最基本的启发是，不要遵循导致重复状态的分支。您保留所有先前状态的集合，并且如果集合中已存在下一个状态，则不遵循分支。

对于您的具体问题，可能的启发式函数可能会采用您的下一个“状态”（罐子的体积）并减去“目标”状态，并根据您的下一个状态与目标的接近程度返回增量分数。该特定问题的每个独特状态最多有 6 个分支，因此您可以选择遵循增量分数最低的分支。

h(state)  = dot(abs(state - goal), 1 / volume)

Answer 2

您提出的启发式函数，h(x,y,z) = (xa) + (yb) + (z*c)，其中 x、y、z 代表每个水壶中的水体积，a、b、c表示水罐是否为空（0 为空，1 为非空），是一种有效但简单化的启发式方法。

虽然您提出的启发式函数在技术上是正确的，并且可以通过考虑每个罐子中的水量以及它们是否为空来引导搜索过程走向目标状态，但它可能不如其他更常用的启发式方法那么有效或高效对于这个具体问题。

对于水壶问题，一种更常见且有效的启发式方法是计算每个水壶的当前体积与目标体积之间的差值之和。例如，h(x,y,z) = |x-8| + |y-3| + |z-0|将是一个更标准的选择，因为它直接测量每个壶距其目标体积的距离。

我检查了本关于“水壶问题”的指南，并从其他来源进行了检查。