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

简介: 【图论搜索专题】灵活运用多种搜索方式进行求解 Ⅱ(含启发式搜索)

网络异常,图片无法展示
|


题目描述



这是 LeetCode 上的 773. 滑动谜题 ,难度为 困难


Tag : 「BFS」、「最小步数」、「AStar 算法」、「启发式搜索」


在一个 2 x 3 的板上(board)有 55 块砖瓦,用数字 1~5 来表示, 以及一块空缺用 00 来表示.


一次移动定义为选择 00 与一个相邻的数字(上下左右)进行交换.


最终当板 board 的结果是 [[1,2,3],[4,5,0]][[1,2,3],[4,5,0]] 谜板被解开。


给出一个谜板的初始状态,返回最少可以通过多少次移动解开谜板,如果不能解开谜板,则返回 -11


示例 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][0,1,2,3,4,5] 的排列.


基本分析



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


这是八数码问题的简化版:将 3 * 333 变为 2 * 323,同时将「输出路径」变为「求最小步数」。


通常此类问题可以使用「BFS」、「AStar 算法」、「康拓展开」进行求解。


由于问题简化到了 2 * 323,我们使用前两种解法即可。


BFS



为了方便,将原来的二维矩阵转成字符串(一维矩阵)进行处理。


这样带来的好处直接可以作为哈希 Key 使用,也可以很方便进行「二维坐标」与「一维下标」的转换。


由于固定是 2 * 323 的格子,因此任意的合法二维坐标 (x, y)(x,y) 和对应一维下标 idxidx 可通过以下转换:


  • idx = x * 3 + yidx=x3+y
  • x = idx / 3,y = idx \% 3x=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 算法的「启发式函数」。


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


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


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


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


我们知道,AStar 算法在有解的情况下,才会发挥「启发式搜索」的最大价值,因此如果我们能够提前判断无解的情况,对 AStar 算法来说会是巨大的提升。


而对于通用的 N * NNN 数码问题,判定有解的一个充要条件是:「逆序对」数量为偶数,如果不满足,必然无解,直接返回 -11 即可。


对该结论的充分性证明和必要性证明完全不在一个难度上,所以建议记住这个结论即可。


代码:


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 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。


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


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


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

相关文章
|
8月前
|
人工智能 数据可视化 网络安全
Dify与DeepSeek的深度融合——构建您的专属AI助手
在当今数据驱动、AI为王的时代,Dify与DeepSeek作为领先的AI开发工具和大模型引擎,为企业和个人提供高效智能的解决方案。Dify是面向AI应用开发的低代码平台,集成预训练模型、可视化界面和无缝部署功能;DeepSeek则是高性能、低成本的开源大语言模型,具备多轮推理能力。两者结合并通过私有化部署,确保数据安全与合规,极大提升开发效率和业务生产力。阿里云计算巢提供了两者的私有化部署方案,帮助用户快速搭建专属AI应用。
818 1
|
Web App开发 网络安全 Go
新MacBook到手时,建议你需要做的事情(二)
在Mac上重装系统前,应备份`~/.gitconfig`, `~/.ssh`, `~/.config`等个人配置文件。推荐的软件包括有道云笔记、WPS Office、FastZip、XMind、网络调试助手、Chrome、Clash、iTerm2、oh-my-zsh、Homebrew、Git、wget、tree、telnet、Neovim、tldr、IDEs(如JetBrains产品)、GitHub Desktop、VS Code、
367 0
新MacBook到手时,建议你需要做的事情(二)
|
10月前
|
数据可视化 数据挖掘
分享5款无广告,小体积的工具
本文介绍了5款体积小、无广告且实用的软件:格式工厂(文件格式转换)、Starrea(数据可视化)、燃精灵(微信空号检测)、EasyCharts(图表生成)和EagleGet(下载加速)。每款软件都有详细的功能介绍,适合不同需求的用户。观看后可自行搜索下载。
184 0
|
Linux Python Windows
IntelliJ全家桶IDEA/Pycharm2020.1激活方式
IntelliJ全家桶IDEA/Pycharm2020.1激活方式
|
算法 C语言 C++
【双指针问题】977. 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
101 0
2.1.1计算机网络(奈氏准则 香农定理 码元 速率 波特 带宽 物理层概念 通信方式 传输方式)
物理层基本概念 1.机械特性 2.电气特性 3.功能特性 4.规程特性 数据通信基础知识 1.典型的数据通信模型 2.数据通信相关术语 三种通信方式 1.单工通信 2.半双工通信 3.全双工通信 传输方式 串行传输&并行传输​ 码元 速率 波特 带宽 码元 速率 带宽 ​ 奈氏准则 香农定理 失真 失真的一种现象---码间串扰 奈氏准则(奈奎斯特定理) 香农定理
2.1.1计算机网络(奈氏准则 香农定理 码元 速率 波特 带宽 物理层概念 通信方式 传输方式)
|
Android开发 安全 文件存储
Android官方开发文档Training系列课程中文版:调用相机之简单拍照
原文地址:http://android.xsoftlab.net/training/camera/index.html 导言 在富媒体开始流行之前,整个世界是一个灰暗且平淡无奇的地方。
1033 0
|
iOS开发
友盟iOS微信登陆没有回调的原因
1、在友盟文档中这样说: 链接 7.4 微信登录 添加配置文件参考文档:添加微信及朋友圈,添加相关库文件,配置URL schemes及添加系统回调 注意微信登录必须先在微信开放平台申请微信登录权限 在你的程序APPdelegate入口方法添加下面的代码 #import "UMSocialWechatHandler.
1223 0
|
Java 数据库连接 mybatis
MyBatis日记
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/SunnyYoona/article/details/50659998 ...
967 0