c# - A* 搜索尖峰时刻游戏？

Question

对于学校的作业，我必须为 Rush Hour 游戏做一个求解器。如果你不熟悉 Rush Hour。请查看此链接：http ://www.puzzles.com/products/rushhour.htm

对于这个求解器，我必须使用 A* 搜索算法，我在网上看了一点，我想我很理解算法是如何工作的。只是我真的不知道如何在求解器中实现它。 . 也不应该如何为汽车建立电网.. 有人可以给我一些提示/帮助吗？不是一个完整的解决方案..

Answer 1

为了表示汽车的网格，我只使用一个矩形的单元格数组，其中每个单元格都用一个整数标记——0 表示“空”，每辆车都有一个特定的数字，所以网格中的不同汽车会出现自己作为具有相同编号的连续单元格。

此时，您应该能够编写一个函数来从给定网格返回所有可能的“移动”，其中“移动”是从一个网格状态到另一个网格状态的转换——你可能不需要编码比这更好的移动表示。

要实现 A*，您需要一个简单的启发式方法来确定一个动作看起来有多好，这样您就知道首先尝试哪个动作。我最初建议任何将目标车移近目标或使空间更靠近目标车前部的任何动作都可能是更好的候选动作。就像 Will A 在评论中所说的那样，除非您要解决 1000x1000 的高峰时间板，否则这可能没什么大不了的。

这就是我能想到的所有棘手的部分。

Answer 2

正如 mquander 或 Will 已经指出的那样，A* 算法对于您的问题可能有点过拟合。

我现在只是给你一些提示，你可以使用什么其他算法来解决这个问题。我不想解释这些算法是如何工作的，因为你可以在互联网上找到很多很好的描述。但是，如果您有任何问题，请随时问我。

您可以使用一些属于“不知情搜索”的算法。例如，广度优先搜索、深度优先搜索、统一成本搜索、深度限制搜索或迭代深化搜索。如果您使用广度优先搜索或统一成本搜索，那么您可能必须处理可用内存空间问题，因为这些算法具有指数空间复杂度（并且您必须将整个搜索空间保留在内存中）。因此，使用深度优先搜索（空间复杂度 O(b*m)）对内存更友好，因为如果您首先访问的树的左侧部分不包含解决方案，则可以省略它。深度限制搜索和迭代加深搜索几乎相同，而在迭代加深搜索中，您迭代地增加树的搜索级别。

如果比较时间复杂度（b=树的分支因子，m=树的最大深度，l=深度级别限制，d=解的深度）：

广度优先：b^(d+1)

统一成本：b^?

深度拳头：b^m

深度受限：b^l if (l>d)

迭代深化：b^d

因此，您可以看到迭代深化或广度优先搜索的表现非常好。深度受限搜索的问题是，如果您的解决方案位于比您的搜索级别更深的位置，那么您将找不到解决方案。

然后你就有了所谓的“知情搜索”，例如最佳优先搜索、贪婪搜索、a*、爬山或模拟退火。简而言之，对于最佳优先搜索，您使用每个节点的评估函数作为“可取性”的估计。贪婪搜索的目标是扩展节点，使您更接近目标。爬山和模拟退火是非常相似。Stuart Russell 对爬山的解释如下（我非常喜欢......）：爬山算法就像在失忆的浓雾中攀登珠穆朗玛峰。它只是一个循环，不断地朝着价值增加的方向移动。因此，您只需“步行”到增加评估功能的方向即可。

我会使用其中一种统一的搜索算法，因为它们很容易实现（您只需要对树进行编程并正确遍历它）。如果您具有良好的评估功能，知情搜索通常会更好地执行...希望对您有所帮助...