23

除了 A*、BFS、DFS 等，Pacman 中常用的其他好的寻路算法/启发式算法还有哪些？如果 pacman 可以找到不止一种水果，我认为我提到的那些不会起作用。

我需要一些好的寻路算法，PacMan 可以使用这些算法以尽可能少的步数完成迷宫。我试图四处寻找指导方针，但到目前为止还没有运气。到处都提到了曼哈顿距离的 A*，但它只适用于只有一个（或两个？或者最多几个？）水果的迷宫。

顺便说一句，为了简单起见，假设周围没有鬼魂。

原始 PacMan 问题的一些示例： First , Second和Third

4

10 回答 10

20

如果您知道迷宫的外观，启发式对我有用：

  1. 在迷宫中找到两个目前最远的水果之间的真实距离——我们称之为x。
  2. 找到从当前 Pacman 位置到前两个水果中较近的位置的真实距离——我们称之为y.

那么，答案就是：x + y。

请注意，真正的距离不是曼哈顿的距离，而是real迷宫中的距离——你可以计算出来（如果你愿意，甚至可以预先计算），因为你知道迷宫的外观（你知道所有的墙壁，......）。此信息（迷宫中某些两点之间的实际距离）是静态的，因为墙壁不会改变。

这个x + y公式的解释可能是这样的：

  • x- 无论哪种方式，你都必须走这段距离，至少在最后
  • y- 当你在最远的两个水果中的一些时，最好收集靠近它的食物，这样你就不必回去了

如果您作为 Berkeley AI 类项目的一部分来解决这个问题，为了计算两点之间的实际距离，您可以使用mazeDistance(pos1, pos2, gameState)已经实现并正在使用您的 bfs 实现的函数。此外，至少对于他们的测试用例，这种启发式是可接受且一致的。顺便说一句，通过这种启发式方法，我设法在trickySearch迷宫中仅扩展了 376 个节点。

于 2016-04-04T13:35:43.513 回答
15

您的评论说您正在寻找最短路径。这个问题是平面图上TSP的变体，因此是NP-Hard。

可能的启发式函数A*可以解决问题但不可接受[因此不能保证找到的路径是最优的]：

从所有水果到代理的曼哈顿距离之和。

您也可以使用可允许的启发式， of #fruits- 但这需要很长时间。

如果您正在寻找最佳选择，那么 - 这很难。您可以尝试所有水果的排列，并检查您需要旅行的总距离。这个解决方案是水果数量的因子，如果它大于 20 - 使用天真的蛮力 - 将花费太长时间。您可以通过将问题减少到 TSP以某种方式使其变得更好，并使用动态编程解决方案（也是指数的）或 TSP 的一些启发式解决方案。

还可以改进不可允许的启发式解决方案以提供一种随时算法：

A*以递减的启发式函数迭代运行：h(v) = h'(v) / m，其中h'是 A* 的最后一次迭代的启发式函数，并且m > 1. 这保证了在某些时候，您的启发式函数h将是可接受的 - 并且找到的解决方案将是最佳的。然而，每次迭代预计会比前一次花费更长的时间[指数更长..]

于 2012-04-03T14:23:21.190 回答
8

我找到了最近的近似食物（使用曼哈顿距离），但为了我的启发，我使用了从我的位置到最近的食物的实际距离。为此，我为所有与我的位置或最近的食物点不共享行或列的食物点添加了 1。

因为与我的位置或最近的食物位置共享行或列的食物点会在从我的位置到最近的食物时被吃掉，我已经在我在第二行中提到的实际距离中计算了这个成本。

所以，简而言之： 启发式 = mazeDistance（我的位置，估计最近的食物）+ 遗漏的点

这是可以接受的并且是一致的。有了这个，我扩展了 5500 个节点并在 FoodHeuristic 上获得了 5/4。 https://github.com/sukriterma1996/Intro-to-AI-course

于 2016-08-14T19:55:14.890 回答
5

我知道这已经过时了，但可能还有很多其他人希望解决这个问题（这是伯克利免费 AI 课程的一部分）。有很多蛮力建议，所以我将提供一个相当简单的建议，它非常接近并且可以接受：

  1. 找到最近的水果
  2. 从剩余水果列表中删除该水果并将距离添加到总数中
  3. 找到离这个水果最近的水果
  4. 返回第 2 步并重复，直到没有更多水果
  5. 返回总计

编辑：先前声称这是一个可接受的启发式方法是错误的。对不起！

于 2016-02-21T00:47:34.980 回答
3

您可以在合理大小的迷宫中对少量水果进行暴力破解。

  • 为迷宫中的每片水果创建一个带有节点的图形。
  • 使用 A* 或类似方法找出每对水果之间的距离。（您需要运行 A* 才能获得水果O(n^2)之间的所有成对距离。）n
  • 将图中的节点（水果）与按距离加权的边连接起来。
  • 通过蛮力找到图中最便宜的循环（至少访问所有节点一次）。在完整图表上查看 最便宜的成本遍历。
于 2012-04-03T14:18:28.790 回答
2

我找到了两个解决方案。

第一个是上面 Antonio Juric 的解决方案，它计算了一个出色的启发式算法。但是，这使用了多次调用 BFS() 的 mazeDistance()。这使得计算速度非常慢，类似于使用 UCS 解决问题，然后使用您的解决方案使用 A* 再次解决它。

My other solution, which checks 8475 nodes for me in trickySearch (but is twice as fast as the first solution), is as follows:

Let pos = the pacman's current position Let near = the coordinates of the closest piece of food by manhattan distance. Let MHD(a,b) = the Manhattan distance between a and b. Let far = the piece of food with maximum MHD(far,near).

The heuristic is calculated to be MHD(pos,near) + MHD(near,far). This is admissible and consistent. It is not as good of a heuristic, but it's much faster to calculate.

于 2021-10-05T16:56:21.310 回答
1

对于吃掉所有点的问题，我使用启发式值作为从所有食物点到当前 Pacman 位置的所有曼哈顿距离的最大值。这是可以接受的，因为吃豆人至少需要走这么远的距离才能到达目标点。它也是一致的，因为从单点开始的曼哈顿距离启发式总是一致的。它在棘手的搜索问题中扩展了 9551 个搜索节点。

对于角落食物问题，使用启发式算法作为 Pacman 中第一个最接近食物的总和。将 Pacman 重新定位到这个食物位置，然后重复上一步，直到所有食物颗粒都被吃掉。这是一种贪婪的方法，它不需要是可接受的和一致的，但这是一个特殊的场景，通过考虑所有情况可以证明这种启发式是可接受的和一致的。它在中等搜索问题中扩展了 485 个节点。

于 2020-03-18T07:52:50.103 回答
0

如果您想减少扩展的节点数量并且不关心运行时间，我建议使用最小生成树，边缘的成本应该是 mazeDistance 并使用优先队列，每次将节点添加到访问节点时，寻找距离刚刚添加的节点最近的节点，然后将其添加到访问节点，直到所有食物节点都添加到访问节点中。如果你做的是人工智能课程问题，扩展的节点应该很低。

于 2016-09-16T02:23:15.400 回答
0

假设这是针对伯克利 AI 项目：

在一般情况下，找到访问每个点的最短路径是 NP 难的。但是，这并不意味着在实践中很难。原因是因为有固定参数可处理的算法，并且提供的 Pacman 迷宫属于易于求解的图的情况。

特别是，对于任何给定的分支宽度，最短路径可以通过动态规划的简单应用在图大小的时间多项式中找到（但在图的分支宽度中是指数的）。这并不违反 NP-hardness，因为任意图可以具有较大的分支宽度，但这意味着如果您只关心具有低分支宽度的图，则可以有效地解决问题。提供的 Pacman 迷宫连接性较差，因此分支宽度较低。

有关更多详细信息，请参阅此帖子。

于 2017-11-29T04:30:36.863 回答
-1

在给定的游戏状态下，比如说md(x)从 pacman 到 node 的曼哈顿距离x，考虑minmd(X)作为一个函数，它为 all in返回xminst 。让我们成为 pacman 剩下的食物。md(xmin)<=md(x)xXX

比想一想 - 如果你考虑一个没有墙壁的 pacman 世界的放松，pacman 不能走少于md(xmin)去哪里xmin=minmd(X)吃水果的地方，然后（在 pacman 移动到 xmin 以便吃它之后）如果它想要要吃另一种水果，他必须去不下什么md(xmin1)地方xmin1=minmd(X-{xmin})等等。返回从 xmin 到 xmin1 到 xmin2 的 mds pacman 的总和，以此类推，因为这是放松的最佳解决方案，您为自己获得了一个很好的可接受且一致的启发式函数！

要考虑的另一点是，如果考虑墙壁，您甚至可以获得更好的启发式方法，这是一个更棘手的问题，所以我没有深入研究，但我注意到如果您将 pacman 绑定在一个矩形中，并带有下一个最佳水果，如果它们之间有一些完整的垂直或水平墙线，他将必须至少支付 2 次以上的操作，因为他必须退出边界矩形并再次重新进入它，同时为每个这样的墙支付至少 2 次操作。这可以进一步检查，您还可以在此矩形中找到更多特殊功能。

编辑：

这种启发式是不可接受的，感谢@Alon Gouldman 看到这一点。

于 2017-10-29T20:58:13.717 回答