搜索“Rush Hour”游戏

为了表示汽车网格，我只使用一个矩形单元格数组，其中每个单元格都标有一个整数——0表示"空"，每辆车都有一个特定的数字，因此网格中的不同汽车将显示为具有相同数字的连续单元格。

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

要实现A*，你需要一个朴素的启发式来确定一个移动看起来有多好，这样你就知道应该先尝试哪些移动。我的建议是，任何让目标车更靠近目标或让目标车更靠近前方的移动都可能是更好的选择。就像Will A在评论中说的，除非你是在解决1000x1000的高峰时间板，否则这可能不是什么大事。

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

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

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

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

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

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

均匀成本:b^?

depth-fist: b ^ m

depth-limited: b^l if (l>d)

迭代深化:b^d

所以你可以看到迭代深化或广度优先搜索表现相当好。深度限制搜索的问题是，如果你的解决方案位于比搜索层更深的地方，那么你将找不到解决方案。

然后你有所谓的"知情搜索"，如最佳优先搜索，贪婪搜索，a*，爬山或模拟退火。简而言之，对于最佳优先搜索，您使用每个节点的评估函数作为"可取性"的估计。贪婪搜索的目标是扩展使你更接近目标的节点。爬山和模拟退火是非常相似的。Stuart Russell是这样解释爬山的(我非常喜欢……):爬山算法就像在浓雾中带着失忆症爬珠穆朗玛峰。它只是一个不断向增值方向移动的循环。所以你只是"走"到增加你的评估函数的方向。

我会使用一种统一的搜索算法，因为它们很容易实现(你只需要编程树并正确地遍历它)。如果你有一个好的评估功能，信息搜索通常会表现得更好……