我已经了解了 A*、BFS、DFS,并且可以很好地实现它们。但是,当我尝试解决 pacman 寻路问题时,会出现一些问题。让我们假设只有两种类型的迷宫:一种有完整的元素,因为没有空白方块,一切都是吃 bean 或元素收集或墙壁;一个只有几个项目(4 个或更少)。
最佳答案
如果您添加更多食物,算法不会改变。唯一改变的是状态空间。你必须想出一种新的方式来表示你的问题。当你只有 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* 将始终为您提供最佳解决方案。问题是:你放的食物越多,找到解决方案的速度就越慢。所以这些算法不会在合理的时间内给出答案。你已经想到了这样做的新方法。
关于graph - pacman 寻路的一些问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9772705/