pacman路径发现的一些问题

Question

我已经了解了A*,BFS,DFS并且可以很好地实现它们.但是,当我尝试解决pacman路径查找问题时会出现一些问题.让我们假设只有两种类型的迷宫:一种是完整的物品,因为没有空白的方块,一切都是pacman或物品收集或墙; 一个只有少数项目(4个或更少).

1. 如果要收集多个项目,BFS和DFS究竟是如何实现的？在这种情况下,它们仍能产生最佳结果吗？

2. 全项目地图的最佳算法/启发式是什么？到目前为止我所提出的是贪婪的启发式,但由于地图上有太多的东西需要收集,所以它很随意,因此,解决这样的迷宫并不是一个好主意.

3. 在少数项目地图中使用A*,是否有任何好方法可以确定应该首先采取哪个项目？我想过尝试使用Mahattan距离作为粗略估计,但这听起来并不正确,特别是在一些棘手的情况下.

Answer 1

如果添加更多食物，算法不会改变。唯一改变的是状态空间。你必须想出一种新的方式来表达你的问题。当你只有1种食物可吃时，你只需要pacman的x,y位置。例如，当您有 3 个点要吃时，您必须将这些信息添加到您的模型中。您可以添加 3 个布尔变量来指示 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 和 A* 总会为您提供最佳解决方案。问题是：你放的食物越多，找到解决方案的速度就越慢。所以这些算法不会在合理的时间内给出答案。你必须想出新的方法来做到这一点。