回溯算法的思想以及主要应用

时间:2022-08-01 01:09:59


回溯算法的思想以及主要应用

0、概念

0.1、定义

回溯法(back tracking)(探索与回溯法)是一种选优搜索法,又称为试探法。按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回到上一步,重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。

0.2、应用

「回溯是递归的副产品,只要有递归就会有回溯」,所以回溯法也经常和二叉树遍历,深度优先搜索混在一起,因为这两种方式都是用了递归,回溯法就是暴力搜索,并不是什么高效的算法,最多再剪枝一下。

回溯算法能解决如下问题:

  1. 组合问题:N个数里面按一定规则找出k个数的集合
  2. 排列问题:N个数按一定规则全排列,有几种排列方式
  3. 切割问题:一个字符串按一定规则有几种切割方式
  4. 子集问题:一个N个数的集合里有多少符合条件的子集
  5. 棋盘问题:N皇后,解数独等等

0.3、思路

解决一个回溯问题,实际上就是一个决策树的遍历过程,需要考虑下面三个环节:
1、路径:也就是已经做出的选择。
2、选择列表:也就是你当前可以做的选择。
3、结束条件:也就是到达决策树底层,无法再做选择的条件。


1、与枚举法的关系

1.1、联系

我是这么人为的,回溯算法是枚举算法的特列,相当于在枚举过程加了限定条件(约束函数和限界函数),大大简化了枚举过程中重复的数据。

1.2、区别

区别是:枚举相当于暴力破解的范畴,在复杂数据求解过程是最简单的想法,回溯在求解过程会裁剪。


2、例子

2.1、八皇后问题

八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后(棋子),使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上。
解法如下:

#include<iostream>
#include<Math.h>
using namespace std;
int count=0;//解法个数 
bool is_ok(int row,int *queen){   //判断设置的皇后是否在同一行,同一列,或者同一斜线上
    for (int j=0;j<row;j++)
    {
        if (queen[row]==queen[j]||abs(row-j)==abs(queen[row]-queen[j]))
            return false;       
    }
    return true;
}
void back_tracking(int n,int *queen,int row=0)    //算法函数,从第0行开始遍历
{
    if (row==n){//表示放完了n个皇后 
        count++;//记录解法个数 
        cout<<endl;
        for(int i=n-1;i>=0;i--){
            cout<<queen[i]<<" ";
        }
        return;
    }    
                      //判断若遍历完成,就进行计数     
    for (int col=0;col<n;col++)     //遍历棋盘每一列
    {
        queen[row] = col;           //将皇后的位置记录在数组
        if (is_ok(row,queen))             //判断皇后的位置是否有冲突
            back_tracking(n,queen,row+1);   //递归,计算下一个皇后的位置
    }
}
int main(){
    int n;
    cout<<"输入皇后数量:"; 
    cin>>n;
    int queen[100]={-1};//皇后默认8个 
    back_tracking(n,queen,0) ;
    cout<<"总解法"<<count<<endl; 

    return 0;
}

有上述还可以引申为 :解数独。

2.2、货物装载

最简单的装载问题 描述: 给定n个货物、每个货物重量为Wi,一艘船的载货总重量为W。问如何选择货物装载使得船尽可能多的装载货物而不翻船? 输入:货物数量n,每个货物的重量 输出:选择的货物i、最大的货物装载量。
这里的约束函数和限界函数要怎么确定决定了算法的效率问题,这也是比穷举、枚举法厉害的地步。
代码如下(示例):

int cw=0;//表示当前船上装的货物重量
int bestw=0;//能装载的最大货物重量  
int bestx[100]={0}; //记录所装货物

void Backtrack(int t,int *w,int W,int n,int r,int *x){//t表示层级,w表示货物的重量,W表示船最大载重,n输入的货物数
//r表示剩余货物的重量 ,x[i]表示货物装不装 
    if(t>n-1){//已经搜索到末尾
        if(cw>bestw&&cw<=W){
            bestw=cw;//最大的重量记录
            for(int i=0;i<n;i++){
                bestx[i]=x[i];
            } 
        }        
        return; 

    }else{
        r=r-w[t];//已经访问该货物了。它不属于剩下的物品了   
        if(cw<W){//还能装下货物
            x[t]=1 ;
            cw=cw+w[t];//装、左子树  
            Backtrack(t+1,w,W,n,r,x); 
            cw=cw-w[t];//不装、右子树 cw之前添加了w,必须减回去

        }
        if(r+cw>bestw)//有希望
        {
            x[t]=0; 
            Backtrack(t+1,w,W,n,r,x);
        }   
        r=r+w[t];        
    }
}


int main(){
    int n,W;
    cout<<"请输入n件货物及船的最大载重量W:";
    cin>>n>>W;
    int w[n];
    cout<<"请输入"<<n<<"件物品的重量:"; 
    for(int i=0;i<n;i++){
        cin>>w[i];  
    }
    Backtrack(0,w,W,n); 
    cout<<"最大能装载货量为:"<<bestw;


    return 0;
}

3、总结

3.1 总结模板

一般模板如下:

def dfs(输入):
    if 当前状态为边界:
        记录或输出
        return 
    for i in range(len(输入)):#横向遍历所有子节点
        目前遍历的当前子节点
        if 子状态满足约束条件:
            dfs(子状态)

4、引用

1、回溯算法详细总结
2、彻底搞懂回溯法(本文真的很详细)