提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

【图论搜索专题】灵活运用多种搜索方式进行求解 Ⅱ（含启发式搜索）

算法 代码
2023-03-31 10:30:58 时间

题目描述

这是 LeetCode 上的「773. 滑动谜题」，难度为「困难」。

Tag : 「BFS」、「最小步数」、「AStar 算法」、「启发式搜索」在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示.一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。

示例 1：

输入：board = [[1,2,3],[4,0,5]]

输出：1

解释：交换 0 和 5 ，1 步完成

示例 2：

输入：board = [[1,2,3],[5,4,0]]

输出：-1

解释：没有办法完成谜板

示例 3：

输入：board = [[4,1,2],[5,0,3]]

输出：5

解释：
最少完成谜板的最少移动次数是 5 ，
一种移动路径:
尚未移动: [[4,1,2],[5,0,3]]
移动 1 次: [[4,1,2],[0,5,3]]
移动 2 次: [[0,1,2],[4,5,3]]
移动 3 次: [[1,0,2],[4,5,3]]
移动 4 次: [[1,2,0],[4,5,3]]
移动 5 次: [[1,2,3],[4,5,0]]

示例 4：

输入：board = [[3,2,4],[1,5,0]]

输出：14

提示：

  • board 是一个如上所述的 2 x 3 的数组.
  • board[i][j] 是一个 [0, 1, 2, 3, 4, 5] 的排列.

基本分析

这是 [图论搜索专题] 中「灵活运用多种搜索方式」的第二篇，第一篇在 这里。

这是八数码问题的简化版：将 3 * 3 变为 2 * 3 ，同时将「输出路径」变为「求最小步数」。通常此类问题可以使用「BFS」、「AStar 算法」、「康拓展开」进行求解。由于问题简化到了 2 * 3 ，我们使用前两种解法即可。

BFS

为了方便，将原来的二维矩阵转成字符串（一维矩阵）进行处理。这样带来的好处直接可以作为哈希 Key 使用，也可以很方便进行「二维坐标」与「一维下标」的转换。由于固定是 2 * 3 的格子，因此任意的合法二维坐标 (x, y) 和对应一维下标 idx 可通过以下转换：

  • idx = x * 3 + y
  • x = idx / 3,y = idx \% 3

其余的就是常规的 BFS 过程了。

代码：

class Solution {
    class Node {
        String str;
        int x, y;
        Node(String _str, int _x, int _y) {
            str = _str; x = _x; y = _y;
        }
    }
    int n = 2, m = 3;
    String s, e;
    int x, y;
    public int slidingPuzzle(int[][] board) {
        s = "";
        e = "123450";
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                s += board[i][j];
                if (board[i][j] == 0) {
                    x = i; y = j;
                }
            }
        }
        int ans = bfs();
        return ans;
    }
    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    int bfs() {
        Deque<Node> d = new ArrayDeque<>();
        Map<String, Integer> map = new HashMap<>();
        Node root = new Node(s, x, y);
        d.addLast(root);
        map.put(s, 0);
        while (!d.isEmpty()) {
            Node poll = d.pollFirst();
            int step = map.get(poll.str);
            if (poll.str.equals(e)) return step;
            int dx = poll.x, dy = poll.y;
            for (int[] di : dirs) {
                int nx = dx + di[0], ny = dy + di[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                String nStr = update(poll.str, dx, dy, nx, ny);      
                if (map.containsKey(nStr)) continue;          
                Node next = new Node(nStr, nx, ny);
                d.addLast(next);
                map.put(nStr, step + 1);
            }
        }
        return -1;
    }
    String update(String cur, int i, int j, int p, int q) {
        char[] cs = cur.toCharArray();
        char tmp = cs[i * m + j];
        cs[i * m + j] = cs[p * m + q];
        cs[p * m + q] = tmp;
        return String.valueOf(cs);
    }
}

AStar 算法

可以直接根据本题规则来设计 AStar 算法的「启发式函数」。

比如对于两个状态 a 和 b 可直接计算出「理论最小转换次数」：所有位置的数值「所在位置」与「目标位置」的曼哈顿距离之和（即横纵坐标绝对值之和）。

注意，我们只需要计算「非空格」位置的曼哈顿距离即可，因为空格的位置会由其余数字占掉哪些位置而唯一确定。

AStar 求最短路的正确性问题：由于我们衡量某个状态 str 的估值是以目标字符串 e=123450 为基准，因此我们只能确保 e 出队时为「距离最短」，而不能确保中间节点出队时「距离最短」，因此我们不能单纯根据某个节点是否「曾经入队」而决定是否入队，还要结合当前节点的「最小距离」是否被更新而决定是否入队。

这一点十分关键，在代码层面上体现在 map.get(nStr) > step + 1 的判断上。

我们知道，AStar 算法在有解的情况下，才会发挥「启发式搜索」的最大价值，因此如果我们能够提前判断无解的情况，对 AStar 算法来说会是巨大的提升。而对于通用的 N * N 数码问题，判定有解的一个充要条件是：「逆序对」数量为偶数，如果不满足，必然无解，直接返回 -1 即可。对该结论的充分性证明和必要性证明完全不在一个难度上，所以建议记住这个结论即可。

代码：

class Solution {
    class Node {
        String str;
        int x, y;
        int val;
        Node(String _str, int _x, int _y, int _val) {
            str = _str; x = _x; y = _y; val = _val;
        }
    }
    int f(String str) {
        int ans = 0;
        char[] cs1 = str.toCharArray(), cs2 = e.toCharArray();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 跳过「空格」，计算其余数值的曼哈顿距离
                if (cs1[i * m + j] == '0' || cs2[i * m + j] == '0') continue;
                int cur = cs1[i * m + j], next = cs2[i * m + j];
                int xd = Math.abs((cur - 1) / 3 - (next - 1) / 3);
                int yd = Math.abs((cur - 1) % 3 - (next - 1) % 3); 
                ans += (xd + yd);
            }
        }
        return ans;
    }
    int n = 2, m = 3;
    String s, e;
    int x, y;
    public int slidingPuzzle(int[][] board) {
        s = "";
        e = "123450";
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                s += board[i][j];
                if (board[i][j] == 0) {
                    x = i; y = j;
                }
            }
        }

        // 提前判断无解情况
        if (!check(s)) return -1;

        int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
        Node root = new Node(s, x, y, f(s));
        PriorityQueue<Node> q = new PriorityQueue<>((a,b)->a.val-b.val);
        Map<String, Integer> map = new HashMap<>();
        q.add(root);
        map.put(s, 0);
        while (!q.isEmpty()) {
            Node poll = q.poll();
            int step = map.get(poll.str);
            if (poll.str.equals(e)) return step;
            int dx = poll.x, dy = poll.y;
            for (int[] di : dirs) {
                int nx = dx + di[0], ny = dy + di[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                String nStr = update(poll.str, dx, dy, nx, ny);      
                if (!map.containsKey(nStr) || map.get(nStr) > step + 1) {
                    Node next = new Node(nStr, nx, ny, step + 1 + f(nStr));
                    q.add(next);
                    map.put(nStr, step + 1);
                }
            }
        }
        return 0x3f3f3f3f; // never
    }
    String update(String cur, int i, int j, int p, int q) {
        char[] cs = cur.toCharArray();
        char tmp = cs[i * m + j];
        cs[i * m + j] = cs[p * m + q];
        cs[p * m + q] = tmp;
        return String.valueOf(cs);
    }
    boolean check(String str) {
        char[] cs = str.toCharArray();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n * m; i++) {
            if (cs[i] != '0') list.add(cs[i] - '0');
        }
        int cnt = 0;
        for (int i = 0; i < list.size(); i++) {
            for (int j = i + 1; j < list.size(); j++) {
                if (list.get(i) < list.get(j)) cnt++;
            }
        }
        return cnt % 2 == 0;
    }
}

最后

这是我们「刷穿 LeetCode」系列文章的第 No.773 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章