【算法学习】分枝限界法
分枝限界
关注那些不断已被他人成功应用的新思路。你的原创思想只应该应用在那些你正在研究的问题上。
——托马斯·爱迪生(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;
}
03
priority queue实现
接下来是优先队列式分枝限界法，我们以单源最短路径问题为例。
最短路径依旧是一个熟悉的问题，可以通过过去的推文了解，就不多解释了：
先简单介绍一下优先队列：
优先队列可以分为最大、最小优先队列。相比于先进先出的普通队列，优先队列每次都是最大（或最小）的元素优先出队。
在单源最短路径问题中，我们采用的剪枝函数则类似于之前提到的Dijkstra算法（其实它本身也就是源于BFS），通过寻找当前离原点最近的点进行下一步操作；通过松弛操作得出下一层子节点。说是最优优先出队，其实这里也只有最小点一个出队拓展新子点了。之前推文里有提到具体算法，可以参考一下，就不难理解了。
这里暂时不深入讲解如何实现优先队列，而是直接通过头文件调用。由于我也不是很习惯用优先队列，这里参考了网上的代码。具体讲解参见注释：
Code：
//优先队列式分支限界法 解单源最短路径问题
//来源互联网 ，作者csdn zzzsdust 原文链接见后文
#include <bits/stdc++.h> //头文件中附带有优先队列
using namespace std;
class MinHeapNode //最小堆
{
public:
int id;
int length; //从起始点 v 到点 id 的距离
public:
friend bool operator < (const MinHeapNode &a, const MinHeapNode &b) //运算符重载
{
return a.length < b.length;
}
friend bool operator > (const MinHeapNode &a, const MinHeapNode &b)
{
return a.length > b.length;
}
};
const int max_ = 0x3f3f3f;
int Graph[100][100]; //输入两点间距离
int dist[100]; //到原点距离
int pre[100]; //记录最短路径中的前一个点
int n, m, v;
void OutPutPath(int i) //输出到原点的最短路径
{
if(i == pre[i])
{
printf("%d", i);
return;
}
else
{
OutPutPath(pre[i]);
printf(" %d", i);
}
}
void OutPut()
{
for(int i = 1; i <= n; ++i)
{
if(i != v)
{
printf("点 %d 到 %d 的最短距离是 %d\n", v, i, dist[i]);
printf("路径为：");
OutPutPath(i);
printf("\n");
}
}
}
//划重点！！
void ShortestPaths()
{
priority_queue<MinHeapNode, vector<MinHeapNode>, greater<MinHeapNode> > q;
/*调用优先队列 ，
第一个参数是数值类型;
第二个参数是存放数值的容器类型，一般用vector;
第三个参数为排序规则。
greater升序，即小的先出；less降序，即大的先出。
具体函数：
1.插入 .push()函数
2.取出顶端元素 .top()函数
3.删除顶端元素 .pop()函数
4.大小 .size()函数
5.是否为空 .empty()函数
*/
memset(dist, max_, sizeof(dist)); //初始化距离
dist[v] = 0;
pre[v] = v;
MinHeapNode cur_p;
cur_p.id = v;
cur_p.length = 0;
q.push(cur_p);
while(true)
{
if(q.empty() == 1) //全员松弛完毕
break;
cur_p = q.top(); //取出堆顶的点（距离最短）
q.pop(); // 在优先队列中删除刚取出的点
for(int i = 1; i <= n; ++i)
{
if(Graph[cur_p.id][i] != max_ && (cur_p.length + Graph[cur_p.id][i] < dist[i])) //剪枝函数，也就是Dijkstra中的松弛
{
dist[i] = cur_p.length + Graph[cur_p.id][i];
pre[i] = cur_p.id;
MinHeapNode temp;
temp.id = i;
temp.length = dist[i];
q.push(temp);
}
}
}
}
void InPut() //输入数据
{
int x, y, len;
scanf("%d %d %d", &v, &n, &m); //以v为原点，n个点，m条边。
memset(Graph, max_, sizeof(Graph)); //默认设置为最大，表示无法到达
for(int i = 1; i <= m; ++i)
{
scanf("%d %d %d", &x, &y, &len);
Graph[x][y] = Graph[y][x] = len; //无向图！！
}
}
int main()
{
InPut();
ShortestPaths();
OutPut();
}
Reference：
https://blog.csdn.net/qjt19950610/article/details/89476784
https://blog.csdn.net/m0_38015368/article/details/80449014
《Introduction to The Design and Analysis of Algorithms》
by Anany Levitin 潘彦 译
后记：
分枝限界法最有名的作用还是求解整数规划问题。
这部分问题我们暂且搁一会儿，等未来再讲。
（关键看我什么时候编出正确的代码）
其实到这里，一个部分的内容也结束了。
这一部分主要是讲算法设计思想。
然而rookie的我连数据结构的不过关。。。
因此打算接下来一段时间恶补一波。
可能会写相关的内容。敬请期待~~