单源最短路径分支限界

一、实验名称：单源最短路径问题时间：X年X月X日星期，第三、四节地点：0#601二、实验目的及要求、掌握分支限界法解题步骤：在题的边带权的解空间树中进行广度优先搜索找个叶结点使其对应路径的权最小(最大搜索到达一个扩展结点一次性扩展它的所有儿子满足约束条件且最小耗费函数目函数限界的儿,入活结点表活结点表中取下一结点同样扩展直到到所需的解或活动结点表为空为止三、实验环境下的vs2010四、实验内容单源最短路径问题以一个例子来说明单源最短路径问题：在下图所给的有向图中每一边都有一个非负边权。求图G的源顶点到目标顶点之的最短路径五、算法描述及实验步骤算法思想：解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表先级是结点所对应的当前路长。算法从图G的顶点s和空优先队列开始s被扩展后儿子结点被依次插入堆中。算法每次从堆中取出具有最小当前路长的结点作为当前扩展结点次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点ij有边可达，且从源出发，途经i再j的所相应路径长度，小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。结点扩展过程一直继续到活结点优先队列为空时为止/

二．单源最短路径问题问题描下面以一个例子来说明单源最短路径问题：在下图所给的有向图中，每一边都有一个非负边权。要求图的源顶点到标顶点t之的最短路径。下图是用优先队列式分支限界法解有向图G的源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。算法思想解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。/

算法从图的顶点和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中此算从堆中取出具有最小当前路长的结点作为当前扩展结点依检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到点j有可达，且从源出发，途经顶点i再顶点j的相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。剪策略在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。在算法中，利用结点间的控制关系进行剪枝。从源顶点s出2条同路径达图G的同一顶点于条路径的路不同此以将路长长的路径所对应的树中的结点为根的子树剪去。下图是用优先队列式分支限界法解有向图的源最短路径题产生的解空间树的剪枝情况。三．程序设计：#include<iostream>namespaceint=intinf=5000;//点距离上界/

//第一组测试参数int//图顶点个数加1int//图的驱顶点intdist[]={0,0,5000,5000,5000,5000};//短距离数组int{{0,0,0,0,0,0},{0,0,2,3,5000,5000},//的邻接矩阵{0,5000,0,1,2,5000},{0,5000,5000,0,9,2},/*二组测试参数int//顶点个数加int//图的前驱顶点intdist[]=int};*/classMinHeapNode{public:inti;//点编号int//当前路长};//循环队列class{intMinHeapNodedata[size];CirQueue(){==0;}//元素入队操作voidqueryIn(MinHeapNodee){if((rearfront){rear=//尾指针在循环意义下加=//队尾插入元素}}//元素出队操作/

MinHeapNodequeryOut(){if(rear!=front){=//列在循环意义下加}}//读取队头元素，但不出队MinHeapNodegetQuery(){if(rear!=front){}}//判断队列是否为空{frontrear;}//判断队列是否为满full(){+1)%sizefront;}结//图的表示class{//单源最短路径问题的优先队列式支限界法voidshortestPath(intv){//创建队列qq;//定义源为初始扩展结点MinHeapNodee;v;=dist[v]=qq.queryIn(e);//搜索问题的解空间/

{for(intj={{break;}MinHeapNodem=qq.getQuery();+c[m.i][j]dist[j])){//顶点i到点j可，且满足控制约束=m.length+c[m.i][j];prev[j]=m.i;//加入活结点优先队列MinHeapNodemi;mi.i=j;mi.length=dist[j];if(qq.full()){break;}qq.queryIn(mi);//元入队}}//for环结束{break;}qq.queryOut();//该结点的孩子结点全部入队后，删除该结点}//while循结束}//方法结束};//类结束int{cout<<"最路径长为"<<dist[n-1]<<endl;cout<<"中路径为：";for(inti=3;i<n;i++){";/

}cout<<endl<<"欢使用本系统"<<endl;return0;}五．算法优缺点：每一步的扩散为当前耗散度的最优。队列式分支限界法的搜索解空间树的方式类似于解空间树的宽度优先搜索，不同的是队列式分支限界法不搜索以不可行结点（已经被判定不能导致可行解或不能导致最优解的结点）为根的子树。按照规则，这样的结点不被列入活结点表。A->E->Q->M优先队列式分支限界法的搜索方式是根据活结点的优先级确定下一个扩展结点。结点的优先级常用一个与该结点有关的数值表示优队列规定p值大的结点点的优先级较高。在算