5

我已经了解了 A*、BFS、DFS，并且可以很好地实现它们。但是，当我尝试解决 pacman 寻路问题时，会出现一些问题。让我们假设只有两种类型的迷宫：一种有完整的项目，因为没有空白方块，所有东西要么是吃豆人，要么是要收集的物品，要么是墙；一个只有几个项目（4个或更少）。

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

  2. 完整项目地图的最佳算法/启发式是什么？到目前为止，我想出的是类似于贪婪启发式的方法，但由于地图上有太多要收集的物品，所以它非常随机，因此，解决这种迷宫不是一个好主意。

  3. 使用A*，在few-item map中，有什么好的方法可以确定先拿哪个item？我曾想过尝试使用 Mahattan 距离作为粗略估计，但这听起来并不正确，尤其是在一些棘手的情况下。

4

2 回答 2

0

如果您添加更多食物，算法不会改变。唯一改变的是状态空间。你必须想出一种新的方式来表达你的问题。当你只有 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 ans A* 将始终为您提供最佳解决方案。问题是：你放的食物越多，找到解决方案的速度就越慢。所以这些算法不会在合理的时间内给出答案。你已经想到了这样做的新方法。

于 2012-10-14T00:14:19.280 回答
0

1）在这种情况下使用 BFS 或 DFS 时我会遇到的问题是这最终会变得多么低效，尤其是在完整地图示例中。要使任一算法适用于多个目标，您可以构建搜索，使其在找到第一条路径后不会结束，但这仍然不会为地图上的每一块食物提供“最佳”路径，或者你可以做一条从吃豆人到最近的食物的路径，从那个食物到下一个最近的食物，等等，找到这些路径，然后比较它们以找到一条真正的最佳路径，但我不想考虑那会持续多长时间拿。

2）我可能会坚持使用贪婪的 A*，它只查看最近的食物（在大多数情况下，我认为曼哈顿距离没有问题，因为 pacman 的地图已经是一个网格；它对于边缘来说不是最理想的墙壁阻止吃豆人进入最近的情况，但这是一个很难解决的问题。曼哈顿将是一个不错的情况，可能会受到食物密度而不是距离的影响，例如：（曼哈顿距离）/（3x3 内的总食物）食物的平方）

3）没有在每个项目上使用寻路，然后选择最短的，我认为曼哈顿在少数项目场景中会做得很好。它不会总是选择最好的，但 100% 最佳的 AI 通常不是游戏的最佳目标。

在这种情况下，我想尝试使用权重偏向于项目集群的贪婪 A* 作为一种简单、相当快速的解决方案。

应该返回更接近 Pacman 遵循的最佳路径的更复杂的解决方案是使用算法来找到最小生成树 http://en.wikipedia.org/wiki/Minimum_spanning_tree但我不知道这有多容易要实施。这是一个讨论两种最小生成树算法优点的问题：Kruskal vs Prim

于 2013-08-01T15:59:23.960 回答