JAVA中的回溯算法解空间树，八皇后问题以及骑士游历问题超详解

1.回溯算法的概念

回溯算法顾名思义就是有回溯的算法

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

回溯算法的核心思想是：

  1. 问题分解：将原问题分解成若干个规模较小的子问题。
  2. 候选解的生成：从根节点开始，逐层生成候选解。
  3. 活节点：当前正在扩展的节点称为活节点。
  4. 死节点：当前扩展的节点如果已经确定不能得到问题的解，则该节点称为死节点。
  5. 剪枝：根据问题的限制条件，对已经确定的死节点进行剪枝。

2.回溯算法解空间树的问题

 典型案例：

集合求幂集的解空间树

意思就是一个集合s所有的子集的集合

问题：求集合S={1,2,3}的所有子集，依次选择每个元素的过程就是一棵树，如图所示

在树中，由从根节点到叶子结点的每条路径上的权值组成三元组（0,0,0）~（1,1,1）都是解，如（0,0,1）表示子集{B，C},共2^{3}=8个解；因此，该树被称为解空间树，高度为4。

为什么帮助理解，我们先看普通的递归方法是什么实现的

下面是迭代方法代码实现：

import java.util.ArrayList;
import java.util.List;

public class PowerSet {
    public static void main(String[] args) {
        List<String> originalSet =new ArrayList<>();
        originalSet.add("A");
        originalSet.add("B");
        originalSet.add("C");
        //这里又嵌套了一个list是为了使每一个元素都变成list
        //适用于多种算法和数据处理任务
        List<List<String>> powerSet =getPowerSet(originalSet);

        for (List<String> subset:powerSet){
            System.out.println(subset);
        }
   }

    private static List<List<String>> getPowerSet(List<String> originalSet) {
        List<List<String>> powerSet =new ArrayList<>();
        if (originalSet==null||originalSet.isEmpty()){
            return powerSet;
        }
        //添加空集
        powerSet.add(new ArrayList<>());

        for (String element:originalSet){
            int size =powerSet.size();
            for (int i =0;i<size;i++){
                List<String> subset =new ArrayList<>(powerSet.get(i));
                subset.add(element);
                powerSet.add(subset);
            }
        }
        return powerSet;

    }

现在让我们来分析一下这个过程：

假设第一次迭代中，我们处理元素“A”：

  • 初始时，powerSet只包含一个空集[ ]。
  • 我们复制这个空集，然后添加“A”,得到["A"]。
  • 将["A"]添加到powerSet，现在powerSet是[ ]，["A"]。

在二次迭代中处理“B”：

  • 现在powerSet有两个子集：[ ]和["A"]。
  • 我们首先复制空集，然后添加“B”,得到["B"]。
  • 然后复制[“A”],然后添加“B”,得到["A","B"]。
  • 然后将这两个新的子集添加到powerSet，现在powerSet有[ ],["A"],["B"],["A","B"]

然后三次迭代重复这个过程就可以了。

下面是回溯方法的代码：

public class PowerSetWithBacktracking {
    public static void main(String[] args) {
        List<String> originalSet = new ArrayList<>();
        originalSet.add("A");
        originalSet.add("B");
        originalSet.add("C");

        List<List<String>> powerSet = new ArrayList<>();
        backtrack(0, originalSet, new ArrayList<>(), powerSet);

        for (List<String> subset : powerSet) {
            System.out.println(subset);
        }
    }

    private static void backtrack(int start, List<String> originalSet, List<String> currentSubset, List<List<String>> powerSet) {
        //将当前子集的副本添加到幂集powerSet中，这里使用new ArrayList<>()来复制当前的子集。
        powerSet.add(new ArrayList<>(currentSubset));
        //遍历集合中的每个元素，从start开始
        for (int i =start;i<originalSet.size();i++){
            //做出选择：包含当前元素
            currentSubset.add(originalSet.get(i));
            //递归调用：移动到下一个元素
            backtrack(i+1,originalSet,currentSubset,powerSet);
            //撤销选择：回溯
            currentSubset.remove(currentSubset.size()-1);

    }
}
}

分析过程：

步骤startcurrentSubsetpowerSet
第一次0[ ][[ ]]
第二次0["a"][[ ]]
第三次1["a","b"][[ ]]
第四次2["a","b","c"][[ ]]
第五次3["a","b","c"][[" "],["a","b","c"],["a","b"],["a"]]
第六次2["a","b"][[" "],["a","b","c"],["a","b"],["a"]]
第七次1["a"][[" "],["a","b","c"],["a","b"],["a"]]
第八次2["a","c"][[" "],["a","b","c"],["a","b"],["a"]]
第九次2["a","c"][[" "],["a","b","c"],["a","b"],["a"],["a","c"]]
第十次1["a"][[" "],["a","b","c"],["a","b"],["a"],["a","c"]]
第十一次1[ ][[" "],["a","b","c"],["a","b"],["a"],["a","c"]]
第十二次1["b"][[" "],["a","b","c"],["a","b"],["a"],["a","c"],["b"]]

 接下来依次推导就行了。整体的思路就是不断递归下一个元素，然后从currentSubset中移除最后添加的元素，进行回溯，准备处理下一个元素。

3.八皇后问题

八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上吗，问有多少种摆法。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解

public class EightQueens {
    private static final int n =8;
    private static int[] queens;//存储皇后的位置
    private static int count =0;//解的计数

    public static void main(String[] args){
        queens=new int[n];
        for (int i =0;i<n;i++){
            queens[i]=-1;//初始化都为-1，表示都没有放皇后
        }
        placeQueens(0);//从第0行开始放置皇后
        System.out.println("");
    }

    private static void placeQueens(int row) {
        if (row==n){
            count++;
            printBoard();
            return;
        }
        for (int col =0;col<n;col++){
            if (isSafe(row,col)){
                queens[row]=col;//在当前位置放置皇后
                placeQueens((row+1));//进入下一行
                queens[row]=-1;//回溯，撤销当前行的皇后放置的位置
            }
        }

    }

    private static boolean isSafe(int row, int col) {
        //检查列是否有冲突
        for (int i =0;i<row;i++ ){
            if (queens[i]==col){
                return false;
            }
        }
        //检查左上对角线是否有冲突
        for (int i =row-1,j=col+1;i>=0&&j>=0;i--,j--){
            if (queens[i]==j){
                return false;
            }
        }
        //检查右下对角线是否有冲突
        for (int i =row-1,j=col+1;i>=0&&j<n;i--,j++){
            if (queens[i]==j){
                return false;
            }
        }
        return true;


    }

    private static void printBoard() {
        System.out.println("第"+count+"种解法");
        for(int i =0;i<n;i++){
            for (int j=0;j<n;j++){
                if (queens[i]==j){
                    System.out.println("Q");
                }else{
                    System.out.println(". ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }
}

过程分析：

回溯发生在两种情况下：

  1. 当前行是最后一行（row==n-1），并且已经尝试了所有可能的列，并且已经找到了一个解决方案，递归将终止，开始回溯
  2. 在递归过程中，当前行不是最后一行，但在下一行无法找到任何安全位置放置皇后。

 4.骑士游历问题

骑士游历问题是指，在国际象棋的棋盘（8行*8列）上，一个马要遍历棋盘，即走到棋盘上的每一格，并且每隔只到达一次。 设码在棋盘的某一位置（x,y）上，按照“走马日”的规则，下一步有8个方向走，如图所示。 若给定起始位置（x0,y0）,使用站和队列探索出一条马遍历棋盘的路径。

 算法步骤：

  • 定义棋盘大小和骑士的可能移动的方式。
  • 创建一个二维数组来表示棋盘，初始值设为-1表示未访问。
  •  编写一个辅助函数来检查当前位置是否合法。
  • 编写一个递归函数来尝试所有可能的移动，使用回溯法来寻找解。
  • 在主函数中调用递归函数，并从指定的起始点开始。


public class KnightTour{
  private static final int N =8;
  private static final int[][] moves={{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};

    public static void main(String[] args) {
        int[][] board =new int[N][N];
        for (int i =0;i<N;i++){
            for (int j =0;j<N;j++){
                board[i][j]=-1;
            }
        }
        //起始点
        int x =0,y =0;
        board[x][y]=0;

        if (!solveKTUtil(board,x,y,1)){
            System.out.println("此解决方案不存在");
        }else{
            printSolution(board);
        }
    }

    private static boolean solveKTUtil(int[][] board, int x, int y, int moveCount) {
        if (moveCount==N*N){
            return true;
        }
        for (int i =0;i<8;i++){
            int nextX =x+moves[i][0];
            int nextY =y+moves[i][1];

            if (isSafe(board,nextX,nextY)){
                board[nextX][nextY]=moveCount;
                if (solveKTUtil(board,nextX,nextY,moveCount+1)){
                    return true;
                }else{
                    board[nextX][nextY]=-1;//回溯
                }
            }
        }
        return false;

    }

    private static boolean isSafe(int[][] board, int X, int Y) {
        return X>=0&&Y>=0&&X<N&&Y<N&&board[X][Y]==-1;
    }
    private static void printSolution(int[][] board){
        for (int i =0;i<N;i++){
            for(int j =0;j<N;j++){
                System.out.print(board[i][j]+" ");
            }
            System.out.println();
        }
    }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/793646.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

kibana连接elasticsearch(版本8.11.3)

kibana连接elasticsearch(版本8.11.3)

前言 elasticsearch在8版本之后就出现了很大变化&#xff0c;由于kibana版本需要需elasticsearch进行版本对象&#xff0c;kibana连接方式也出现了很大变化。我在这里记录下自己的踩坑记录。 服务部署 本文中的服务都是在docker环境中部署的。其中elasticsearch版本和kibana版…
阅读更多...
攻防世界(PHP过滤器过滤)file_include

攻防世界(PHP过滤器过滤)file_include

转换过滤器官方文档&#xff1a;https://www.php.net/manual/zh/filters.convert.php#filters.convert.iconv 这道题因为convert.base64-encode被过滤掉了&#xff0c;所以使用convert.iconv.*过滤器 在激活 iconv 的前提下可以使用 convert.iconv.* 压缩过滤器&#xff0c; 等…
阅读更多...
【Python实战因果推断】31_双重差分2

【Python实战因果推断】31_双重差分2

目录 Canonical Difference-in-Differences Diff-in-Diff with Outcome Growth Canonical Difference-in-Differences 差分法的基本思想是&#xff0c;通过使用受治疗单位的基线&#xff0c;但应用对照单位的结果&#xff08;增长&#xff09;演变&#xff0c;来估算缺失的潜…
阅读更多...
加减计数器

加减计数器

目录 描述 输入描述&#xff1a; 输出描述&#xff1a; 参考代码 描述 请编写一个十进制计数器模块&#xff0c;当mode信号为1&#xff0c;计数器输出信号递增&#xff0c;当mode信号为0&#xff0c;计数器输出信号递减。每次到达0&#xff0c;给出指示信号zero。 模块的接…
阅读更多...
昇思25天学习打卡营第18天|MindNLP ChatGLM-6B StreamChat

昇思25天学习打卡营第18天|MindNLP ChatGLM-6B StreamChat

MindNLP ChatGLM-6B StreamChat MindNLP ChatGLM-6B StreamChat是基于MindNLP框架和ChatGLM-6B模型实现的聊天应用&#xff0c;利用自然语言处理技术&#xff0c;实现与用户的自然语言交流。这样的应用可以广泛应用于智能客服、在线助理和社交聊天等场景。 在当前技术环境下&a…
阅读更多...
鸿蒙语言基础类库：【@ohos.application.testRunner (TestRunner)】 测试

鸿蒙语言基础类库：【@ohos.application.testRunner (TestRunner)】 测试

TestRunner TestRunner模块提供了框架测试的能力。包括准备单元测试环境、运行测试用例。 如果您想实现自己的单元测试框架&#xff0c;您必须继承这个类并覆盖它的所有方法。 说明&#xff1a; 开发前请熟悉鸿蒙开发指导文档&#xff1a;gitee.com/li-shizhen-skin/harmony-…
阅读更多...
法律咨询援助网站

法律咨询援助网站

1 项目介绍 1.1 摘要 随着互联网技术的飞速发展&#xff0c;公众对于便捷、高效的法律咨询服务需求日益增长。传统的法律咨询方式已难以满足人们即时性、多样化的咨询需求&#xff0c;促使法律咨询援助网站应运而生。这些平台旨在通过数字化手段&#xff0c;为用户提供法律知…
阅读更多...
教务管理系统

教务管理系统

教务管理系统 For Free 本项目免费获取&#xff0c;获取方式在后台发送教务管理系统。系统的实现比较简单&#xff0c;主要是对数据库的读取和前端数据调用的表格展示&#xff0c;并没有太多的交互&#xff0c;比较适合初学者学习Flask和数据库的使用&#xff0c;所以免费获取…
阅读更多...
8626 原子量计数

8626 原子量计数

分析&#xff1a; 1. **读取输入**&#xff1a;首先&#xff0c;我们需要读取输入中的第一行&#xff0c;了解有多少个化学式需要处理。之后&#xff0c;对于每个化学式&#xff0c;我们逐行读取并进行处理。 2. **解析化学式**&#xff1a;对于每个化学式&#xff0c;我们需要…
阅读更多...
如何在Ubuntu环境下使用加速器配置Docker环境

如何在Ubuntu环境下使用加速器配置Docker环境

一、安装并打开加速器 这个要根据每个加速器的情况来安装并打开&#xff0c;一般是会开放一个代理端口&#xff0c;比如1087 二、安装Docker https://docs.docker.com/engine/install/debian/#install-using-the-convenience-script 三、配置Docker使用加速器 3.1 修改配置…
阅读更多...
如何处理 PostgreSQL 中由于表锁定导致的并发访问问题？

如何处理 PostgreSQL 中由于表锁定导致的并发访问问题？

文章目录 一、表锁定的类型二、表锁定导致的并发访问问题三、解决方案&#xff08;一&#xff09;使用合适的锁定模式&#xff08;二&#xff09;优化事务处理&#xff08;三&#xff09;避免不必要的锁定&#xff08;四&#xff09;使用索引&#xff08;五&#xff09;监控和分…
阅读更多...
Protobuf: 大数据开发中的高效数据传输利器

Protobuf: 大数据开发中的高效数据传输利器

作为一名大数据开发者&#xff0c;我经常需要处理海量的数据传输和存储。在这个过程中&#xff0c;选择一个高效、可靠的数据序列化工具至关重要。今天&#xff0c;我想和大家分享一下我在项目中使用 Protobuf 的经历。 目录 故事背景Protobuf 简介优点&#xff1a; 实战案例示…
阅读更多...
在【Open3D】点云世界中精准定位，绘制立方体标记特定点位

在【Open3D】点云世界中精准定位，绘制立方体标记特定点位

Open3D精准定位点云特定点&#xff0c;绘制醒目立方体标记&#xff0c;提升数据解读效率与直观性。 Open3D是一个开源的跨平台计算机视觉库&#xff0c;它为开发人员提供了一个易于使用且高性能的3D数据处理平台。 # pcd&#xff1a;传入原始点云图 # point1&#xff1a;要进…
阅读更多...
【HarmonyOS】获取通讯录信息

【HarmonyOS】获取通讯录信息

【HarmonyOS】获取通讯录信息 一、问题背景&#xff1a; 在Android和IOS中&#xff0c;获取手机通讯录信息的方式&#xff0c;一般是申请通讯录权限后&#xff0c;获得手机所有的通讯录列表信息。 在鸿蒙中&#xff0c;因为权限方式安全性提高的变更&#xff1a;将用户权限限…
阅读更多...
springboot 旅游导航系统-计算机毕业设计源码69476

springboot 旅游导航系统-计算机毕业设计源码69476

目 录 第 1 章 引 言 1.1 选题背景 1.2 研究现状 1.3 论文结构安排 第 2 章 系统的需求分析 2.1 系统可行性分析 2.1.1 技术方面可行性分析 2.1.2 经济方面可行性分析 2.1.3 法律方面可行性分析 2.1.4 操作方面可行性分析 2.2 系统功能需求分析 2.3 系统性需求分析…
阅读更多...
【Python实战因果推断】30_双重差分1

【Python实战因果推断】30_双重差分1

目录 Panel Data 在讨论了干预效果异质性之后&#xff0c;是时候转换一下思路&#xff0c;回到平均干预效果上来了。在接下来的几章中&#xff0c;您将学习如何利用面板数据进行因果推断。 面板数据是一种跨时间重复观测的数据结构。在多个时间段观察同一单位&#xff0c;可以…
阅读更多...
347. 前 K 个高频元素（中等）

347. 前 K 个高频元素（中等）

347. 前 K 个高频元素 1. 题目描述2.详细题解3.代码实现3.1 Python3.2 Java 1. 题目描述 题目中转&#xff1a;347. 前 K 个高频元素 2.详细题解 寻找出现频率前 k k k高的元素&#xff0c;因此需要先统计各个元素出现的次数&#xff0c;该步骤时间复杂度为 O ( n ) O(n) O(n)…
阅读更多...
前端-Cookie篇

前端-Cookie篇

文章目录 一、由来什么是Cookie&#xff1f;特点Cookie的类型 二、原理三、Cookie生成机制客户端设置案例 四、属性五、缺陷最后分享一段自己工作中封装的一些关于cookie的公众方法✒️总结 前端Cookie是Web开发中非常重要的一部分&#xff0c;它是服务器发送到用户浏览器并保存…
阅读更多...
如何识别图片文字转化为文本？5个软件帮助你快速提取图片文字

如何识别图片文字转化为文本？5个软件帮助你快速提取图片文字

如何识别图片文字转化为文本&#xff1f;5个软件帮助你快速提取图片文字 将图片中的文字提取为文本是一项非常有用的技能&#xff0c;特别是当你需要处理大量扫描文档、截图或其他图片时。以下是五款能够帮助你快速提取图片文字的软件&#xff1a; 迅捷文字识别 这是一款非…
阅读更多...
对接高德开放平台API

对接高德开放平台API

高德开放平台API&#xff1a; https://lbs.amap.com/ 一、天气查询 天气查询: https://lbs.amap.com/api/webservice/guide/api/weatherinfo adcode城市码表下载: https://lbs.amap.com/api/webservice/download Component public class WeatherUtil {Resourceprivate GdCon…
阅读更多...
最新文章

Copyright @ 2022~2023