当初始位置未知时，迷宫中的允许启发式算法

Question

这是伯克利人工智能课程作业的一部分。由于它现在不活跃，我无法从导师那里得到帮助，因此我会向社区提出问题。

问题：

现在是晚上，你控制着一只昆虫。你知道迷宫，但你不知道昆虫会从什么方格开始。您必须提出一个搜索问题，其解决方案是一个通用的操作序列，这样，在执行这些操作之后，昆虫将位于出口广场上，而不管初始位置如何。昆虫无意识地执行这些动作，不知道它的动作是否成功:如果它使用一个动作将它移动到一个阻塞的方向，它就会停留在它所处的地方。

问题是，当不知道初始位置时，下列哪一种是迷宫中允许的启发式：

( A)昆虫可能位于的可能地点的总数。

( B)从昆虫可能在的每一个可能的位置到目标的最大曼哈顿距离。

( C)从昆虫可能在的每一个可能的位置到目标的最小曼哈顿距离。

答案似乎都是(B)和(C)。我无法理解(B)是正确的答案。在我看来，(B)将大于达到目标状态的实际成本(如果我离目标更近-当然在这一点上是未知的)，因此不应该被接受。

在这种情况下，有谁能帮我解释为什么曼哈顿离每个可能的地点的最大距离是允许的启发式的？

Answer 1

除非昆虫总是能从迷宫中的任何地方直接移动到目标状态，否则你可以轻微地表明A和B都是不可接受的。假设昆虫离目标有一个动作是可能的，任何计算出大于1的启发式都是不可接受的。如果任何职位需要2次调动，B将评估为大于1，因此不可接受。