伯克利人工智能课程 - PacMan 食物启发式没有迷宫距离？

Question

我正在学习与 Berkeley 的 AI 课程类似的课程，并且我正在尝试找到 Q7 的 foodHeuristic（问题可以在此处找到），但是我不允许使用 mazeDistance，因为它的实现使用 BFS，它扩展了节点。我根本不知道如何找到这样的启发式方法。我尝试过 - 曼哈顿到壁橱食物的距离，曼哈顿到最远食物的距离，加上剩余的食物量，曼哈顿到最远食物的距离+曼哈顿从最远食物到壁橱食物的距离。

媒体搜索几乎到处都有食物，那么如何才能有效地计算它呢？

没有 mazeDistance 是否有可能击败 7000？

有关于食物启发的线索吗？

Answer 1

介绍

好吧，这不是一个完整的答案，因为我还没有实现它，所以我不知道它是如何执行的。然而，我的方法基于以下几点：

1. 注释“请确保在解决问题 7 之前完成问题 4，因为问题 7 建立在您对问题 4 的答案之上。”。因此，以曼哈顿距离为一致启发式的 A* 搜索是我们的基础。
2. 事实上，“如果你的启发不一致，你将不会获得任何荣誉”。

因此，他们肯定会用比曼哈顿距离更聪明的一致启发式方法引导我们进行 A* 搜索。

检查你的（有时不一致的）启发法

您的前两个启发式：“曼哈顿到壁橱食物的距离”和“曼哈顿到最远食物的距离”绝对是一致的。

您的第三个启发式“添加到剩余的食物量中”与第一个启发式一致，但与第二个启发式不同（例如，如果沿直线走到最远的食物吃掉所有食物，那么您将高估成本） 。

由于同样的原因，你的最后一个启发式（“曼哈顿到最远食物的距离+曼哈顿从最远食物到壁橱食物的距离”）也是不一致的：同样，图片沿直线走到最后一个颗粒会导致吃掉所有剩余的食物。

因此，到目前为止，您最好的一致启发式是“曼哈顿到壁橱食物的距离”+（食物颗粒总数）- 1。我想知道：您必须使用此启发式扩展多少个节点？

更严格的启发式

因此，当我试图找到一致的启发法时，我通常会做你所做的事情：从基本计算开始，然后添加缺少的因素，同时仍然保持一致。例如，您的第一个启发式对于一个颗粒非常有用，但对于多个颗粒则不然。添加剩余食物颗粒的数量使其变得更紧，而不会失去稠度。

让我们找出这种启发式方法效果好的案例和效果不佳的案例。如果我想象一个正方形的颗粒（没有墙壁），那么这个启发式就非常好：我首先到达墙壁的最近部分，然后我一次吞掉一个颗粒（自从我在一个圆圈）。如果它是颗粒的单一路径而不是正方形，那么我可能会大大低估（例如，最近的点是路径的中间；朝一个方向吃东西需要返回），但我没有看到一种简单的建模方法这。

回到广场，如果我删除每一个第二个颗粒会怎么样？预估会减半，但实际上成本是一样的！因此，我们缺少一个重要因素：连接组件的数量。

无论你怎么吃，你都必须花费一次从一个连接的组件到另一个组件的移动（例如想象多个断开的路径；我们吃一个，然后移动到下一个，吞噬那个并重复）。

所以我推荐的第一个启发式如下：

1. 计算食物颗粒的连接成分数 = C。（这个值可以在你穿过迷宫时逐渐更新。每当你吃掉一个颗粒，你就可能吃完一个成分，所以 C' = C - 1，或者你可以除以组件分解为多个组件，因此 C' = C + 1 或 C' = C + 2 或 C' = C + 3；只需从当前位置的 4 个邻居进行洪水填充）。
2. 使用一致的启发式 (C - 1) + (F - 1) + 到最近颗粒的曼哈顿距离，其中 C 是成分数量，F 是食物颗粒数量。

这显然比您现有的启发式更严格。主要思想是捕捉颗粒之间的间隙。

更严格的启发式

现在，连接的组件之间可能存在很大的间隙（例如，仅将每 N 个颗粒保留在正方形中）。知道我们将访问组件的顺序太复杂了，但是，除了最后访问的组件之外，我们至少必须移动到最近的邻居组件。

因此，假设 TravelCost(C_i) 是从颗粒连通分量 C_i 到其最近邻连通分量（例如 C_j）的曼哈顿距离。那么 TotalTravelCost 将为 sum(i=1..n)(TravelCost(C_i) - 1) - max(TravelCost(C_i) - 1, i=1..n)。注意两件事：

1. 为了保持一致，我们必须假设最大旅行成本是被跳过的成本，并且
2. 根据定义，TravelCost(C_i) >= 2，因此 TotalTravelCost >= (C-1)。（如果只剩下一个连接的组件，则 TotalTravelCost = C-1 = 0。）

因此，我们更严格的一致启发式将是 TotalTravelCost + (F - 1) + 到最近颗粒的曼哈顿距离。

实现起来有点困难，并且肯定会使每个节点的评估速度变慢，因此我个人会尝试实现我的第一个建议，并在继续之前看看它的执行情况。有几个技巧可以让最后一个启发式更快：

• 当您的最后一步没有吃掉颗粒时，TravelCost(C_i) 不会改变。
• 当你吃一颗颗粒时，你只需要更新你改变的分量C_i以及那些最邻近分量是C_i的分量的TravelCost(C_i)。
• 当您将一个组件拆分为多个组件（即 C' = C + 1 或 C' = C + 2 或 C' = C + 3）时，每个组件的 TravelCost 必须为 2。

解释启发式一致性

根据下面的评论，我将详细说明上述启发式的一致性。请记住，一致性意味着我们永远不会高估成本。

假设我们有一个解决方案，它按顺序列出了我们访问的位置，例如 L_0、L_1、L_2、...、L_n，其中 L_0 是我们的起始位置，L_n 是我们的最终位置（即当我们吃掉最后一个颗粒时）。请注意，在每个位置，我们要么吃颗粒，要么在颗粒之间移动（即在没有颗粒的位置），并且该解决方案的最终成本为 n。

现在在某个时刻我们必须吃掉最远的颗粒。也就是说，至少存在一个L_i来指定最远颗粒的位置。好吧，我们可以得出结论，i >= 到最远颗粒的曼哈顿距离，因为显然我们无法从 L_0 更快地到达这个位置（因为每个 L_i 都与 L_{i-1} 相邻）。由于 n >= i，总成本必须至少是到最远颗粒的曼哈顿距离，因此最远距离显然是一致的。

产生一致启发的另一种方法是考虑我们什么时候吃第一个颗粒。这种情况最早发生的时间是 L_i，其中 i >= 到最近颗粒的曼哈顿距离。吃完第一个颗粒后，我们还必须吃剩下的F-1个剩余的食物颗粒。由于每个位置最多有一个食物颗粒，因此这需要至少 F - 1 个额外步骤。因此我们可以得出结论 n >= (曼哈顿到最近颗粒的距离) + (F - 1)，其中 F 是食物颗粒的数量。因此，我们有另一个一致的启发式。

[稍后我将返回解释更复杂的启发式，但希望这会有所帮助。]