分支界限法.
武汉理工大学
算法设计与分析论文
题 目：
分支限界法应用研究
目 录
摘 要 . ...................................................... 1 1. 绪 论 . .................................................... 2 2分支限界法的内容 ........................................... 3 2.1 分支限界法基本思想 .................................... 3 2.2 两种分支限界法 ........................................ 3 2.3 分支限界法的设计思路 .................................. 4 2.4分支限界法与回溯法区别 ............... 错误！未定义书签。 3 分支限界法应用 . ............................................ 5 3.1批处理作业问题 ........................................ 5 3.2 旅行售货员问题 ........................................ 6 3.3单源最短路径问题 ..................................... 12 3.4 01背包问题 .......................................... 12 4. 总结 . ..................................................... 24 5. 参考文献 . ................................................. 25
摘 要
分支限界法常以广度优先或以最小耗费优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
本文讲述了分支限界法的含义、基本思路及实现过程，分支限界法的核心、基本性质、特点及其存在的问题。并通过分支限界法的特点，举例列出了以往研究过的几个经典问题，对于实际应用中的问题，也希望通过分支限界法的特点来解决。
关键词：分支限界法；解空间树；最优解；
1. 绪 论
为了解决各种实际问题，计算机算法学得到了飞速的发展，线性规划、动态规划、分支限界法等一系列运筹学模型纷纷运用到计算机算法学中，产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法更像是一门艺术而不像是技术 ,但仍然存在一些行之有效的、能够用于解决许多问题的算法设计方法 ,你可以使用这些方法来设计算法 ,并观察这些算法是如何工作的。一般情况下, 为了获得较好的性能, 必须对算法进行细致的调整。但是在某些情况下, 算法经过调整之后性能仍无法达到要求, 这时就必须寻求另外的方法来求解该问题。分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
2分支限界法的内容
2.1 分支限界法基本思想
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
2.2 两种分支限界法
（1）队列式(FIFO)分支限界法
按照队列先进先出（FIFO ）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法
按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点
2.3分支限界法的设计思路
设求解最大化问题，解向量为X=(x1,…,xn) ，xi 的取值范围为Si ，|Si|=ri。在使用分支限界搜索问题的解空间树时，先根据限界函数估算目标函数的界[down, up]，然后从根结点出发，扩展根结点的r1个孩子结点，从而构成分量x1的r1种可能的取值方式。对这r1个孩子结点分别估算可能的目标函数bound(x1)，其含义：以该结点为根的子树所有可能的取值不大于bound(x1)，即： bound(x1)≥bound(x1,x2)≥…≥ bound(x1,…,xn)
若某孩子结点的目标函数值超出目标函数的下界，则将该孩子结点丢弃；否则，将该孩子结点保存在待处理结点表PT 中。再取PT 表中目标函数极大值结点作为扩展的根结点，重复上述。直到一个叶子结点时的可行解X=(x1,…,xn) ，及目标函数值bound(x1,…,xn) 。
2.4分支限界法与回溯法区别
（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。
3分支限界法应用
3.1批处理作业问题
（1）问题提出。
给定n 个作业的集合J={J1,J2,…,Jn}。每一个作业Ji 都有2项任务要分别在2台机器上完成。每一个作业必须先由机器1处理，然后再由机器2处理。作业Ji 需要机器j 的处理时间为tji ，i=1,2,…,n ；j=1,2。对于一个确定的作业调度，设是Fji 是作业i 在机器j 上完成处理的时间。则所有作业在机器2上完成处理的时间和
f = 批处理作业调度问题要求对于给定的∑F 2i 称为该作业调度的完成时间和。
i =1n
n 个作业，制定最佳作业调度方案，使其完成时间和达到最小。 （2）算法分析。
在结点E 处相应子树中叶结点完成时间和的下界是：
f ≥∑F 2i +max{S 1, S 2}
i ∈M
注意到如果选择Pk ，使t1pk 在k>=r+1时依非减序排列，S1则取得极小值。同理如果选择Pk 使t2pk 依非减序排列，则S2取得极小值。
f ≥
i ∈M
∑F
2i
ˆ, S ˆ}+max{S 12
这可以作为优先队列式分支限界法中的限界函数。 （3）主要算法介绍。 do {
if (enode.s == n ) { if (enode.sf2
for (int i = 0; i
for (int i = enode.s; i
MyMath.swap(enode.x, enode.s,i); int [] f= new int [3]; int bb=bound(enode,f); if (bb
HeapNode node=new HeapNode(enode,f,bb,n); heap.put(node); } MyMath.swap(enode.x, enode.s,i); }
算法的while 循环完成对排列树内部结点的有序扩展。在while 循环体内算法依次从活结点优先队列中取出具有最小bb 值（完成时间和下界）的结点作为当前扩展结点，并加以扩展。首先考虑enode.s=n的情形，当前扩展结点enode 是排列树中的叶结点。enode.sf2是相应于该叶结点的完成时间和。当enode.sf2
3.2 旅行售货员问题
（1）问题提出。
某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费) 。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费) 最小。
（2）算法分析。
旅行商问题的解空间是一个排列树。
有两种实现的方法：第一种是只使用一个优先队列，队列中的每个元素 中都包含到达根的路径。另一种是保留一个部分解空间树和一个优先队列，优先队列中 的元素并不包含到达根的路径。
以下为第一种方法， 由于我们要寻找的是最小耗费的旅行路径，因此可以使用最小耗费分枝定界法。在实现过程中，使用一个最小优先队列来记录活节点，队列中每个节点的类型为MinHeapNode 。每个节点包括如下区域： x（从1到n 的整数排列，
其中x[0] = 1 ），s （一个整数，使得从排列树的根节点到当前节点的路径定义了旅行路径的前缀x[0:s], 而剩余待访问的节点是x [s + 1 : n - 1 ]），cc （旅行路径前缀，即解空间树中从根节点到当前节点的耗费），lcost （该节点子树中任意叶节点中的最小耗费）， rcost（从顶点x[s : n - 1]出发的所有边的最小耗费之和）。当类型为MinHeapNode( T )的数据被转换成为类型T 时，其结果即为lcost 的值。 程序代码：
#include #include using namespace std;
//---------------------宏定义------------------------------------------ #define MAX_CITY_NUMBER 10 //城市最大数目
#define MAX_COST 10000000 //两个城市之间费用的最大值
//---------------------全局变量---------------------------------------- int City_Graph[MAX_CITY_NUMBER][MAX_CITY_NUMBER]; //表示城市间边权重的数组 int City_Size; //表示实际输入的城市数目 int Best_Cost; //最小费用 int Best_Cost_Path[MAX_CITY_NUMBER];
//最小费用时的路径
//------------------------定义结点--------------------------------------- typedef struct Node{
int lcost; //优先级 int cc; //当前费用
int rcost; //剩余所有结点的最小出边费用的和 int s; //当前结点的深度，也就是它在解数组中的索引位置 int x[MAX_CITY_NUMBER]; //当前结点对应的路径 struct Node* pNext; //指向下一个结点 }Node;
//---------------------定义堆和相关对操作-------------------------------- typedef struct MiniHeap{
Node* pHead; //堆的头 }MiniHeap; //初始化
void InitMiniHeap(MiniHeap* pMiniHeap){ pMiniHeap->pHead = new Node; pMiniHeap->pHead->pNext = NULL; }
//入堆
void put(MiniHeap* pMiniHeap,Node node){ Node* next;
Node* pre;
Node* pinnode = new Node; //将传进来的结点信息copy 一份保存 //这样在函数外部对node 的修改就不会影响到堆了
pinnode->cc = node.cc;
pinnode->lcost = node.lcost; pinnode->pNext = node.pNext; pinnode->rcost = node.rcost; pinnode->s = node.s; pinnode->pNext = NULL;
for(int k=0;kx[k] = node.x[k]; }
pre = pMiniHeap->pHead;
next = pMiniHeap->pHead->pNext; if(next == NULL){
pMiniHeap->pHead->pNext = pinnode; } else{
while(next != NULL){
if((next->lcost) > (pinnode->lcost)){ //发现一个优先级大的，则置于其前面
pinnode->pNext = pre->pNext; pre->pNext = pinnode;
break; //跳出 }
pre = next;
next = next->pNext; }
pre->pNext = pinnode; //放在末尾 } }
//出堆
Node* RemoveMiniHeap(MiniHeap* pMiniHeap){ Node* pnode = NULL;
if(pMiniHeap->pHead->pNext != NULL){ pnode = pMiniHeap->pHead->pNext;
pMiniHeap->pHead->pNext = pMiniHeap->pHead->pNext->pNext; }
return pnode; }
//---------------------分支限界法找最优解-------------------------------- void Traveler(){ int i,j;
int temp_x[MAX_CITY_NUMBER];
Node* pNode = NULL;
int miniSum; //所有结点最小出边的费用和
int miniOut[MAX_CITY_NUMBER];
//保存每个结点的最小出边的索引
MiniHeap* heap = new MiniHeap; //分配堆
InitMiniHeap(heap); //初始化堆
miniSum = 0;
for (i=0;i
miniOut[i] = MAX_COST; //初始化时每一个结点都不可达
for(j=0;j
if (City_Graph[i][j]>0 && City_Graph[i][j]
//从i 到j 可达，且更小
miniOut[i] = City_Graph[i][j];
}
}
if (miniOut[i] == MAX_COST){// i 城市没有出边
Best_Cost = -1;
return ;
}
miniSum += miniOut[i];
}
for(i=0;i
走一遍
Best_Cost_Path[i] = i;
}
Best_Cost = MAX_COST; //初始化的最优费用是一个很大的数
pNode = new Node; //初始化第一个结点并入堆
pNode->lcost = 0; //当前结点的优先权为0 也就是最优
pNode->cc = 0; //当前费用为0（还没有开始旅行）
pNode->rcost = miniSum; //剩余所有结点的最小出边费用和就是初始
化的miniSum
pNode->s = 0; //层次为0
pNode->pNext = NULL;
for(int k=0;k
pNode->x[k] = Best_Cost_Path[k]; //第一个结点所保存的路径也就
是初始化的路径
}
put(heap,*pNode); //入堆
while(pNode != NULL && (pNode->s)
//堆不空 不是叶子
for(int k=0;k
Best_Cost_Path[k] = pNode->x[k] ; //将最优路径置换为当前结点本身所保存的
}
/*
* * pNode 结点保存的路径中的含有这条路径上所有结点的索引
* * x路径中保存的这一层结点的编号就是x[City_Size-2]
* * 下一层结点的编号就是x[City_Size-1] */
if ((pNode->s) == City_Size-2){ //是叶子的父亲
Int edge1 = City_Graph[(pNode->x)[City_Size-2]][(pNode->x)[City_Size-1]];
int edge2 = City_Graph[(pNode->x)[City_Size-1]][(pNode->x)[0]];
if(edge1 >= 0 && edge2 >= 0 && (pNode->cc+edge1+edge2) cc + edge1+edge2;
pNode->cc = Best_Cost;
pNode->lcost = Best_Cost; //优先权为 Best_Cost
pNode->s++; //到达叶子层
}
}
else{ //内部结点
for (i=pNode->s;i
if(City_Graph[pNode->x[pNode->s]][pNode->x[i]] >= 0){
//pNode的层数就是它在最优路径中的位置
Int temp_cc =
pNode->cc+City_Graph[pNode->x[pNode->s]][pNode->x[i]];
int temp_rcost = pNode->rcost-miniOut[pNode->x[pNode->s]];
//下一个结点的剩余最小出边费用和
//等于当前结点的rcost 减去当前这个结点的最小出边费用
if (temp_cc+temp_rcost
//下一个结点的最小出边费用和小于当前的最优解，说明可能存在更优解
for(j=0;j
temp_x[j]=Best_Cost_Path[j];
}
temp_x[pNode->x[pNode->s+1]] = Best_Cost_Path[i];
//将当前结点的编号放入路径的深度为s+1的地方
temp_x[i] = Best_Cost_Path[pNode->s+1];
Node* pNextNode = new Node;
pNextNode->cc = temp_cc;
pNextNode->lcost = temp_cc+temp_rcost;
pNextNode->rcost = temp_rcost;
pNextNode->s = pNode->s+1;
pNextNode->pNext = NULL;
for(int k=0;k
pNextNode->x[k] = temp_x[k];
}
put(heap,*pNextNode);
delete pNextNode;
}
}
}
}
pNode = RemoveMiniHeap(heap);
}
}
int main(){
int i,j;
printf("请输入旅行的节点数");
scanf("%d",&City_Size);
for(i=0;i
printf("请分别输入每个节点与其它节点的路程花费");
for(j=0;j
scanf("%d",&City_Graph[i][j]);
}
}
Traveler();
printf("最小花费""%d\n",Best_Cost);
return 1;
}
实验结果如图：
由于我们要寻找的是最小耗费的旅行路径，因此可以使用最小耗费分枝限界法。在实现过程中，使用一个最小优先队列来记录活节点，队列中每个节点的类型为MinHeapNode 。每个节点包括如下区域： x（从1到n 的整数排列，其中x[0] = 1 ），s （一个整数，使得从排列树的根节点到当前节点的路径定义了旅行路径的前缀x[0:s], 而剩余待访问的节点是x [s + 1 : n - 1 ]），cc （旅行路径前缀，即解空间树中从根节点到当前节点的耗费），lcost （该节点子树中任意叶节点中的最小耗费）， rcost（从顶点x[s : n - 1]出发的所有边的最小耗费之和）。当类型为MinHeapNode( T )的数据被转换成为类型T 时，其结果即为lcost 的值。
3.3单源最短路径问题
（1）问题提出。
下面以一个例子来说明单源最短路径问题：在下图所给的有向图G 中，每一边都有一个非负边权。要求图3-1从源顶点s 到目标顶点t 之间的最短路径。
图3-1 有向图G
（2）算法分析。
下图3-2是用优先队列式分支限界法解有向图G 的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。
图3-2 解空间树
程序代码：
#include
#include
#include
#include
using namespace std;
struct node_info
{
public:
node_info (int i,int w)
: index (i), weight (w) {}
node_info ()
: index(0),weight(0) {}
node_info (const node_info & ni)
: index (ni.index), weight (ni.weight) {}
friend
bool operator rth.weight ; // 为了实现从小到大的顺序 }
public:
int index; // 结点位置
int weight; // 权值
};
struct path_info
{
public:
path_info ()
: front_index(0), weight (numeric_limits::max()) {} public:
int front_index;
int weight;
};
class ss_shortest_paths