Berkeley AI class - 没有 mazeDistance 的 PacMan 食物启发式算法？
Berkeley AI class - PacMan food heuristic without mazeDistance?
我正在学习与 Berkeley 的 AI class 类似的 class，我正在尝试寻找 Q7 的 foodHeuristic（问题可以找到 here），但是我不允许使用 mazeDistance，因为它的实现使用扩展节点的 BFS。
我根本不知道如何找到这样的启发式方法。我试过了 - 曼哈顿到壁橱食物的距离，曼哈顿到最远食物的距离，加上剩下的任何食物量，曼哈顿到最远食物的距离 + 曼哈顿从最远食物到它的壁橱食物的距离..
有 mediumSearch，几乎到处都有食物，那么怎么可能有效地计算它呢？
有没有可能在没有 mazeDistance 的情况下打败 7000？
关于 foodHeuristic 的任何线索？
简介
好的，所以这不是一个完整的答案，因为我还没有实现它，所以我不知道它的性能如何。但是，我的方法基于以下几点：
- 注释“请确保在回答问题 7 之前完成问题 4，因为问题 7 建立在您对问题 4 的回答之上。”。所以以曼哈顿距离作为一致启发式的 A* 搜索是我们的基础。
- 事实是“如果您的启发式不一致，您将得不到信用”。
所以他们肯定会引导我们使用比曼哈顿距离更聪明的一致启发式进行 A* 搜索。
检查您的（有时不一致的）启发法
您的前两个启发式：“曼哈顿到最接近食物的距离”和“曼哈顿到最远食物的距离”绝对一致。
你的第三个启发式“添加到任何剩余的食物量”与第一个启发式一致但不是第二个（例如，如果直线走到最远的食物吃掉所有食物，那么你会结束-估算成本）。
你最后的启发式（“曼哈顿到最远食物的距离 + 曼哈顿从最远食物到它的壁橱食物的距离”）也是不一致的，原因是一样的：再一次，图片沿着直线走到最后一个颗粒会导致进食所有剩余的食物。
所以到目前为止，你最好的一致启发式是“曼哈顿到壁橱食物的距离”+（食物颗粒总数）- 1。我想知道：你需要多少个节点用这个启发式扩展？
更严格的启发式
因此，当我试图找到一致的启发式方法时，我通常会按照您所做的去做：从基本计算开始，然后添加缺失的因素 ，同时仍然保持一致。因此，例如，您的第一个启发式方法适用于一个颗粒，但不适用于多个颗粒。添加剩余食物颗粒的数量使其更紧密而不失一致性。
让我们找出这种启发式算法表现良好的情况，以及表现不佳的情况。如果我想象一个正方形的弹丸（没有墙），那么这种启发式非常好：我首先到达最近的墙部分，然后一次一个地吞噬这些弹丸（自从我旅行以来没有浪费移动一个圆圈）。如果它是颗粒的单一路径而不是正方形，那么我可能会大大低估（例如，最近的点是中间路径；在一个方向上进食需要返回），但我没有看到一种简单的建模方法这个。
回到正方形，如果我每隔一秒删除一个小球会怎样？估计会减半，但实际上成本是一样的！所以这是我们缺少的一个重要因素：连接组件的数量。
无论您如何进食，您都必须始终从一个连接的组件移动到另一个连接的组件（例如，想象多条断开连接的路径；我们吃一个，然后移动到下一个，吞噬那个并重复）。
所以我第一个推荐的启发式方法如下：
- 计算食物颗粒的连接成分数= C。（这个值可以随着你穿过迷宫而递增更新。每当你吃一个颗粒你可能会完成一个组件，所以C'= C - 1，或者你可以将一个组件分成多个组件，所以 C' = C + 1 或 C' = C + 2 或 C' = C + 3；只需从你当前位置的 4 个邻居做一个洪水填充）。
- 使用一致的启发式 (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)。注意两点：
- 为了保持一致，我们必须假设最大旅行费用是被跳过的费用，并且
- TravelCost(C_i) >= 2 根据定义，因此 TotalTravelCost >= (C-1)。 （如果只剩下一个连通分量，则 TotalTravelCost = C-1 = 0。）
因此，我们更严格的一致启发式将是 TotalTravelCost + (F - 1) + 曼哈顿到最近颗粒的距离。
这实现起来有点麻烦，而且肯定会使每个节点的评估速度变慢，所以我会亲自尝试实现我的第一个建议，看看它的表现如何，然后再继续这个。一些技巧可以使最后的启发式算法更快：
- TravelCost(C_i) 在您最后一步没有吃掉弹丸时不会改变。
- 当你吃一个颗粒时，你只需要更新你改变的组件C_i的TravelCost(C_i)，以及那些最接近的相邻组件是C_i的组件。
- 当您将一个组件拆分为多个组件（即 C' = C + 1 或 C' = C + 2 或 C' = C + 3）时，每个组件的 TravelCost 必须为 2。
我正在学习与 Berkeley 的 AI class 类似的 class，我正在尝试寻找 Q7 的 foodHeuristic（问题可以找到 here），但是我不允许使用 mazeDistance，因为它的实现使用扩展节点的 BFS。 我根本不知道如何找到这样的启发式方法。我试过了 - 曼哈顿到壁橱食物的距离，曼哈顿到最远食物的距离，加上剩下的任何食物量，曼哈顿到最远食物的距离 + 曼哈顿从最远食物到它的壁橱食物的距离..
有 mediumSearch，几乎到处都有食物，那么怎么可能有效地计算它呢？
有没有可能在没有 mazeDistance 的情况下打败 7000？
关于 foodHeuristic 的任何线索？
简介
好的，所以这不是一个完整的答案，因为我还没有实现它，所以我不知道它的性能如何。但是，我的方法基于以下几点：
- 注释“请确保在回答问题 7 之前完成问题 4，因为问题 7 建立在您对问题 4 的回答之上。”。所以以曼哈顿距离作为一致启发式的 A* 搜索是我们的基础。
- 事实是“如果您的启发式不一致，您将得不到信用”。
所以他们肯定会引导我们使用比曼哈顿距离更聪明的一致启发式进行 A* 搜索。
检查您的（有时不一致的）启发法
您的前两个启发式：“曼哈顿到最接近食物的距离”和“曼哈顿到最远食物的距离”绝对一致。
你的第三个启发式“添加到任何剩余的食物量”与第一个启发式一致但不是第二个（例如，如果直线走到最远的食物吃掉所有食物，那么你会结束-估算成本）。
你最后的启发式（“曼哈顿到最远食物的距离 + 曼哈顿从最远食物到它的壁橱食物的距离”）也是不一致的，原因是一样的：再一次，图片沿着直线走到最后一个颗粒会导致进食所有剩余的食物。
所以到目前为止，你最好的一致启发式是“曼哈顿到壁橱食物的距离”+（食物颗粒总数）- 1。我想知道：你需要多少个节点用这个启发式扩展？
更严格的启发式
因此，当我试图找到一致的启发式方法时，我通常会按照您所做的去做：从基本计算开始，然后添加缺失的因素 ，同时仍然保持一致。因此，例如，您的第一个启发式方法适用于一个颗粒，但不适用于多个颗粒。添加剩余食物颗粒的数量使其更紧密而不失一致性。
让我们找出这种启发式算法表现良好的情况，以及表现不佳的情况。如果我想象一个正方形的弹丸（没有墙），那么这种启发式非常好：我首先到达最近的墙部分，然后一次一个地吞噬这些弹丸（自从我旅行以来没有浪费移动一个圆圈）。如果它是颗粒的单一路径而不是正方形，那么我可能会大大低估（例如，最近的点是中间路径；在一个方向上进食需要返回），但我没有看到一种简单的建模方法这个。
回到正方形，如果我每隔一秒删除一个小球会怎样？估计会减半，但实际上成本是一样的！所以这是我们缺少的一个重要因素：连接组件的数量。
无论您如何进食，您都必须始终从一个连接的组件移动到另一个连接的组件（例如，想象多条断开连接的路径；我们吃一个，然后移动到下一个，吞噬那个并重复）。
所以我第一个推荐的启发式方法如下：
- 计算食物颗粒的连接成分数= C。（这个值可以随着你穿过迷宫而递增更新。每当你吃一个颗粒你可能会完成一个组件，所以C'= C - 1，或者你可以将一个组件分成多个组件，所以 C' = C + 1 或 C' = C + 2 或 C' = C + 3；只需从你当前位置的 4 个邻居做一个洪水填充）。
- 使用一致的启发式 (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)。注意两点：
- 为了保持一致，我们必须假设最大旅行费用是被跳过的费用，并且
- TravelCost(C_i) >= 2 根据定义，因此 TotalTravelCost >= (C-1)。 （如果只剩下一个连通分量，则 TotalTravelCost = C-1 = 0。）
因此，我们更严格的一致启发式将是 TotalTravelCost + (F - 1) + 曼哈顿到最近颗粒的距离。
这实现起来有点麻烦，而且肯定会使每个节点的评估速度变慢，所以我会亲自尝试实现我的第一个建议，看看它的表现如何，然后再继续这个。一些技巧可以使最后的启发式算法更快：
- TravelCost(C_i) 在您最后一步没有吃掉弹丸时不会改变。
- 当你吃一个颗粒时，你只需要更新你改变的组件C_i的TravelCost(C_i)，以及那些最接近的相邻组件是C_i的组件。
- 当您将一个组件拆分为多个组件（即 C' = C + 1 或 C' = C + 2 或 C' = C + 3）时，每个组件的 TravelCost 必须为 2。