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);
}
}
}
分析过程：
步骤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 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();
}
}
}
Ongwu博客 版权声明：以上内容未经允许不得转载！授权事宜或对内容有异议或投诉，请联系站长，将尽快回复您，谢谢合作！