PacMan:主要使用哪种启发式方法？

Question

除了A*,BFS,DFS等之外,Pacman中常用的其他优秀路径寻找算法/启发式算法是什么？我不认为我提到的那些将会起作用,如果有多个水果供pacman找到.

我需要一些好的寻路算法,PacMan可以用它来尽可能少地完成迷宫.我试图寻找指南,但到目前为止还没有运气.到处都提到了与曼哈顿距离的A*,但它只适用于只有一个(或两个？或者可能多达几个？)果实的迷宫.

顺便说一句,为了保持简单,假设周围没有鬼魂.

原始PacMan问题的一些例子: 第一,第二和第三

Answer 1

如果你知道迷宫的样子,启发式对我有用:

1. 找出迷宫中两个目前最远的水果之间的真正距离 - 让我们称之为x.
2. 找到从当前Pacman位置到前两个水果更接近的实际距离 - 让我们称之为y.

那么,答案就是:x + y.

请注意,真实距离不是曼哈顿距离,而是real迷宫中的距离 - 你可以计算出来(如果你想要的话,甚至可以预先计算),因为你知道迷宫的外观(你知道所有的墙壁......).这些信息(迷宫中某两点之间的实际距离)是静态的,因为墙壁不会改变.

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

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

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

Answer 2

你评论说你正在寻找最短路径.这个问题是平面图上TSP的变化,因此是NP-Hard.

用于可能的启发式函数A*,可以解决的问题,但并不受理 [从而发现不能保证路径是最佳]:

从所有水果到代理人的曼哈顿距离总和.

您也可以使用可接受的启发式#fruits- 但这需要很长时间.

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

还可以改进不允许的启发式解决方案以提供任意时间算法:

A*使用递减的启发式函数迭代运行:h(v) = h'(v) / m,其中h'是A*的最后一次迭代的启发式函数,和m > 1.这保证了在某些时候,您的启发式功能h将是可接受的 - 并且找到的解决方案将是最佳的.但是,每次迭代预计比前一次迭代要长得多[指数长...]

Answer 3

我找到了最近的食物(使用曼哈顿距离)但是对于我的启发式,我使用了从我的位置到最近食物的实际距离.为此,我为所有那些不与我的位置或最接近的食物点分享行或列的食物点添加1.

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

所以,简而言之: heuristic = mazeDistance(我的位置,估计最接近的食物)+剩下的点数

这是可以接受的和一致的.有了这个,我扩展了5500个节点并获得了5/4的FoodHeuristic. https://github.com/sukritiverma1996/Intro-to-AI-course

Answer 4

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

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

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