algorithm - 尖峰时刻 - 解决游戏

Question

高峰时间
如果您不熟悉它，该游戏由一系列不同大小的汽车组成，水平或垂直设置在具有单个导出的 NxM 网格上。
每辆车都可以按照设定的方向前进/后退，只要没有另一辆车挡住它。你不能永远改变汽车的方向。
有一辆特别的车，通常是红色的。它设置在导出所在的同一行，游戏的目标是找到一系列 Action (一个 Action - 将汽车向后或向前移动 N 步)，让红色汽车驶出迷宫.

我一直在想如何通过计算来解决这个问题，我实在想不出什么好的解决方案。
我想到了一些:

1. 回溯。这非常简单 - 递归和更多递归，直到找到答案。然而，每辆车都可以以几种不同的方式移动，并且在每个游戏状态下可以移动几辆汽车，由此产生的游戏树将是巨大的。
2. 某种约束算法会考虑需要移动的内容，并以某种方式递归工作。这是一个非常粗略的想法，但它是一个想法。
3. 图表？将游戏状态建模为图形并对着色算法应用某种变体，以解决依赖关系？同样，这是一个非常粗略的想法。
4. 一位 friend 建议使用遗传算法。这是可能的，但并不容易。我想不出制作评估函数的好方法，没有它我们就一事无成。

所以问题是 - 如何创建一个程序来获取网格和车辆布局，并输出将红色汽车开出所需的一系列步骤？

子问题:

1. 寻找一些解决方案。
2. 寻找最佳解决方案(最少的移动次数)
3. 评估当前状态的好坏

示例:在此设置中如何移动汽车，以便红色汽车可以通过右侧的导出“退出”迷宫？

_{(来源:scienceblogs.com)}

Answer 1

对于经典的尖峰时刻，这个问题很容易通过简单的广度优先搜索来解决。声称最难的已知初始配置需要 93 步才能解决，总共只有 24132 个可到达的配置。即使是简单实现的广度优先搜索算法也可以在一台普通机器上用不到 1 秒的时间探索整个搜索空间。

引用资料

• Wikipedia/Rush Hour (board game)
• Rush Hour Initial Configurations -- 这些被称为“最难”的问题
• Solver source at ideone.com - 输出“最难”的输入

---

Java 求解器

这是用 C 语言编写的广度优先搜索穷举求解器的完整源代码。

import java.util.*;

public class RushHour {
    // classic Rush Hour parameters
    static final int N = 6;
    static final int M = 6;
    static final int GOAL_R = 2;
    static final int GOAL_C = 5;

    // the transcription of the 93 moves, total 24132 configurations problem
    // from http://cs.ulb.ac.be/~fservais/rushhour/index.php?window_size=20&offset=0
    static final String INITIAL =   "333BCC" +
                                    "B22BCC" +
                                    "B.XXCC" +
                                    "22B..." +
                                    ".BB.22" +
                                    ".B2222";

    static final String HORZS = "23X";  // horizontal-sliding cars
    static final String VERTS = "BC";   // vertical-sliding cars
    static final String LONGS = "3C";   // length 3 cars
    static final String SHORTS = "2BX"; // length 2 cars
    static final char GOAL_CAR = 'X';
    static final char EMPTY = '.';      // empty space, movable into
    static final char VOID = '@';       // represents everything out of bound

    // breaks a string into lines of length N using regex
    static String prettify(String state) {
        String EVERY_NTH = "(?<=\\G.{N})".replace("N", String.valueOf(N));
        return state.replaceAll(EVERY_NTH, "\n");
    }

    // conventional row major 2D-1D index transformation
    static int rc2i(int r, int c) {
        return r * N + c;
    }

    // checks if an entity is of a given type
    static boolean isType(char entity, String type) {
        return type.indexOf(entity) != -1;
    }

    // finds the length of a car
    static int length(char car) {
        return
            isType(car, LONGS) ? 3 :
            isType(car, SHORTS) ? 2 :
            0/0; // a nasty shortcut for throwing IllegalArgumentException
    }

    // in given state, returns the entity at a given coordinate, possibly out of bound
    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);
    }

    // checks if a given state is a goal state
    static boolean isGoal(String state) {
        return at(state, GOAL_R, GOAL_C) == GOAL_CAR;
    }

    // in a given state, starting from given coordinate, toward the given direction,
    // counts how many empty spaces there are (origin inclusive)
    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;
    }

    // the predecessor map, maps currentState => previousState
    static Map<String,String> pred = new HashMap<String,String>();
    // the breadth first search queue
    static Queue<String> queue = new LinkedList<String>();
    // the breadth first search proposal method: if we haven't reached it yet,
    // (i.e. it has no predecessor), we map the given state and add to queue
    static void propose(String next, String prev) {
        if (!pred.containsKey(next)) {
            pred.put(next, prev);
            queue.add(next);
        }
    }

    // the predecessor tracing method, implemented using recursion for brevity;
    // guaranteed no infinite recursion, but may throw StackOverflowError on
    // really long shortest-path trace (which is infeasible in standard 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;
    }

    // in a given state, from a given origin coordinate, attempts to find a car of a given type
    // at a given distance in a given direction; if found, slide it in the opposite direction
    // one spot at a time, exactly n times, proposing those states to the breadth first search
    //
    // 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(); // comment to combo as one step
        }
    }

    // explores a given state; searches for next level states in the breadth first search
    //
    // Let (r,c) be the intersection point of this cross:
    //
    //     @       nU = 3     '@' is not a car, 'B' and 'X' are of the wrong type;
    //     .       nD = 1     only '2' can slide to the right up to 5 spaces
    //   2.....B   nL = 2
    //     X       nR = 4
    //
    // The n? counts how many spaces are there in a given direction, origin inclusive.
    // Cars matching the type will then slide on these "alleys".
    //
    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) {
        // typical queue-based breadth first search implementation
        propose(INITIAL, null);
        boolean solved = false;
        while (!queue.isEmpty()) {
            String current = queue.remove();
            if (isGoal(current) && !solved) {
                solved = true;
                trace(current);
                //break; // comment to continue exploring entire space
            }
            explore(current);
        }
        System.out.println(pred.size() + " explored");
    }
}

源码中有两行值得注意:

• break; 当找到解决方案时
  • 现在对此进行注释，以便广度优先搜索探索整个搜索空间，以确认上面链接网站中给出的数字
• 幻灯片中的current = sb.toString();
  • 基本上，这会将任何汽车的每次运动都计为一次运动。如果汽车向左移动 3 个空格，则为 3 步。要将此组合为一个 Action (因为它涉及向同一方向移动的同一辆车)，只需注释这一行。链接的网站不承认组合，因此现在取消注释此行以匹配给定的最小移动次数。使用连击计数，93 步问题只需要 49 次连击。也就是说，如果 parking 场里有一个 parking 服务员来搬运这些车，他只需要进出一辆车 49 次。

---

算法概述

该算法本质上是广度优先搜索，通常使用队列实现。维护一个前导图，以便任何状态都可以追溯到初始状态。一个键永远不会被重新映射，并且由于条目是按广度优先搜索顺序插入的，因此保证了最短路径。

状态表示为 NxM 长度的 String。每个 char 代表棋盘上的一个实体，以行优先顺序存储。

通过从空白区域扫描所有 4 个方向来找到相邻状态，寻找合适的汽车类型，并在房间容纳时滑动它。

这里有很多多余的工作(例如，多次扫描长“小巷”)，但如前所述，虽然通用版本是 PSPACE 完备的，但经典的 Rush Hour 变体很容易被蛮力处理。

维基百科引用

• Breadth-first search
• Row-major order