Rush Hour（交通堵塞）
如果你还不熟悉它，这个游戏由一组大小不一的汽车组成，它们水平或垂直地放置在一个NxM的网格上，网格有一个唯一的出口。
每辆车都可以沿着它所放置的方向前进/后退，只要没有其他车阻挡它。你永远不能改变汽车的方向。
有一辆特殊的车，通常是红色的。它位于出口所在的同一行，游戏的目标是找到一系列的移动（一次移动 – 将一辆车向后或向前移动N步），使红色的车能够驶出迷宫。
我一直在尝试思考如何通过计算来解决这个问题，但我真的想不出任何好的解决方案。
我想出了几个：
- 回溯法。这非常简单 – 递归以及更多的递归，直到找到答案。然而，每辆车都可以通过几种不同的方式移动，并且在每个游戏状态下，都可以移动一些车，因此生成的游戏树将非常巨大。
- 某种约束算法，它将考虑到需要移动的东西，并以某种方式递归地工作。这是一个非常粗略的想法，但它是一个想法。
- 图？将游戏状态建模为一个图，并应用着色算法的某种变体来解决依赖关系？同样，这是一个非常粗略的想法。
- 一位朋友建议使用遗传算法。这在某种程度上是可能的，但不容易。我想不出一个好的方法来创建一个评估函数，没有它，我们就什么都没有。
所以问题是 – 如何创建一个程序，它接收一个网格和车辆布局，并输出一系列的步骤，使得红色的车能够驶出？
子问题：
- 找到一些解决方案。
- 找到一个最佳解决方案（最少的移动次数）。
- 评估当前状态有多好。
例子：你如何在这个设置中移动汽车，以便红色的车可以通过右侧的出口“退出”迷宫？
(来源: scienceblogs.com)
回答：
对于经典的 Rush Hour 游戏，这个问题通过简单的广度优先搜索很容易解决。据称最难的已知初始配置需要 93 步才能解决，总共只有 24132 个可达到的配置。即使是朴素实现的广度优先搜索算法也可以在不到 1 秒的时间内在普通的机器上探索整个搜索空间。
参考资料
- 维基百科/Rush Hour (棋盘游戏)
- Rush Hour 初始配置 — 这些据称是“最难”的问题
- ideone.com 上的求解器源代码 – 带有“最难”输入的输出
Java 求解器
这是一个用 C 风格编写的广度优先搜索穷举求解器的完整源代码。
import java.util.*;public class RushHour { // 经典的 Rush Hour 参数 static final int N = 6; static final int M = 6; static final int GOAL_R = 2; static final int GOAL_C = 5; // 从 http://cs.ulb.ac.be/~fservais/rushhour/index.php?window_size=20&offset=0 抄录的 93 步，总共 24132 个配置问题 static final String INITIAL = "333BCC" + "B22BCC" + "B.XXCC" + "22B..." + ".BB.22" + ".B2222"; static final String HORZS = "23X"; // 水平滑动的汽车 static final String VERTS = "BC"; // 垂直滑动的汽车 static final String LONGS = "3C"; // 长度为 3 的汽车 static final String SHORTS = "2BX"; // 长度为 2 的汽车 static final char GOAL_CAR = 'X'; static final char EMPTY = '.'; // 空格，可以移动进入 static final char VOID = '@'; // 表示所有超出范围的东西 // 使用正则表达式将字符串分成长度为 N 的行 static String prettify(String state) { String EVERY_NTH = "(?<=\\G.{N})".replace("N", String.valueOf(N)); return state.replaceAll(EVERY_NTH, "\n"); } // 传统的行主序 2D-1D 索引转换 static int rc2i(int r, int c) { return r * N + c; } // 检查实体是否为给定的类型 static boolean isType(char entity, String type) { return type.indexOf(entity) != -1; } // 找到汽车的长度 static int length(char car) { return isType(car, LONGS) ? 3 : isType(car, SHORTS) ? 2 : 0/0; // 用于抛出 IllegalArgumentException 的一个糟糕的快捷方式 } // 在给定的状态下，返回给定坐标上的实体，可能超出范围 static char at(String state, int r, int c) { return (inBound(r, M) && inBound(c, N)) ? state.charAt(rc2i(r, c)) : VOID; } static boolean inBound(int v, int max) { return (v >= 0) && (v < max); } // 检查给定的状态是否为目标状态 static boolean isGoal(String state) { return at(state, GOAL_R, GOAL_C) == GOAL_CAR; } // 在给定的状态下，从给定的起始坐标开始，朝着给定的方向， // 计算有多少个空格（包括起点） static int countSpaces(String state, int r, int c, int dr, int dc) { int k = 0; while (at(state, r + k * dr, c + k * dc) == EMPTY) { k++; } return k; } // 前驱映射，将 currentState => previousState 映射 static Map<String,String> pred = new HashMap<String,String>(); // 广度优先搜索队列 static Queue<String> queue = new LinkedList<String>(); // 广度优先搜索提议方法：如果我们还没有到达它， // (即它没有前驱)，我们映射给定的状态并添加到队列 static void propose(String next, String prev) { if (!pred.containsKey(next)) { pred.put(next, prev); queue.add(next); } } // 前驱追踪方法，为了简洁起见，使用递归实现； // 保证没有无限递归，但可能会在 // 真正长的最短路径跟踪上抛出 StackOverflowError（这在标准的 Rush Hour 中是不可能的） static int trace(String current) { String prev = pred.get(current); int step = (prev == null) ? 0 : trace(prev) + 1; System.out.println(step); System.out.println(prettify(current)); return step; } // 在给定的状态下，从给定的原始坐标，尝试在给定的距离上，以给定的方向找到给定类型的汽车；如果找到，则将其在相反的方向滑动 // 一次一个位置，总共 n 次，将这些状态提议给广度优先搜索 // // e.g. // direction = --> // __n__ // / \ // ..o....c // \___/ // distance // static void slide(String current, int r, int c, String type, int distance, int dr, int dc, int n) { r += distance * dr; c += distance * dc; char car = at(current, r, c); if (!isType(car, type)) return; final int L = length(car); StringBuilder sb = new StringBuilder(current); for (int i = 0; i < n; i++) { r -= dr; c -= dc; sb.setCharAt(rc2i(r, c), car); sb.setCharAt(rc2i(r + L * dr, c + L * dc), EMPTY); propose(sb.toString(), current); current = sb.toString(); // 注释以将组合作为一步 } } // 探索给定的状态；在广度优先搜索中搜索下一级别的状态 // // 令 (r,c) 为此十字的交点： // // @ nU = 3 '@' 不是汽车，'B' 和 'X' 是错误的类型； // . nD = 1 只有 '2' 可以向右滑动最多 5 个空格 // 2.....B nL = 2 // X nR = 4 // // n? 计算在给定方向上有多少个空格，包括起点。 // 然后，匹配类型的汽车将滑过这些“小巷”。 // static void explore(String current) { for (int r = 0; r < M; r++) { for (int c = 0; c < N; c++) { if (at(current, r, c) != EMPTY) continue; int nU = countSpaces(current, r, c, -1, 0); int nD = countSpaces(current, r, c, +1, 0); int nL = countSpaces(current, r, c, 0, -1); int nR = countSpaces(current, r, c, 0, +1); slide(current, r, c, VERTS, nU, -1, 0, nU + nD - 1); slide(current, r, c, VERTS, nD, +1, 0, nU + nD - 1); slide(current, r, c, HORZS, nL, 0, -1, nL + nR - 1); slide(current, r, c, HORZS, nR, 0, +1, nL + nR - 1); } } } public static void main(String[] args) { // 基于队列的典型广度优先搜索实现 propose(INITIAL, null); boolean solved = false; while (!queue.isEmpty()) { String current = queue.remove(); if (isGoal(current) && !solved) { solved = true; trace(current); //break; // 注释以继续探索整个空间 } explore(current); } System.out.println(pred.size() + " explored"); }}源代码中有两个值得注意的行：
- 当找到解决方案时，
break;- 现在已注释掉，以便广度优先搜索探索整个搜索空间，以确认上面链接的网站中给出的数字
slide中的current = sb.toString();- 本质上，这会将任何汽车的每次移动都计为一步。如果一辆车向左移动 3 个空格，那就是 3 步。要将此组合为一步（因为它涉及同一辆车沿同一方向移动），只需注释掉此行即可。链接的网站没有承认组合，所以现在取消注释此行以匹配给定的最小移动次数。通过组合计数，93 步问题仅需要 49 次组合移动。也就是说，如果停车场里有一个停车服务员来移动这些汽车，他只需要进出汽车 49 次。
算法概述
该算法本质上是广度优先搜索，使用队列实现，这是典型的。维护一个前驱映射，以便任何状态都可以追溯到初始状态。密钥永远不会被重新映射，并且条目以广度优先搜索顺序插入，保证了最短路径。
状态表示为一个 NxM 长度的 String。每个 char 代表棋盘上的一个实体，以行主序存储。
通过从空闲空间扫描所有 4 个方向，查找适当的汽车类型，并根据空间滑动它，来找到相邻的状态。
这里有很多冗余工作（例如，长“小巷”被多次扫描），但正如之前提到的，尽管广义版本是 PSPACE 完全的，但经典的 Rush Hour 变体很容易通过蛮力解决。
