这是 Berkeley AI course 中家庭作业的一部分 | .由于它现在不活跃,我无法从讲师那里得到帮助,因此向社区提问。
问题:
现在是晚上,您控制着一只昆虫。你知道迷宫,但你不知道昆虫将从哪个方格开始。你必须提出一个搜索问题,其解决方案是一个通用的 Action 序列,这样,在执行这些 Action 后,昆虫将在导出方格上,无论初始位置如何。昆虫无意识地执行这些 Action ,并且不知道它的移动是否成功:如果它使用一个会使其向受阻方向移动的 Action ,它会留在原地。
问题是当初始位置未知时,以下哪些是迷宫中可接受的启发式:
A) 昆虫可能存在的位置总数。
B) 从昆虫可能存在的每个可能位置到目标的最大曼哈顿距离。
C) 从昆虫可能存在的每个可能位置到目标的最小曼哈顿距离。
似乎答案是 (B) 和 (C)。无法理解 (B) 是正确答案。在我看来,(B) 将大于达到目标状态的实际成本(如果我更接近目标,当然这在这一点上是未知的)因此不应该被接受。
任何人都可以帮助我推理为什么在这种情况下距每个可能位置的最大曼哈顿距离是可接受的启发式?
最佳答案
除非昆虫总是可以从迷宫中的任何地方直接移动到目标状态,否则您可以简单地表明 A 和 B 都是 Not Acceptable 。假设昆虫有可能距离目标 1 个 Action ,任何评估大于 1 的启发式都是 Not Acceptable 。如果任何位置需要 2 步,B 将评估为高于 1,因此 Not Acceptable 。
关于algorithm - 当初始位置未知时,迷宫中可接受的启发式算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35643392/