启发式函数背后的直觉加上示例

Question

我正在参加人工智能课程，并完成一些提供的期中练习，以便更好地理解材料并帮助准备初次考试。我觉得我很了解搜索，也很了解可受理性，但不太了解一致性，我知道这对很多人来说是一个麻烦点。我在这里查看了很多答案，坦率地说，它们对于真正确定直观的部分并没有多大帮助。 所以我更大的问题是要求对一致性本身进行解释，但我也有一个我不明白的期中考试中的一个小例子来帮助锚定解释。

现在对于这个问题，在第三个迷宫中，练习期中告诉我，吃豆人到每个盒子的距离的最小值，负1，是一致的。我实在不明白这是为什么。 （为了清楚起见，附上下面直接问题的图片）。

这是我对此的思考过程。一致性意味着当我们搜索树时，我们永远不会高估到达任何特定节点的成本，也不会高估从任何节点到达解决方案本身的成本。我的看法是，如果我们取吃豆人到盒子的最小距离，那么当我们将一个盒子推到按钮上时，吃豆人必须朝远离按钮上盒子的方向移动，朝向其中一个盒子。其他盒子。由于吃豆人最接近现在按钮上的盒子，启发式函数将告诉我们，随着我们最初离开，成本正在增加，尽管实际上情况并非如此。因此，在某些情况下，启发式方法实际上确实高估了节点的成本，对吧？要么我不理解一致性，要么我不理解这个例子，或者当然可能两者兼而有之。 所以我的问题是：

1. 为什么这个启发式实际上是一致的？
2. 为什么我的推理有缺陷？
3. 对于一致性来说，真正可靠的直觉是什么？ “实际上”保持一致是什么意思？可接纳性很容易凭直觉判断——这意味着我们永远不会错误地认为我们离目标比实际距离更远。例如，如果我尝试从休斯顿步行到达拉斯，我绝不会错误地认为达拉斯比实际距离更远，尽管我可以认为达拉斯比实际距离更近。从直觉上来说，一致性是什么？我知道三角不等式，但如果有人对我说“像我五岁（所以没有数学抽象能力）并试图从休斯顿步行到达拉斯一样向我解释这一点”，我将无法保持一致性，但完全能够受理。这让我很烦恼。我想要“对于不会做数学的五岁孩子”的答案，而不是“对于困惑的计算机科学学生”的答案。

Answer 1

一致的启发式意味着您无法通过走到相邻节点来找到较低的总成本估计。具体来说，如果您可以以成本 c 从 a->b 获得，那么您需要来自 a 的 h(a) <= h(b)+c. This transitively guarantees that no path，包括循环路径，可以提供较低的总成本估计。

为了评估问题中给出的启发式，请考虑从任何节点 a 到其任何邻居 b 的成本为 1。因此，如果我们始终有 h(a) <= h(b)+1, given that h(goal)=0.

，则启发式是一致的

由于吃豆人只能移动一格，并且只能移动 1 个盒子 1 个格，因此给定指标的所有选项最多可以更改 1，并且会保持一致，除了与目标状态。当迷宫 3 达到目标时，两个 max 选项都会突然从高值跳到 0。两个 min 选项是一致的。