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

🕗 发布于 2024-07-12 07:14 算法

1.回溯算法的概念

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

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

回溯算法的核心思想是：

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

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);

    }
}
}

分析过程：

步骤	start	currentSubset	powerSet
第一次	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();
    }
}

过程分析：

回溯发生在两种情况下：

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

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();
        }
    }
}

原文地址：https://blog.csdn.net/2302_79993788/article/details/140290767

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：无人机控制的创新解决方案：STM32微控制器的多任务处理（内附资料）
下一篇：maven私有镜像仓库nexus部署使用

leetcode289:生命游戏
根据，简称为，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。给定一个包含m × n个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1即为（live），或0即为
阅读更多2024-10-20
MongoDB数据恢复
注意：两个MongoDB的版本要一致，本文使用的是mongo:4.2.24。先把K8S上面的MongoDB 容器停止（可以把副本改成0）。1、将容器挂载MongoDB的数据目录备份到本地。经常是数据文
阅读更多2024-10-20
C#中实现事务
C#中实现事务
阅读更多2024-10-20
【LeetCode每日一题】——560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。
阅读更多2024-10-20
「漏洞复现」满客宝智慧食堂系统 selectUserByOrgId 未授权访问漏洞
请勿利用文章内的相关技术从事非法测试，由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失，均由使用者本人负责，作者不为此承担任何责任。工具来自网络，安全性自测，如有侵权请联系删除。本次
阅读更多2024-10-20
React面试题目（从基本到高级）
React前端面试常见题目涵盖了React的基础概念、组件、状态管理、生命周期、性能优化等多个方面。
阅读更多2024-10-20
12.个人博客系统（Java项目基于spring和vue）
1 在校学习的学生，可用于日常学习使用或是毕业设计使用 2 毕业一到两年的开发人员，用于锻炼自己的独立功能模块设计能力，增强代码编写能力。 3 亦可以部署为商化项目使用。 4 需要完整资料及源码
阅读更多2024-10-20
YoloV8改进策略：注意力改进|DeBiFormer，可变形双级路由注意力|引入DeBiLevelRoutingAttention注意力模块（全网首发）
本次改进的核心在于将DeBiLevelRoutingAttention模块嵌入到YoloV8的主干网络中，具体位置是在SPPF（Spatial Pyramid Pooling Fast）模块之后。这一
阅读更多2024-10-20
word取消自动单词首字母大写
情况说明：在word输入单词后首字母会自动变成大写取消单词首字母大写步骤：（1）点击菜单栏文件（2）点击“更多”——>“选项”（3）点击“校对”——>“自动更正选项”（4）取消“句首字母大
阅读更多2024-10-20
web前端网页用户注册页面
【代码】web前端网页用户注册页面。
阅读更多2024-10-20

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

1.回溯算法的概念

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

3.八皇后问题

4.骑士游历问题

相关文章