JAVA中的回溯算法解空间树,八皇后问题以及骑士游历问题超详解
1.回溯算法的概念
回溯算法顾名思义就是有回溯的算法
回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的,规模较大的问题都可以使用回溯法,有“通用解题方法”的美称。
回溯算法的核心思想是:
- 问题分解:将原问题分解成若干个规模较小的子问题。
- 候选解的生成:从根节点开始,逐层生成候选解。
- 活节点:当前正在扩展的节点称为活节点。
- 死节点:当前扩展的节点如果已经确定不能得到问题的解,则该节点称为死节点。
- 剪枝:根据问题的限制条件,对已经确定的死节点进行剪枝。
2.回溯算法解空间树的问题
典型案例:
集合求幂集的解空间树
意思就是一个集合s所有的子集的集合
问题:求集合S={1,2,3}的所有子集,依次选择每个元素的过程就是一棵树,如图所示
在树中,由从根节点到叶子结点的每条路径上的权值组成三元组(0,0,0)~(1,1,1)都是解,如(0,0,1)表示子集{B,C},共=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)!