分枝限界
关注那些不断已被他人成功应用的新思路。你的原创思想只应该应用在那些你正在研究的问题上。
——托马斯·爱迪生(1847-1931)
这周到来的太快，
没想到这么快就迎来了考试。
干了这碗烤柿粥！
（然而我至今还没开始复习）
没办法，试可以乱考，文不能不更
那么就来看看这次认（随）真（意）完成的内容吧！
目录
1.方法概述
2.FIFO实现
3.priority queue实现
01
方法概述
对老板写过的内容，肯定是要先放链接的：
干货 | 10分钟带你全面掌握branch and bound（分支定界）算法-概念篇
干货 | 10分钟搞懂branch and bound算法的代码实现附带java代码
干货 | 10分钟教你用branch and bound（分支定界）算法求解TSP旅行商问题
老板写的是java，学过的童鞋可以康康，不过可能比较难。
那么，抛玉引砖，接下来就开始正文啦。
在谈到分枝限界法时，我们一般都会提到回溯法。因为这两种方法有很多的类似点。关于回溯法，不了解的同学可以康康往期的内容，一些提到过的定义就不再讲解了：
回溯法和分支限界都是以构造一颗解空间树为基础的。回溯法通过深度优先搜索的思想，选择一条可行的路径，一路走下去；而分支限界法可以根据多种规则生成节点，如广度优先搜索，再结合剪枝函数（我们在回溯法里也可以使用）进行剪枝，得出最优解。
限界函数的使用我们在回溯法里也提到过，是在寻找最优解时使用的一种优化方法，如果我们使用回溯法解决最优解问题也可以使用（其实回溯法寻找最优解的过程本身就可以看作是分枝限界通过深度优先LIFO的栈实现）。而在分枝限界中，这是必不可少的一部分。这也就意味着，回溯法可以找到所有解（这里纠正一下那篇文章的错误），而分枝限界一般解决最优解问题。
限界函数的作用是判断后续结点对应的选择是否有机会得出问题的最优解。如果不可能，直接剪枝掉解空间树的这一条分支，停止遍历。
在大致了解分支限界的流程后，我们发现，主要的难点在于：
（1）解空间树的构造，即节点的生成顺序
（2）剪枝函数的确定，即如何判断是否可能得到最优解
下一个扩展节点的选择（或者说对树的搜索方法）一般有如下方式：
队列式（FIFO）分支界限法（广度优先）：按照队列先进先出原则选取下一个结点为扩展结点。这种搜索可以用FIFO queue实现，即通过队列的数据结构。
优先队列式分支限界法（最小损耗优先）：按照优先队列规定的优先级选取优先级最高的结点成为当前扩展结点。这种搜索可以用优先队列priority queue来实现。
为了判断能否剪枝，我们一般需要两个额外的条件：
1.对于一颗状态空间树的每一个节点所代表的部分解，我们要提供一种方法，计算出通过这个部分解繁衍出的任何解在目标函数上的最佳值边界。（即可能达到的最优解）
2.目前求得的最佳解的值。（记录即可）
如果可以得到这些信息，我们可以拿某个节点的边界值和目前求得的最佳解进行比较。只要符合下面三种中的一种原因，我们就会中止掉它的在当前节点上的查找路径：
1.该节点的边界值不能超越目前最佳解的值。
2.该节点无法代表任何可行解，因为它已经违反了问题的约束。
3.该节点代表的可行解的子集只包含一个单独的点（因此无法给出更多的选择）。在这种情况下，我们拿这个可行解在目标函数上的值和目前求得的最佳解进行比较，如果新的解更好一些的话，就用前者替换后者。
我们结合图片看一看解空间树的建立，顺便具象化一下队列的概念（盗图，请忽略边上的数字）：
1.节点１入队列queue＝｛１｝，创建队列。
2.我们取出队尾节点tail，作为父节点，更新他的后代的值。此题中更新节点２，３，４ 的距离，并将他们加入队列，queue＝｛１，２，３，４｝。完成后节点１出队。queue＝｛２，３，４｝。
3.同样，重复2的步骤，queue＝｛３，４，５，６｝；
4.当我们取到节点３时，出于“限界”（称为”剪枝“）的考虑，我们需要剪去某些边；或者说本身就无法扩展出新的边。
5.重复步骤，直到queue为空（head=tail）。
优先队列法方法和FIFO方法类似，区别在于优先队列每次取队列元素中最优的解先进行拓展，我们在接下来的例子中具体说明。
02
FIFO实现
我们先来介绍一下基于广度优先搜索实现的分枝限界法。例题依旧是我们熟悉的0-1背包问题。
这里我们采用之前回溯法里讲到的限界函数。但是在我们的队列中，每层只判断一个物品是否被选中，所以bag_v不到最后一层都一直为0。所以，我们需要先找出一个bag_v来进行对比。我们可以考虑用贪婪算法找出一个较优解。
说实话，针对这题，个人认为还是回溯法比较快捷，写代码的时候全程无语，感觉在做一件很没意义的事。。。（尤其是debug的过程中）本想选别的例题，但找不到太好的，而01背包又比较熟悉，就当是熟悉FIFO的分枝限界吧。（编的时候还真是改错了好久。。。）
具体讲解参考代码注释，感觉有点傻，还是将就着看吧。。。
Code
//01背包问题 分枝限界法 队列实现 #include <iostream> using namespace std; int n,bag_v,bag_w; int bag[105],w[105],v[105],order[105]; //存储初始编号 double perp[105]; //单位重量价值 class node //队列； { public: node(int w,int v,int isput,node front); node(int num); node(); double cur_w; //当前重量 double cur_v; //当前价值 int put[105]; //put表示当前是否被选中，将选中的物品存入bag中 int cur; //判断到第cur个物品 }; node bagque[105]=node(); node::node(int w,int v,int isput,node front) { cur_w=w+front.cur_w ; cur_v=v+front.cur_v ; cur=front.cur +1; for (int i=1;i<cur;i++) put[i]=front.put[i]; put[cur]=isput; } node::node(int num) { cur_w=0; cur_v=0; cur=0; for (int i=1;i<=num;i++) put[i]=0; } node::node() { cur_w=0; cur_v=0; cur=0; for (int i=1;i<=10;i++) put[i]=0; } //按照单位重量价值排序，这里用冒泡 void bubblesort() { int i,j; int temporder = 0; double temp = 0.0; for(i=1;i<=n;i++) perp[i]=v[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 = v[i];//冒泡对v[]交换 v[i]=v[j]; v[j]=temp; temp=w[i];//冒泡对w[]交换 w[i]=w[j]; w[j]=temp; } } } //基于平均价值优先的贪婪算法，用于剪枝 int greedy () { double greedyvalue=0; double greedyweight=0; for (int i=1;i<=n;i++) { if(greedyweight+w[i]<=bag_w) { greedyvalue+=v[i]; greedyweight+=w[i]; } } return greedyvalue; } //计算上界函数，功能为剪枝 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+=v[i]; i++; } //装满背包 if(i<=n) b+=v[i]/w[i]*leftw; return b;//返回计算出的上界 } void FIFO( ) { bagque[1]=node(n); int head=2,tail=1; while (head>tail) { int current=bagque[tail].cur+1; if(bagque[tail].cur>=n) //判断边界 { if(bagque[tail].cur_v >=bag_v) //是否超过最大价值 { bag_v=bagque[tail].cur_v; //更新最大价值 for(int i=1;i<=n;i++) bag[order[i]]=bagque[tail].put[i]; } tail++; continue; } //如若可以选择当前物品，则直接加入队列; //如果不选择，先计算上界函数，以判断是否将其减去 if(bagque[tail].cur_w+w[current]<=bag_w)//选择加入当前物品cur的情况入列 { bagque[head]=node(w[current],v[current],1,bagque[tail]); head++; } if(bound(current,bagque[tail].cur_v,bagque[tail].cur_w)>bag_v) //不选cur的情况入列 { bagque[head]=node(0,0,0,bagque[tail]); head++; } tail++; } } 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>>v[i]; for (i=1;i<=n;i++) order[i]=i; bubblesort(); bag_v=greedy(); FIFO(); cout<<"最大价值为:"<<endl; cout<<bag_v<<endl; cout<<"物品的编号依次为:"<<endl; for(i=1;i<=n;i++) if(bag[i]==1) cout<<i<<" "; cout<<endl; return 0; }
