PacMan:主要使用哪些启发式方法? [英] PacMan: what kinds of heuristics are mainly used?

问题描述

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

Beside A*, BFS, DFS and the like, what are other good path-finding algorithms/heuristics popularly used in Pacman? I don't think the ones I mentioned will work if there're more than one fruits for pacman to find.

我需要一些好的寻路算法，吃豆人可以用它来以尽可能少的步数完成迷宫.我试图四处寻找指南，但到目前为止还没有运气.曼哈顿距离的 A* 随处可见，但它只适用于只有一个(或两个?或者最多几个?)水果的迷宫.

I need some good path-finding algorithms that PacMan can use to finish the maze with the least possible step-count. I've tried to search around for a guideline, but so far no luck. A* with Manhattan distance is mentioned everywhere but it will only work with mazes with only one (or two? or maybe up to a few?) fruit to get.

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

BTW, to keep things simple, assuming that there're no ghosts around.

来自原始 PacMan 问题的一些示例:首先，第二 和 第三个

Some examples from the original PacMan problems: First, Second and Third

推荐答案

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

You comment says you are looking for shortest path. This problem is a variation of TSP on a planar graph, and thus is NP-Hard.

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

Possible heuristics function for A* that can solve the problem but is not admissible [thus the path found is not guaranteed to be optimal]:

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

Sum of manhattan distances from all fruits to the agent.

您也可以使用 #fruits 的可允许启发式方法 - 但需要很长时间.

You can also use an edmissible heuristic, of #fruits - but it will take a long time.

如果您正在寻找最佳选择，那么 - 这很难.您可以尝试水果的所有排列，并检查您需要行驶的总距离.这个解决方案是水果数量的阶乘，如果它大于 20 - 使用天真的蛮力 - 它将花费太长时间.您可以通过将问题简化为 TSP 并使用动态规划解决方案(也是指数式的)或一些 TSP 的启发式解决方案来以某种方式使其更好.

If you are looking for optimal, well - it is hard. You can try all permutations of fruits, and check the total distance you need to travel. This solution is factorial in the number of fruits, and if it is greater then 20 - with naive bruteforce - it will take too long. You can somehow make it better by reducing the problem to TSP, and use dynamic-programming solution, which is also exponential, or some heuristical solutions to TSP.

还可以改进不可接受的启发式解决方案以提供任何时间算法:

One can also improve the non-admissible heuristic solution to provide an any-time algorithm:

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

iteratively run A* with a decreasing heuristic function: h(v) = h'(v) / m, where h' is the heuristic function on last iteration of A*, and m > 1. This guarantees that at some point, your heuristic function h will be admissible - and the solution found will be optimal. However, each iteration is expected to take much longer then the previous one [exponentially longer..]

这篇关于PacMan:主要使用哪些启发式方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！