小白带你学--回溯算法

微信公众号:小白算法
关注可了解更多算法,并能领取免费资料。问题或建议,请公众号留言;
文末有资料领取
上一期算法回顾--贪婪法:https://mp.weixin.qq.com/s/978Tdplj3IaSG2dc-5F-aw

算法导读

本期算法讲解思路:
白话算法->算法思路->实例:八皇后问题->实例:01背包问题->算法教你玩数独

白话算法

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

白话:回溯法可以理解为通过选择不同的岔路口寻找目的地,一个岔路口一个岔路口的去尝试找到目的地。如果走错了路,继续返回来找到岔路口的另一条路,直到找到目的地。

实例一:八皇后问题

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

小白面试经:理解如何解决这个问题,回溯法的精髓已经get。如果只是想了解算法面试知识,知道解决这个问题就能完成你的算法积累了。想快速掌握算法,可以直接查看解题思路的四个步骤

八皇后问题解题思路:

问题简化:下面我们将八皇后问题转化为四皇后问题,并用回溯法来找到它的解
目的:在4x4棋盘上,使得4个皇后不能在同行同列以及同斜线上。

step1
尝试先放置第一枚皇后,被涂黑的地方是不能放皇后

step2
第二行的皇后只能放在第三格或第四格,比方我们放第三格,则:

此时我们也能理解为什么叫皇后问题了,皇后旁边容不下其他皇后。而在同一个房间放下四个皇后确实是个不容易的问题。

step3
可以看到再难以放下第三个皇后,此时我们就要用到回溯算法了。我们把第二个皇后更改位置,此时我们能放下第三枚皇后了。

step4
虽然是能放置第三个皇后,但是第四个皇后又无路可走了。返回上层调用(3号皇后),而3号也别无可去,继续回溯上层调用(2号),2号已然无路可去,继续回溯上层(1号),于是1号皇后改变位置如下,继续回溯。

这就是回溯算法的精髓,虽然没有最终把问题解决,但是可以剧透一波,就是根据这个算法,最终能够把四位皇后放在4x4的棋盘里。也能用同样的方法解决了八皇后问题。下面我们用代码解决八皇后问题。

代码实现八皇后问题

我们将算法也设置成两步,
第一步 我们要判断每次输入的皇后是否在同一行同一列,或者同一斜线上。


bool is_ok(int row){            //判断设置的皇后是否在同一行,同一列,或者同一斜线上
    for (int j=0;j<row;j++)
    {
        if (queen[row]==queen[j]||row-queen[row]==j-queen[j]||row+queen[row]==j+queen[j])
            return false;       
    }
    return true;
}

第二步 我们用十行代码来进入我们核心算法

void back_tracking(int row=0)    //算法函数,从第0行开始遍历
{
    if (row==n)
        t ++;               //判断若遍历完成,就进行计数     
        for (int col=0;col<n;col++)     //遍历棋盘每一列
        {
            queen[row] = col;           //将皇后的位置记录在数组
            if (is_ok(row))             //判断皇后的位置是否有冲突
                back_tracking(row+1);   //递归,计算下一个皇后的位置
        }
}

代码实现算法也是比较简单的,主要还是看是否掌握算法思想。

实例二:01背包问题

有N件物品和一个容量为V的背包。第i件物品的价格(即体积,下同)是w[i],价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

这是最基础的背包问题,总的来说就是:选还是不选,这是个问题

相当于用f[i][j]表示前i个物品装入容量为v的背包中所可以获得的最大价值。

对于一个物品,只有两种情况

情况一: 第i件不放进去,这时所得价值为:f[i-1][v]

情况二: 第i件放进去,这时所得价值为:f[i-1][v-c[i]]+w[i]

接下来的实例属于算法进阶,可做了解
提两点,
1.与上期贪婪法所解决的背包问题相比,回溯法将能更能顾及寻找全局最优。
2.背包问题与八皇后问题所用的算法虽然都是回溯法,但是他们的目的不一样,八皇后只要求把所有的棋子放在棋盘上(即只需解决深度最优)。而01背包问题不仅需要让物品都放进背包,而且要使得物品质量最大,在八皇后问题上多提出了一个限制。

问题的解空间

用回溯法解问题时,应明确定义问题的解空间。问题的解空间至少包含问题的一个(最优)解。对于 n=3 时的 0/1 背包问题,可用一棵完全二叉树表示解空间,如图所示:


1表示选取,0表示不选

求解步骤

1)针对所给问题,定义问题的解空间;

2)确定易于搜索的解空间结构;

3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。

常用的剪枝函数:用约束函数在扩展结点处剪去不满足约束的子树;用限界函数剪去得不到最优解的子树。

回溯法对解空间做深度优先搜索时,有递归回溯和迭代回溯(非递归)两种方法,但一般情况下用递归方法实现回溯法。

算法描述

解 0/1 背包问题的回溯法在搜索解空间树时,只要其左儿子结点是一个可行结点,搜索就进入其左子树。当右子树中有可能包含最优解时才进入右子树搜索。否则将右子树剪去。

我们直接上手代码解决这个问题

算法部分

void dfs(int i,int cv,int cw)
{  //cw当前包内物品重量,cv当前包内物品价值
    if(i>n)   
    {
        if(cv>bestval)             //是否超过了最大价值
        {
            bestval=cv;            //得到最大价值
            for(i=1;i<=n;i++)      
                bestx[i]=x[i];      //得到选中的物品
        }
    }
    else 
        for(int j=0;j<=1;j++)    //枚举物体i所有可能的路径,
        {
            x[i]=j;      
            if(cw+x[i]*w[i]<=TotCap)  //满足约束,继续向子节点探索
            {
                cw+=w[i]*x[i];
                cv+=val[i]*x[i];
                dfs(i+1,cv,cw);
                cw-=w[i]*x[i];    //回溯上一层物体的选择情况
                cv-=val[i]*x[i];
            }
        }
}

主函数部分

int main()
{
    int i;
    bestval=0; 
    cout<<"请输入背包最大容量:"<<endl;;
    cin>>TotCap;
    cout<<"请输入物品个数:"<<endl;
    cin>>n;
    cout<<"请依次输入物品的重量:"<<endl;
    for(i=1;i<=n;i++) 
        cin>>w[i];
    cout<<"请依次输入物品的价值:"<<endl;
    for(i=1;i<=n;i++) 
        cin>>val[i];
    dfs(1,0,0);
    cout<<"最大价值为:"<<endl;
    cout<<bestval<<endl;
    cout<<"被选中的物品的标号依次是:"<<endl;

    for(i=1;i<=n;i++)
        if(bestx[i]==1) 
            cout<<i<<" ";
    cout<<endl;

    
    return 0;
}

回溯算法带你玩数独

我们可以想象,我们经常玩的数独问题其实就是一个的八皇后问题。在9宫格数独的约束为每一行每一列不能出现相同的数。这里我们限于篇幅,不将细讲代码了。

#include <iostream>
using namespace std;
#define   LEN  9
int a[LEN][LEN] = {0};


//查询该行里是否有这个值
bool  Isvaild(int  count)
{
   int i = count/9;
   int j = count%9;    
   //检测行
   for(int iter = 0;iter!=j;iter++)
   {      
       if(a[i][iter]==a[i][j])
       {
          return 1;
       }
   }
   
   //检测列
   for(int iter=0;iter!=i;iter++)
   {
        if(a[iter][j]==a[i][j])
        {
          return 1;
        }
   }
   
   //检测九宫   
   for(int p =i/3*3;p<(i/3+1)*3;p++)
   {
    for(int q=j/3*3;q<(j/3+1)*3;q++)
    {      
         if(p==i&&j==q)
         {         
           continue;
         }     
         if(a[p][q]==a[i][j])
            {
                return 1;
            }
   }
   }
   return 0;
}
void print()
{
    cout<<"数度的解集为"<<":"<<endl;
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
        {

            cout<<a[i][j]<<" ";
        }

        cout<<endl;
    }

  cout<<endl;
}

void  first_chek(int count)
{
    if(81 ==count)
    {
        print();
        return;
    }

    int  i = count/9;   //列
    int  j  = count%9;   //行
  
    if(a[i][j]==0)
     {
        for(int n=1;n<=9;n++)
        {
            a[i][j] =  n;

            if(!Isvaild(count))  //这个值不冲突
            {
                first_chek(count+1)           }

        }      
         a[i][j] = 0;
    }  

    else
    {       
        first_chek(count+1);
    }
}


int main()
{
    a[1][2] = 3;
    a[5][3] = 9;
    a[8][8] = 1;
    a[4][4] = 4;
    first_chek(0);
    return 0;
}

其中2行3列、6行4列、9行9列、5行5列数字为已知。最后结果,


总结

回溯法属于深度优先搜索,由于是全局搜索,复杂度相对高。
如果你想了解更深的了解回溯算法,可以翻阅相关的数据结构书籍。当然,如果你选择深入了解这个算法,必然会枯燥。

回溯算法代码:https://github.com/haixiansheng/algorithm

如果只是想对算法进行了解,你就可以选择关注“小白算法”公众号,我们每周都会有新的算法介绍,并有相关学习资料赠送。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,839评论 6 482
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,543评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 153,116评论 0 344
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,371评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,384评论 5 374
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,111评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,416评论 3 400
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,053评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,558评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,007评论 2 325
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,117评论 1 334
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,756评论 4 324
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,324评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,315评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,539评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,578评论 2 355
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,877评论 2 345

推荐阅读更多精彩内容