算法基础之回溯

傷城~ 2022-09-07 00:08 320阅读 0赞

### 算法基础之回溯（C++示例） ###

回溯法（BackTracking）也叫试探法，是一种选优搜索法，按选优条件向前搜索，以达到目标。若探索到某一步，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

回溯算法类似于枚举的过程，当搜索时遇到不满足条件，回退到上一个，尝试别的路径。

回溯法从问题本身出发，寻找可能实现的所有情况。和穷举法的思想相近，不同在于穷举法是将所有的情况都列举出来以后再一一筛选，而回溯法在列举过程如果发现当前情况根本不可能存在，就停止后续的所有工作，返回上一步进行新的尝试。

回溯法常与和递归法结合使用，在回溯法中可以看到有递归的身影。

八皇后问题、迷宫问题是回溯算法的应用场景。

**例1、**列举集合 \{1,2,3\} 中所有子集的问题

这个问题就可以使用回溯算法。从集合的开头元素开始，对每个元素都有两种选择：取还是舍。当确定了一个元素的取舍之后，再进行下一个元素，直到集合最后一个元素。其中的每个操作都可以看作是一次尝试，每次尝试都可以得出一个结果。将得到的结果综合起来，就是集合的所有子集。

源码如下：

#include <stdio.h>
    //设置一个数组，数组的下标表示集合中的元素，所以数组只用下标为1，2，3的空间
    int set[5];
    //i代表数组下标，n表示集合中最大的元素值
    void PowerSet(int i,int n){
        //当i>n时，说明集合中所有的元素都做了选择，开始判断
        if (i>n) {
            for (int j=1; j<=n; j++) {
                //如果树组中存放的是 1，说明在当初尝试时，选择取该元素，即对应的数组下标，所以，可以输出
                if (set[j]==1) {
                    printf("%d ",j);
                }
            }
            printf("\n");
        }else{
            //如果选择要该元素，对应的数组单元中赋值为1；反之，赋值为0。然后继续向下探索
            set[i]=1;PowerSet(i+1, n);
            set[i]=0;PowerSet(i+1, n);
        }
    }
    int main() {
        int n=3;
        for (int i=0; i<5; i++) {
            set[i]=0;
        }
        PowerSet(1, n);
        return 0;
    }

运行结果如下：

1 2 3  
1 2  
1 3  
1  
2 3  
2  
3

**例2、**八皇后问题

该问题由国际西洋棋棋手马克斯·贝瑟尔于 1848 年提出：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。其中一种放法（0代表皇后）：

![20210821160009281.png][]

算法解决思路：

1.  从棋盘的第一行开始，从第一个位置开始，依次判断当前位置是否能够放置皇后，判断的依据为：同该行之前的所有行中皇后的所在位置进行比较，如果在同一列，或者在同一条斜线上（斜线有两条，为正方形的两个对角线），都不符合要求，继续检验后序的位置。
2.  如果该行所有位置都不符合要求，则回溯到前一行，改变皇后的位置，继续试探。
3.  如果试探到最后一行，所有皇后摆放完毕，则直接打印出 8\*8 的棋盘。最后一定要记得将棋盘恢复原样，避免影响下一次摆放。

源码如下：

#include<iostream>
    using namespace std;
    
    int count = 0;
    int chess[8][8] = {0};
    
    void Print(){
    	printf("解法%d：\n", count);
    	for(int i = 0; i < 8; i++){
    		for(int j = 0; j < 8; j++){
    			if(chess[i][j] == 1)
    				cout << "0 ";//皇后
    			else cout << "* ";
    		}
    		cout << endl;
    	}
    	cout << endl;
    }
    
    bool notDanger(int row, int col){
    	int i, j;
    	for(i = 0; i < 8; i++){	//检查列 
    		if(chess[i][col] == 1)
    			return false;
    	}	
    	for(i = row, j = col; i >=0 && j >=0; i--, j--){	//左对角线 
    		if(chess[i][j] == 1)
    			return false;
    	}	
    	for(i = row, j = col; i >= 0 && j < 8; i--, j++){	//右对角线 
    		if(chess[i][j] == 1)
    			return false;
    	}	
    	return true;
    }
    
    void EightQueen(int row){
    	if(row > 7){	//8行遍历结束 
    		count++;
    		Print();
    		return;
    	}
    	for(int col = 0; col < 8; col++){	//对第row行的每一列尝试赋值 
    		if(notDanger(row, col)){
    			chess[row][col] = 1;
    			EightQueen(row+1);	//每行只有一个 
    			chess[row][col] = 0; //复原 
    		}
    	}
    }
    
    int main(){
    	EightQueen(0);
    	printf("共%d种解法\n", count);
    	return 0; 
    }

运行效果如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70][]

**例3、迷宫问题**

问题描述

迷宫问题是回溯法的一种应用。迷宫问题的描述为：假设主体放在一个迷宫地图入口处，迷宫中有许多墙，使得大多数的路径都被挡住而无法行进。主体可以通过遍历所有可能到出口的路径来到达出口。当主体走错路时需要将走错的路径记录下来，避免下次走重复的路径，直到找到出口。主体需遵从如下三个原则：

一次步进只能走一格；  
    遇到路径堵塞后，退后直到找到另一条路径可行；  
    走过的路径记录下来，不会再走第二次。

先创建一个二维数组Map\[\]\[\]并进行初始化，Map\[i\]\[j\]=1表示该位置是墙体，Map\[i\]\[j\]=0 表示该位置是路。假设主体（人、动物或者飞行器）放在一个迷宫地图入口处，按上述原则在寻找出口路径。

源码如下：

#include <iostream>
    using namespace std;
    
    # define UP 0 //定义上
    # define DOWN 1 //定义下
    # define LEFT 2 //定义左
    # define RIGHT 3 //定义右
    
    # define MAP_MAX 10 //定义最大地图
    int map[MAP_MAX][MAP_MAX] =
    {
        {1,1,1,2,1,1,1,1,1,1},
        {1,0,0,0,1,0,1,1,1,1},
        {1,0,1,0,1,0,1,1,1,1},
        {1,0,1,0,0,0,0,0,1,1},
        {1,0,1,0,1,1,0,1,1,1},
        {1,0,1,0,0,1,0,1,1,1},
        {1,0,1,1,0,1,0,0,0,1},
        {1,0,1,1,1,1,1,1,0,1},
        {1,0,0,0,0,0,0,0,0,1},// 
        {1,1,1,1,1,1,1,1,0,1}//1是墙 ，0是路 ；出发点标2【注*】 
    };
    
    /*
        打印地图
    */
    void print_map()
    {
        int i,j;
        char emt[]=" #R";
        //定义显示的数组
        putchar(' ');
        for(j=0; j<MAP_MAX; j++)
        {
            printf(" %d", j);
        }
        putchar('\n');
        for(i=0; i<MAP_MAX; i++)
        {
            printf("%d ", i);
            for(j=0; j<MAP_MAX; j++)
            {
                printf("%c ", emt[map[i][j]]);
            }
            putchar('\n');
        }
    }
    
    /*
        单纯的移动，并且进行值的改变
    */
    void move(int &x, int &y, int d)
    {
        switch(d)
        {
        case UP:
            x--;
            break;
        case DOWN:
            x++;
            break;
        case LEFT:
            y--;
            break;
        case RIGHT:
            y++;
            break;
        }
    }
    /*
        检查下一步是否可行
        x，y点开始
        d方向
    */
    int inspect(int x,int y,int d)
    {
        // printf("%d %d %d\n", x,y,d);
        move(x,y,d);
    
        if(x<0 || y<0|| x>=MAP_MAX || y>=MAP_MAX || map[x][y]!=0)
        {
            return 0;
        }
    
        return 1;
    }
    
    void print_pro(int s[2], int e[2], int n){
        /*打印过程*/
        putchar('\n'); //
        printf("当前:(%d, %d) 终点:(%d, %d) 步数:%d\n", s[0],s[1],e[0],e[1],n);
        print_map();
    }
    
    /*
        走迷宫（递归回溯所有可能都走）
        s是开始坐标
        e是结束坐标
        n当前第几步
    */
    int mazes(int s[2],int e[2],int n)
    {
        if(s[0]==e[0] && s[1]==e[1]){
            print_pro(s,e,n);
        }
    
        int i;
        for(i=0; i<4; i++)//向四个方向同时走
        {
            if(inspect(s[0],s[1],i))//检查i方向是否可以行得通
            {
                int tx = s[0], ty = s[1];//设置临时变量，防止数据混乱
                move(tx,ty,i);//向i方向移动一步
                map[tx][ty] = 2;//标记已走
                int ta[2] = {tx,ty};//传值变量
                mazes(ta,e,n+1);
                map[tx][ty] = 0;//取消标记
            }
        }
    }
    
    int main()
    {
        int n = 0;//初始步数
        int s[2] = {0,3};//s初始位置【注*】 
        int e[2] = {9,8};//e终止位置 
        mazes(s,e,n);//调用走迷宫
        putchar('\n');
        return 0;
    }

运行效果如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70 1][]

[20210821160009281.png]: /images/20220829/4329038a93ed4a329dcdfa64fa3cc048.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70]: /images/20220829/4105183b75904f8d958665211c914574.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NuZHMxMjM_size_16_color_FFFFFF_t_70 1]: /images/20220829/0369efb40e834a198628a966b2a1ab7c.png