graph - pacman 寻路的一些问题

Question

我已经了解了 A*、BFS、DFS，并且可以很好地实现它们。但是，当我尝试解决 pacman 寻路问题时，会出现一些问题。让我们假设只有两种类型的迷宫:一种有完整的元素，因为没有空白方块，一切都是吃 bean 或元素收集或墙壁；一个只有几个项目(4 个或更少)。

如果要收集的元素不止一件，BFS 和 DFS 究竟是如何实现的？在这种情况下，它们是否仍然产生最佳结果？

全项目 map 的最佳算法/启发式是什么？到目前为止，我想出的是类似贪婪启发式的东西，但由于 map 有太多要收集的元素，因此它非常随机，因此，解决此类迷宫不是一个好主意。

使用A*，在少项映射中，有什么好的方法可以确定应该先取哪个项？我想尝试使用马哈坦距离作为粗略估计，但这听起来不太正确，尤其是在一些棘手的情况下。

Answer 1

如果您添加更多食物，算法不会改变。唯一改变的是状态空间。你必须想出一种新的方式来表示你的问题。当你只有 1 种食物可以吃时，你只需要 pacman 的 x, y 位置。例如，当您有 3 个点可以吃时，您必须将这些信息添加到您的模型中。您可以添加 3 个 bool 变量来指示 pacman 已通过点。现在你的状态空间是一个由以下类型的节点组成的图:

 ((x,y),FALSE,FALSE,FALSE) -> state that indicates that pacman has not eat any food
 ((x,y),FALSE,TRUE,FALSE) -> state that indicates that pacman has eat only one food
 ((x,y),TRUE,TRUE,TRUE) -> this is the goal state

要解决这个问题，您只需在新模型中运行相同的算法。 BFS ans A* 将始终为您提供最佳解决方案。问题是:你放的食物越多，找到解决方案的速度就越慢。所以这些算法不会在合理的时间内给出答案。你已经想到了这样做的新方法。