支限界分.docx
《支限界分.docx》由会员分享，可在线阅读，更多相关《支限界分.docx（21页珍藏版）》请在冰点文库上搜索。
支限界分
分支限界法的应用
课程名称：
算法设计与分析
院系：
计算机科学与信息工程学院
学生姓名：
*********
学号：
****************
专业班级：
*****************************
指导教师：
******
2013年12月27日
旅行售货员问题--分支限界法
摘要：
分支限界法是一种选优搜索法,按选优条件向前搜索,以达到目标。
但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择。
采用算法设计的基本方法--分枝限界法解决城市推销员问题是一种行之有效而且节省内存空间的方法。
旅行售货员问题是图论中一个著名的问题，这个问题有着明显的实际意义。
旅行售货员问题是指旅行售货员要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。
本文主要介绍用分支界限法求解旅行售货员问题，并给出相应求解程序。
关键词：
分支限界旅行售货员最短路径
第一章、绪论3
第二章、分支界限算法的理论知识4
2.1基本思想4
2.2分枝节点的选择4
2.32分枝界限法的步骤5
2.43分枝界限法的算法分析5
第三章、旅行售货员问题6
3.1问题描述6
3.2相关概念与数据结构的介绍6
3．3算法设计8
3.4流程图：
8
3.5测试结果9
第四章、结论10
参考文献11
附件：
11
第一章、绪论
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。
活结点一旦成为扩展结点，就一次性产生其所有儿子结点。
在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。
这个过程一直持续到找到所需的解或活结点表为空时为止。
与贪婪算法一样，这种方法也是用来为组合优化问题设计求解算法的，所不同的是它在问题的整个可能解空间搜索，所设计出来的算法虽其时间复杂度比贪婪算法高，但它的优点是与穷举法类似，都能保证求出问题的最佳解，而且这种方法不是盲目的穷举搜索，而是在搜索过程中通过限界，可以中途停止对某些不可能得到最优解的子空间进一步搜索（类似于人工智能中的剪枝），故它比穷举法效率更高。
第二章、分支界限算法的理论知识
2.1基本思想
分支限界法是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。
分支定界法的基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。
该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为定界）。
在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。
这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。
这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限。
因此这种算法一般可以求得最优解。
将问题分枝为子问题并对这些子问题定界的步骤称为分枝定界法。
2.2分枝节点的选择
对搜索树上的某些点必须作出分枝决策，即凡是界限小于迄今为止所有可行解最小下界的任何子集（节点），都有可能作为分枝的选择对象（对求最小值问题而言）。
怎样选择搜索树上的节点作为下次分枝的节点呢？
有两个原则：
1）从最小下界分枝（优先队列式分枝限界法）：
每次算完界限后，把搜索树上当前所有叶节点的界限进行比较。
找出限界最小的节点，此结点即为下次分枝的结点。
·优点：
检查子问题较少，能较快地求得最佳解；
·缺点：
要存储很多叶节点的界限及对应的耗费矩阵，花费很多内存空间。
2）从最新产生的最小下界分枝（队列式（FIFO）分枝限界法）：
从最新产生的各子集中按顺序选择各结点进行分枝，对于下届比上届还大的节点不进行分枝。
优点：
节省了空间；缺点：
需要较多的分枝运算，耗费的时间较多。
这两个原则更进一步说明了，在算法设计中的时空转换概念。
分枝定界法已经成功地应用于求解整数规划问题、生产进度表问题、货郎担问题、选址问题、背包问题以及可行解的数目为有限的许多其它问题。
对于不同的问题，分枝与界限的步骤和内容可能不同，但基本原理是一样的。
2.32分枝界限法的步骤
分枝界限法是组合优化问题的有效求解方法，其步骤如下所述：
步骤一：
如果问题的目标为最小化，则设定目前最优解的值Z=∞
步骤二：
根据分枝法则（Branchingrule），从尚未被洞悉（Fathomed）节点（局部解）中选择一个节点，并在此节点的下一阶层中分为几个新的节点。
步骤三：
计算每一个新分枝出来的节点的下限值（Lowerbound，LB）
步骤四：
对每一节点进行洞悉条件测试，若节点满足以下任意一个条件，则此节点可洞悉而不再被考虑：
此节点的下限值大于等于Z值。
已找到在此节点中，具最小下限值的可行解；若此条件成立，则需比较此可行解与Z值，若前者较小，则需更新Z值，燕以此为可行解的值。
此节点不可能包含可行解。
步骤五：
判断是否仍有尚未被洞悉的节点，如果有，则进行步骤二，如果已无尚未被洞悉的节点，则演算停止，并得到最优解。
Kolen等曾利用此方法求解含时间窗约束的车辆巡回问题，其实验的节点数范围为6-15。
当节点数为6时，计算机演算所花费的时间大约1分钟（计算机型为VAZ11/785），当节点数扩大至12时，计算机有内存不足的现象产生，所以分枝定界法比较适用于求解小型问题。
Held和Karp指出分枝定界法的求解效率，与其界限设定的宽紧有极大的关系。
2.43分枝界限法的算法分析
1、算法优点：
可以求得最优解、平均速度快。
因为从最小下界分支，每次算完限界后，把搜索树上当前所有的叶子结点的限界进行比较，找出限界最小的结点，此结点即为下次分支的结点。
这种决策的优点是检查子问题较少，能较快的求得最佳解。
2、缺点：
要存储很多叶子结点的限界和对应的耗费矩阵。
花费很多内存空间。
存在的问题：
分支定界法可应用于大量组合优化问题。
其关键技术在于各结点权值如何估计，可以说一个分支定界求解方法的效率基本上由值界方法决定，若界估计不好，在极端情况下将与穷举搜索没多大区别
第三章、旅行售货员问题
3.1问题描述
某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。
他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程（或总旅费）最小。
3.2相关概念与数据结构的介绍
1.分支限界法利用的是广度优先搜索和最优值策略。
2.利用二维数组保存图信息City_Graph[MAX_SIZE][MAX_SIZE]其中City_Graph[i][j]的值代表的是城市i与城市j之间的路径费用一旦一个城市没有通向另外城市的路，则不可能有回路，不用再找下去了
3.我们任意选择一个城市，作为出发点。
（因为最后都是一个回路，无所谓从哪出发）下面是关键思路：
想象一下，我们就是旅行员，假定从城市1出发，根据广度优先搜索的思路，我们要把从城市1能到达的下一个城市，都要作为一种路径走一下试试。
可是程序里面怎么实现这种“试试”呢？
利用一种数据结构，保存我们每走一步后，当前的一些状态参数，如，我们已经走过的城市数目（这样就知道，我们有没有走完，比如上图，当我们走了四个城市之后，无论从第四个城市是否能回到起点城市，都就意味着我们走完了，只是这条路径合不合约束以及能不能得到最优解的问题）。
这里把，这种数据结构成为结点。
这就需要另一个数据结构，保存我们每次试出来的路径，这就是堆。
数据结构定义如下：
Node{
ints;//结点深度，即当前走过了几个城市
intx[MAX_SIZE];//保存走到这个结点时的路径信息
}
MiniHeap{
//保存所有结点并提供一些结点的操作
}
a.我们刚开始的时候不知道最总能得到的路径是什么，所以我们，就认为按照城市编号的次序走一遍。
于是有了第一个结点0，放入堆中。
相当于来到了城市1（可以是所有城市中的任意一个，这里姑且设为图中城市1）。
b.从城市1，出发，发现有三条路可走，分别走一下，这样就产生了三个结点，都放入堆中。
结点1数据为：
x[1234]，深度为s=1（深度为0表示在城市1还没有开始走），这说明，结点1是从城市1走来，走过了1个城市，当前停在城市2，后面的城市3和城市4都还没有走，但是具体是不是就按照3.4的顺序走，这个不一定。
结点2数据为：
x[1324]，深度为s=1，表示，从城市1走来，走过了1个城市，当前停在了城市3，后面2.4城市还没走结点3数据为：
x[1432]，深度为s=1，表示，从城市1走来，走过了1个城市，当前停在了城市4，后面3.2城市还没有走
c.从堆中取一个结点，看看这个结点是不是走完了的，也就是要看看它的深度是不是3，是的话，说明走完了，看看是不是能回到起点，如果可以而且费用少于先前得到最优的费用，就把当前的解作为最优解。
如果没有走完，就继续把这条路走下去。
以上就是简单的想法，而实际的程序中，堆还需要提供对结点的优先权排序的支持。
而当前结点在往下一个城市走时，也是需要约束和限界函数，这些书上讲的很清楚，不懂，就翻翻书。
有点要提出来说说的就是结点优先权和限界函数时都用到了一个最小出边和，就相当于把所有城市最便宜的一条路（边）费用加起来的值。
3．3算法设计
算法开始时创建一个最小堆，用于表示活结点优先队列。
堆中每个结点的子树费用的下界lcost值是优先队列的优先级。
接着算法计算出图中每个顶点的最小费用出边并用MinOut记录。
如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。
如果每个顶点都有出边，则根据计算出的MinOut作算法初始化。
算法的while循环体完成对排列树内部结点的扩展。
对于当前扩展结点，算法分2种情况进行处理：
（1）首先考虑s=n-2的情形，此时当前扩展结点是排列树中某个叶结点的父结点。
如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点。
（2）当s由于当前扩展结点所相应的路径是x[0:
s]，其可行儿子结点是从剩余顶点x[s+1:
n-1]中选取的顶点x[i]，且（x[s]，x[i]）是所给有向图G中的一条边。
对于当前扩展结点的每一个可行儿子结点，计算出其前缀（x[0:
s]，x[i]）的费用cc和相应的下界lcost。
当lcost算法中while循环的终止条件是排列树的一个叶结点成为当前扩展结点。
当s=n-1时，已找到的回路前缀是x[0:
n-1]，它已包含图G的所有n个顶点。
因此，当s=n-1时，相应的扩展结点表示一个叶结点。
此时该叶结点所相应的回路的费用等于cc和lcost的值。
剩余的活结点的lcost值不小于已找到的回路的费用。
它们都不可能导致费用更小的回路。
因此已找到的叶结点所相应的回路是一个最小费用旅行售货员回路，算法可以结束。
算法结束时返回找到的最小费用，相应的最优解由数组v给出。
3.4流程图：
Y
Y
N
3.5测试结果
1当节点数n=4其各个节点之间的边的全矩阵为
时，其最优解和路径为：
图6-1
6.2当节点数n=5其各个节点之间的边的全矩阵为
时，其最优解和其路径为：
图6-2
第四章、结论
旅行售货员问题的解决，这里用了分支界限法，由于是NP问题，其时间复杂度很高，当相对于回溯法而言，分支限界法剪掉了一些不必要的计算，效率有很大的提高，但是在最坏的情况下可能需要满历所有的结点。
此时的时间复杂度也是很高课程设计是对于知识的综合运用，通过学习算法分析也设计了解了一些关于实际问题的解决办法。
还有一点就是在学习过程中只停留在书本，只是知道书中某一算法的几个应用的例子。
知识面很窄，考虑问题也只会从书本出发。
想在例题中是如何解决问题的。
其实我们在平常的学习中应该多研究一些实际问题，扩展视野。
这样就可以用不同的办法解决同一问题，使用同一方法解决不同问题，也可以使复杂问题简单化。
参考文献
[1]算法设计与分析吕国英主编
[2]《计算机算法分析与设计》第二版，王晓东编著，电子工业出版社
[3]现代计算机常用数据结构和算法，潘金贵编著，南京大学出版社,1992
附件：
程序代码：
#include
#include
#defineNoEdge1000
structMinHeapNode{
intlcost;//子树费用的下界
intcc;//当前费用
intrcost;//x[s:
n-1]中顶点最小出边费用和
ints;//根节点到当前节点的路径为x[0:
s]
int*x;//需要进一步搜索的顶点是//x[s+1:
n-1]
structMinHeapNode*next;
};
intn;//图G的顶点数
int**a;//图G的邻接矩阵
//intNoEdge;//图G的无边标记
intcc;//当前费用
intbestc;//当前最小费用
MinHeapNode*head=0;/*堆头*/
MinHeapNode*lq=0;/*堆第一个元素*/
MinHeapNode*fq=0;/*堆最后一个元素*/
intDeleteMin（MinHeapNode*&E）
{
MinHeapNode*tmp=NULL;
tmp=fq;
//w=fq->weight;
E=fq;
if（E==NULL）
return0;
head->next=fq->next;/*一定不能丢了链表头*/
fq=fq->next;
//free（tmp）;
return0;
}
intInsert（MinHeapNode*hn）
{
if（head->next==NULL）
{
head->next=hn;//将元素放入链表中
fq=lq=head->next;//一定要使元素放到链中
}
else
{
MinHeapNode*tmp=NULL;
tmp=fq;
if（tmp->cc>hn->cc）
{
hn->next=tmp;
head->next=hn;
fq=head->next;/*链表只有一个元素的情况*/
}
else
{
for（;tmp!
=NULL;）
{
if（tmp->next!
=NULL&&tmp->cc>hn->cc）
{
hn->next=tmp->next;
tmp->next=hn;
break;
}
tmp=tmp->next;
}
}
if（tmp==NULL）
{
lq->next=hn;
lq=lq->next;
}
}
return0;
}
intBBTSP（intv[]）
{//解旅行售货员问题的优先队列式分支限界法
inti,j;
/*初始化最优队列的头结点*/
head=（MinHeapNode*）malloc（sizeof（MinHeapNode））;
head->cc=0;head->x=0;
head->lcost=0;head->next=NULL;head->rcost=0;head->s=0;
int*MinOut=newint[n+1];/*定义定点i的最小出边费用*/
//计算MinOut[i]=顶点i的最小出边费用
intMinSum=0;//最小出边费用总合
for（i=1;i<=n;i++）{
intMin=NoEdge;/*定义当前最小值*/
for（j=1;j<=n;j++）
if（a[i][j]!
=NoEdge&&/*当定点i,j之间存在回路时*/
（a[i][j]Min=a[i][j];/*更新当前最小值*/
if（Min==NoEdge）
returnNoEdge;//无回路
MinOut[i]=Min;/*顶点i的最小出边费用*/
MinSum+=Min;/*最小出边费用的总和*/
}
MinHeapNode*E=0;
E=（MinHeapNode*）malloc（sizeof（MinHeapNode））;
E->x=newint[n];
//E.x=newint[n];
for（i=0;iE->x[i]=i+1;
E->s=0;
E->cc=0;
E->rcost=MinSum;
E->next=0;//初始化当前扩展节点
intbestc=NoEdge;/*记录当前最小值*/
//搜索排列空间树
while（E->sif（E->s==n-2）{//当前扩展结点是叶结点的父结点
if（a[E->x[n-2]][E->x[n-1]]!
=NoEdge&&
a[E->x[n-1]][1]!
=NoEdge&&
（E->cc+a[E->x[n-2]][E->x[n-1]]+a[E->x[n-1]][1]||bestc==NoEdge））{
bestc=E->cc+a[E->x[n-2]][E->x[n-1]]+a[E->x[n-1]][1];/*更新当前最新费用*/
E->cc=bestc;
E->lcost=bestc;
E->s++;
E->next=NULL;
Insert（E）;/*将该页节点插入到优先队列中*/
}
else
free（E->x）;//该页节点不满足条件舍弃扩展结点
}
else{
for（i=E->s+1;iif（a[E->x[E->s]][E->x[i]]!
=NoEdge）
{/*当前扩展节点到其他节点有边存在*/
//可行儿子结点
intcc=E->cc+a[E->x[E->s]][E->x[i]];/*加上节点i后当前节点路径*/
intrcost=E->rcost-MinOut[E->x[E->s]];/*剩余节点的和*/
intb=cc+rcost;//下界
if（b{//子树可能含最优解,结点插入最小堆
MinHeapNode*N;
N=（MinHeapNode*）malloc（sizeof（MinHeapNode））;
N->x=newint[n];
for（intj=0;jN->x[j]=E->x[j];
N->x[E->s+1]=E->x[i];
N->x[i]=E->x[E->s+1];/*添加当前路径*/
N->cc=cc;/*更新当前路径距离*/
N->s=E->s+1;/*更新当前节点*/
N->lcost=b;/*更新当前下界*/
N->rcost=rcost;
N->next=NULL;
Insert（N）;/*将这个可行儿子结点插入到活结点优先队列中*/
}
}
free（E->x）;
}//完成结点扩展
DeleteMin（E）;//取下一扩展结点
if（E==NULL）break;//堆已空
}
if（bestc==NoEdge）
returnNoEdge;//无回路
for（i=0;iv[i+1]=E->x[i];//将最优解复制到v[1:
n]
while（true）{//释放最小堆中所有结点
free（E->x）;
DeleteMin（E）;
if（E==NULL）
break;
}
returnbestc;
}
intmain（）
{
n=0;
inti=0;
FILE*in,*out;
in=fopen（"input.txt","r"）;
out=fopen（"output.txt","w"）;
if（in==NULL||out==NULL）{
printf（"没有输入输出文件\n"）;
return1;
}
fscanf（in,"%d",&n）;
a=（int**）malloc（sizeof（int*）*（n+1））;
for（i=1;i<=n;i++）
{
a[i]=（int*）malloc（sizeof（int）*（n+1））;
}
for（i=1;i<=n;i++）
for（intj=1;j<=n;j++）
fscanf（in,"%d",&a[i][j]）;
int*v=（int*）malloc（sizeof（int）*（n+1））;
for（i=1;i<=n;i++）
v[i]=0;
bestc=BBTSP（v）;
printf（"最佳路径:
\n"）;
for（i=1;i<=n;i++）
fprintf（stdout,"%d\t",v[i]）;
fprintf（stdout,"\n"）;
printf（"最小路程花费：
\n"）;
fprintf（stdout,"%d\n",bestc）;
return0;
}
指导教师评语：
1、文档：
a、内容：
不完整□完整□详细□
b、方案设计：
较差□合理□非常合理□
c、实现：
未实现□部分实现□全部实现□
d、文档格式：
不规范□基本规范□规范
升级会员 