【算法学习】再谈回溯法
02.01背包：子集树
03.旅行售货商：排序树
04.总结
壹
回溯法介绍
回溯法，又叫试探法，是一种寻找最优解的暴力搜寻法，也比较容易理解（适合小白学习）。但是，由于暴力，回溯法的时间复杂度较高，因此在比较一些数字较大的问题时，比如上次我们提到的最短路径问题等，运行时间一般比较长。
在回溯法中，深度优先搜索是一种很重要的工具——说到这是不是想起来上次的最短路径问题的DFS解法了？了解了DFS，就比较容易理解回溯法。
简单地介绍一下DFS，用一句话概括，就是“不撞南墙不回头”。（这句话也适用于回溯法）
它的基本思想是：
（1）某一种可能情况向前探索，并生成一个子节点。
（2）过程中，一旦发现原来的选择不符合要求，就回溯至父亲结点，然后重新选择另一方向，再次生成子结点，继续向前探索。
（3）如此反复进行，直至求得最优解。
我们再回到回溯法。
回溯法基本思想是：
（1）针对具体问题，定义问题的解空间；
（2）确定易于搜索的解空间结构（数据结构的选择）。
（3）一般以DFS的方式搜索解空间。
（4）在搜索过程中，可以使用剪枝函数等来优化算法。
是不是看到了几个生词？没关系，我们再解释一下。
解空间：顾名思义，就是一个问题的所有解的集合。（但别忘了，这离我们要求的最优解还差很远！）
剪枝函数：用约束函数和限界函数剪去得不到最优解的子树，统称为剪枝函数。
慢着，又多了几个生词！
别着急，我们继续看。
约束条件：有效解的要求，即题目的要求。
约束函数：减去不满足约束条件的子树的函数
限界函数：去掉得不到最优解的结点的函数
扩展结点：当前正在产生子结点的结点称为扩展结点
那么，为什么我们这里要提到树呢？
因为我们用回溯法处理的解空间常常可以分为这两种（或者说可以采取这两种方法）：
子集树：当所给问题是从集合中找出满足某种性质的子集时，相应的解空间树称为子集树。
排列树：当所给问题事从集合中确定满足某种性质的排列时，相应的解空间树称为排列树。
解释了这么多名词，相信大家对回溯法都有了一点基础的了解。但很多同学可能还有一个很大的问题：
回溯法到底和DFS有什么区别？
其实我认为吧，真没什么区别。真要说的话，DFS是一种遍历搜索图、树等数据结构的一种算法，更像一种工具；而回溯法则是为了解决问题不断地生成又放弃一些解决方案（解空间在搜索问题的过程中动态产生是回溯法的一个重要特点），直至找到最优解或搜索完毕为止的一种方法，更像一种指导思想，在解空间中利用DFS进行全面的搜索。
我觉得也没必要太纠结这两者的区别。。。（不是因为我搞不懂！！！）
还有就是关于优化的剪枝函数。
剪枝就是在搜索过程中利用过滤条件来剪去完全不用考虑（已经判断这条路走下去得不到最优解）的搜索路径，从而避免了一些不必要的搜索，优化算法求解速度，当然还必须得保证结果的正确性。
应用到回溯算法中，我们可以提前判断当前路径是否能产生结果集，如果否，就可以提前回溯。而这也叫做可行性剪枝。
另外还有一种叫做最优性剪枝，每次记录当前得到的最优值，如果当前结点已经无法产生比当前最优解更优的解时，可以提前回溯。
然而，剪枝的过滤条件不好找，想通过剪枝优化来提高算法高效性，又要保证结果正确性，还要保证剪枝的准确性。是非常难得的。哎，我太难了。。。
了解完回溯法的一些概念后，我们来就着题目讲解吧~~
贰
01背包：子集树
之前我们提到了，用回溯法处理解空间大致可以分为两种（当然也可以不用这两种），其中一种是子集树。01背包问题就是由子集树解决的一个经典问题。
我们贴一张图来说明：
因为我们考虑的是找子集，所以每个物品只有选与不选两种状态，因此解空间是一个二叉树。在这个树中，每一层的边表示对一个物品的选择与否。
举个例子，选择第一层点0与左边点1间的边，表示选择1号物品，也就是选择左子树走下去；如果不选择1号物品入包，则进入右子树，选择右边点1。那么，一共有n件物品，就有n层的边，n+1层点。最后一层的每一个叶结点分别表示一种选择法，一共有2^个叶结点，即解空间中共有2^n种解，我们要在这些叶结点中选择最佳结点。
我们先给出利用回溯法搜索子树集的伪代码框架：
void search(层数)
{
If(搜索到最底层)
打印出结果解;
Else for(遍历当前层解)
{
If(合适解)继续搜索;
撤消当前状态的影响;//回溯
}
}
来看看题干：
01背包问题。
某舟同学打算去拜访某欣同学，他打算带一背包的巧克力作为礼物。他希望装进的巧克力总价值最高，这样可能比较好吃。然而小舟体力有限，巧克力包不能太重，只能有8kg。
可供选择的巧克力如下：
1 费列罗 4kg $4500
2 好时之点 5kg $5700
3 德芙 2kg $2250
4 Cudie（西班牙） 1kg $1100
5 自制 6kg $6700
（某欣不会介意巧克力太重太贵的）
玩笑开玩了。。。不知道看懂题目没？不懂也得懂~
回溯法讲究“暴力”。我们从暴力的角度思考，想把所有的尽量装满背包的搭配都找出来，标记每一种装法（每一个解）最大value，从而找到最优解。
我们从第一种巧克力开始装，然后找下一个，判断能否装入，再递归，到达边界，比较，记录较优解，回溯，继续往下找。。。循环。
从子集树的角度将，我们优先选择走左子树，也就是入包；当走到叶结点或不符合约束的重量条件时，回溯到父结点，进入右结点，最后遍历全树。
判断能否装入后可以用一个book数组来标记是否选择入包。（我第一次自己编时就忘了！！不断通过循环来调用寻找下一个结点的函数，实在是太傻了，明明这个方法超级常用！！果然小白。。。）
再根据这个写出01背包问题的代码（注释中有详解，请放心食用）：
//01背包问题——回溯法子集树
#include <iostream>
using namespace std;
int n,bag_v,bag_w;
int bag[100],x[100],w[100],val[100];
void search(int cur,int cur_v,int cur_w)
{ //search递归函数，当前current节点的价值为current value，重量为current weight
if(cur>n) //判断边界
{
if(cur_v>bag_v) //是否超过了最大价值
{
bag_v=cur_v; //得到最大价值
for(int i=1;i<=n;i++)
bag[i]=x[i]; //x表示当前是否被选中，将选中的物品存入bag中
}
}
else
for(int j=0;j<=1;j++) //遍历当前解层:是否选择该物品
{
x[cur]=j;
if(cur_w+x[cur]*w[cur]<=bag_w) //满足重量约束,继续向前寻找配对
{
cur_w+=w[cur]*x[cur];
cur_v+=val[cur]*x[cur];
search(cur+1,cur_v,cur_w);//递归，下一件物品
//清楚痕迹，回溯上一层
cur_w-=w[cur]*x[cur];
cur_v-=val[cur]*x[cur];
x[cur]=0;
}
}
}
int main()
{
int i;
bag_v=0; //初始化背包最大价值
//输入数据
cout<<"请输入背包最大容量:"<<endl;;
cin>>bag_w;
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];
search(1,0,0);
cout<<"最大价值为:"<<endl;
cout<<bag_v<<endl;
cout<<"物品的编号依次为:"<<endl;
for(i=1;i<=n;i++)
if(bag[i]==1)
cout<<i<<" ";
cout<<endl;
return 0;
}
我们再来略微讲解一下如何优化。
我们可以用一个上界函数bound():当前价值+剩余容量可容纳的最大价值，去和目前的背包最大价值（也就是最优解）比较，如果bound（）更小，那就没有继续搜索的意义了，剪去左子树，即不选择当前物品，进入右子树。
因为物品只有选与不选2个决策，而总共有n个物品，所以时间复杂度为O（2^n）。
因为递归栈最多达到n层，而且存储所有物品的信息也只需要常数个一维数组，所以最终的空间复杂度为O(n)。
那么，我们如何计算这个“剩余容量可容纳的最大价值”呢？
首先，我们先将物品按照其单位重量价值从大到小排序，此后就按照顺序考虑各个物品。
接下来，我们贴代码讲解。（对不起我也是网上看来的呜呜呜）
if(cur_w+w[cur]<=bag_w)//将物品cur放入背包,搜索左子树,即选择当前物品
{
cur_w+=w[cur];//同步更新当前背包的重量
cur_v+=val[cur];//同步更新当前背包的总价值
put[cur]=1;
search(cur+1,cur_v,cur_w);//深度搜索进入下一层
cur_w-=w[cur];//回溯复原
cur_v-=val[cur];//回溯复原
}
if(bound(cur+1,cur_v,cur_w)>bag_v)//如若符合条件则搜索右子树,即不选择当前物品
{
put[cur]=0;
search(cur+1,cur_v,cur_w);
}当i<=n，重量超过限制时，leftw为负，我们得到的是一个达不到的理想最大价值，因为此时最后放入的物品单位价值较高，但无法完全塞进书包，我们就去掉多余的部分，只取一部分该物体入包。当然，这是做不到的。因此计算出的值是一个达不到的理想值。
当i>n，重量未超过限制时，则是可达到的最大价值。
这样就解释了这个上界函数的优化。可以看出，这是一个最优性剪枝优化，判断当前结点是否有机会产生更优解。
总代码：
//01背包问题优化
#include <iostream>
using namespace std;
int n,bag_v,bag_w;
int bag[100],put[100],w[100],val[100],order[100];
double perp[100];
//按照单位重量价值排序，这里用冒泡
void bubblesort()
{
int i,j;
int temporder = 0;
double temp = 0.0;
for(i=1;i<=n;i++)
perp[i]=val[i]/w[i]; //计算单位价值（单位重量的物品价值）
for(i=1;i<=n-1;i++)
{
for(j=i+1;j<=n;j++)
if(perp[i]<perp[j])//冒泡排序perp[],order[],sortv[],sortw[]
{
temp = perp[i]; //冒泡对perp[]排序交换
perp[i]=perp[i];
perp[j]=temp;
temporder=order[i];//冒泡对order[]交换
order[i]=order[j];
order[j]=temporder;
temp = val[i];//冒泡对val[]交换
val[i]=val[j];
val[j]=temp;
temp=w[i];//冒泡对w[]交换
w[i]=w[j];
w[j]=temp;
}
}
}
//计算上界函数，功能为剪枝
double bound(int i,int cur_v,int cur_w)
{ //判断当前背包的总价值cur_v＋剩余容量可容纳的最大价值<=当前最优价值
double leftw= bag_w-cur_w;//剩余背包容量
double b = cur_v;//记录当前背包的总价值cur_v,最后求上界
//以物品单位重量价值递减次序装入物品
while(i<=n && w[i]<=leftw)
{
leftw-=w[i];
b+=val[i];
i++;
}
//装满背包
if(i<=n)
b+=val[i]/w[i]*leftw;
return b;//返回计算出的上界
}
void search(int cur,int cur_v,int cur_w)
{ //search递归函数，当前current节点的价值为current value，重量为current weight
if(cur>n) //判断边界
{
if(cur_v>bag_v) //是否超过了最大价值
{
bag_v=cur_v; //得到最大价值
for(int i=1;i<=n;i++)
bag[order[i]]=put[i]; //put表示当前是否被选中，将选中的物品存入bag中
}
}
//如若左子节点可行，则直接搜索左子树;
//对于右子树，先计算上界函数，以判断是否将其减去
if(cur_w+w[cur]<=bag_w)//将物品cur放入背包,搜索左子树,即选择当前物品
{
cur_w+=w[cur];//同步更新当前背包的重量
cur_v+=val[cur];//同步更新当前背包的总价值
put[cur]=1;
search(cur+1,cur_v,cur_w);//深度搜索进入下一层
cur_w-=w[cur];//回溯复原
cur_v-=val[cur];//回溯复原
}
if(bound(cur+1,cur_v,cur_w)>bag_v)//如若符合条件则搜索右子树,即不选择当前物品
{
put[cur]=0;
search(cur+1,cur_v,cur_w);
}
}
int main()
{
int i;
bag_v=0; //初始化背包最大价值
//输入数据
cout<<"请输入背包最大容量:"<<endl;;
cin>>bag_w;
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];
for (i=1;i<=n;i++) //新增的order数组，存储初始编号
order[i]=i;
search(1,0,0);
cout<<"最大价值为:"<<endl;
cout<<bag_v<<endl;
cout<<"物品的编号依次为:"<<endl;
for(i=1;i<=n;i++)
if(bag[i]==1)
cout<<i<<" ";
cout<<endl;
return 0;
}
叁
旅行售货员：排序树
讲完子集树，我们再讲讲排序树。排列树与子集树最大的区别在于，子集树的解是无序的子集，而排列树的解则包含整个集合的所有元素，我们从暴力的原则出发，将元素进行全排列。
我们再贴出排序树的图。
｛｝外的数表示已经排好序，｛｝内的数尚未排序。
在排序树中，每一层选择一个数字排到队尾，因此对一个n元素的集合，树的第一层将有n个子结点，表示可选n个数放在队伍的第一个位置，一次分叉比前一次减少一个（因为已经确定了一个位置的元素）；
树共有n+1层（图中省略了最后一层），表示选择n次；
叶结点共有n！个，表示组合数A，全排列共有n！种情形（因此时间复杂度也是n！）。
我们再给出算法框架（这次换英文了~保持新鲜感）：
void backtrack(int t)
{
if(t>n)
output(x)
else
{
for(int i=t;i<=n;i++)
{
swap(x[t],x[i]);
if(constraint(t)&&bound(t))//
backtrack(t+1)
swap(x[i],x[t]);
}
}
}这里的swap是一个交换函数，对于一个排列，只要交换任意两数后就是一个新排列。constraint（）和bound（）分别是约束条件和限定函数（用于剪枝优化）。
为什么要用swap来交换，而不是把数据放入新数组啦等等什么别的操作呢？
这是因为，当我们在原先存储数据的数组x内进行交换时，我们把排好序的元素放到了数组的前面，留下的数据则是未排序的。这样在我们进行for循环的时候就能从t开始，同时避免了重复遇到排过序的数，也不需要book记录等多余的代码。
差不多了解了排序树的概念和回溯法在排序树中的框架，我们就来看题目啦。
旅行售货员问题（TSP）：
某舟同学在去小欣同学那前想了一想，准备顺便拜访各高校的高中同学。他打算从本校出发，途径高中同学所在的一些高校，最终回到自己学校。小舟很懒，希望只走最短的路，同时不想在一个学校玩第二次，因为他们不是主要目标。怎么满足贪得无厌的小舟，制定一个旅行方案？
继续开玩笑。。。别介意~~
回到正题，乍一看这个题目是不是和最短路径问题很像？但很可惜的是，最短路径不要求通过每一个点，还是有所不同。
关键词：最短，每点一次，闭合回路。
（但学过的知识还是有用的：比方说我们可以用上次学过的邻接矩阵来存储图的内容。）
在这个问题中，我们的解空间就是所有城市的全排列，即走过每一个城市的顺序，因此可以用排序树来考虑这个问题。
放码：
//旅行售货员问题——回溯法排序树
#include <iostream>
using namespace std;
int n,t;
int dis[100][100],x[100],bestroad[100];
int cur_dis,bestdis;
const int INF=99999;
void swap(int&a,int&b) //swap函数，交换
{
int temp;
temp=a;
a=b;
b=temp;
}
void backtrack(int t)
{
if (t==n)
{ //判断边界。很长的判断 ，不能到自己或到不了，要比当前最优解短
if (dis[x[n - 1]][x[n]] != 0 && dis[x[n]][1] != 0 &&(cur_dis + dis[x[n - 1]][x[n]] + dis[x[n]][1] < bestdis || bestdis == 0))
{ //记录最优路径，最优距离
for (int j=1;j<=n;j++)
bestroad[j]=x[j];
bestdis=cur_dis+ dis[x[n - 1]][x[n]] + dis[x[n]][1];
return;
}
}
else
{
for (int j=t;j<=n;j++)
{
if(dis[x[t]][x[j]]!=0&& (cur_dis + dis[x[t - 1]][x[t]] + dis[x[t]][1] < bestdis || bestdis == 0))
{
swap(x[t],x[j]);
cur_dis+=dis[x[t]][x[t-1]];
backtrack(t+1);
//回溯
cur_dis-=dis[x[t]][x[t-1]];
swap(x[t],x[j]);
}
}
}
}
int main()
{
int i,j,m,a,b,c;
cout<<"输入城市数:"<<endl;
cin>>n;
cout<<"输入路径数:"<<endl;
cin>>m;
//初始化邻接矩阵
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
dis[i][j]=0;
cout<<"输入路径与距离:"<<endl;
//读入城市之间的距离
for(i=1;i<=m;i++)
{
cin>>a>>b>>c;
dis[a][b]=dis[b][a]=c; //无向图，两边都记录
}
for(i = 1; i <= n; i++)
x[i] = i;
backtrack(2);
cout<<"最佳路径为:";
for (i=1;i<=n;i++)
cout<<bestroad[i]<<" --> ";
cout<<"1"<<endl;
cout<<"最短距离为:"<<bestdis;
return 0;
}
代码中有一些细节：
不同于最短路径，这里我们把INF（即无路径连通）与0（即自身）放在一起处理，因为他们都不需要swap。
我们用t==n，而不是t>=n，是为了防止数组下表越界。
然而，当我们想用剪枝函数优化时，发现其实没什么好方法。。。
再一次说明了通过剪枝函数优化是不容易的。（当然，对TSP问题还有许多方法，针对这个问题老板也写过很多文章哦，可以在公众号内查询，老板赛高）
肆
简单总结
在总结之前，我们再提提老板2年前（好强！）写的N皇后问题。
在那个问题中，老板没有用子集树或排序树。因为本就不止这些方法。
但N皇后问题确实可以用这两种数据结构来写。这里就不再写了，再写我就要死了。有兴趣的盆友可以自行搜索。
那么，终于到了激动人心的总结时间。（也就是完稿时间）
回溯法作为一种极暴力的搜索法，其时间复杂度是极高的，子集树大概是2^n，排序树大概是n！，所以处理大的问题不太给力。
但作为回报，它能给出真正的最优解。
回溯法的子集树和排序树，可以处理两类问题，求子集最优和排序最优。
想要利用剪枝函数优化是非常困难的。（亲身经历）
那么，本次总结就这样水一水啦~~飘走~~
写下最后这个TSP真是感慨万分啊！
在20多天前，我问老板：怎么学算法？我新手，不懂啊。你文章里题目太难了。
老板说：TSP很难吗，小老弟？
当时心态是绝望的(┬＿┬)
如今最起码能用暴力法写写了，不容易，不容易
特此纪念~~~（公号私用，砍了）
这里是新来的工人小舟，
正走在努力学习编程的路上。
让我们下次再见~