《单源最短路径1分支限界》由会员分享，可在线阅读，更多相关《单源最短路径1分支限界（7页珍藏版）》请在金锄头文库上搜索。
1、一、实验名称：单源最短路径问题时间：X年X月X日，星期3,第三、四节地点：0#601二、实验目的及要求1、掌握分支限界法解题步骤：1在问题的边带权的解空间树中进行广度优先搜索2找一个叶结点使其对应路径的权最小（最大）3 当搜索到达一个扩展结点时,一次性扩展它的所有儿子4 将满足约束条件且最小耗费函数目标函数限界的儿子,插入活结点表中5 从活结点表中取下一结点同样扩展直到找到所需的解或活动结点表为空为止三、实验环境Window下的vs2010四、实验内容单源最短路径问题以一个例子来说明单源最短路径问题：在下图所给的有向图G中，每一边都有一个非负边权。解单源最短路径问题的优先队列式分支限界法用一极
2、小堆来存储活结点表。其优先级是结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。算法每次从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到j有边可达，且从源出发，途经i再到j的所相应路径长度，小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。结点扩展过程一直继续到活结点优先队列为空时为止二单源最短路径问题1.问题描述下面以一个例子来说明单源最短路径问题：在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。下图是用优先队列
3、式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中每一个结点旁边的数字表示该结点所对应的当前路长。b324ge55,41296g5671071411768102.算法思想解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活
4、结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。3.剪枝策略在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。在算法中，利用结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树的剪枝情况。20126610714111QA优于乩B可剪枝经过不同的路径到达相同的顶点三程序设计：#includeusingnamespacestd;constintsize=1
5、00;constintinf=5000;/两点距离上界/第一组测试参数constintn=6;/图顶点个数加1intprevn;/图的前驱顶点intdist=0,0,5000,5000,5000,5000;/最短距离数组intcnn=0,0,0,0,0,0,0,0,2,3,5000,5000,/图的邻接矩阵0,5000,0,1,2,5000,0,5000,5000,0,9,2,0,5000,5000,5000,0,2,0,5000,5000,5000,5000,0;/*第二组测试参数constintn=5;/图顶点个数加1intprevn;/图的前驱顶点intdist=0,0,5000,500
6、0,5000;intcn=0,0,0,0,0,0,0,2,3,5000,0,5000,0,1,2,0,5000,5000,0,9,0,5000,5000,5000,0;*/classMinHeapNodepublic:inti;/顶点编号intlength;/当前路长;/循环队列classCirQueueprivate:intfront,rear;MinHeapNodedatasize;public:CirQueue()front=rear=0;/元素入队操作voidqueryIn(MinHeapNodee)if(rear+1)%size!=front)rear=(rear+1)%size;/
7、队尾指针在循环意义下加1datarear=e;/在队尾插入元素/元素出队操作MinHeapNodequeryOut()if(rear!=front)front=(front+1)%size;/队列在循环意义下加1returndatafront;/读取队头元素，但不出队MinHeapNodegetQuery()if(rear!=front)returndata(front+1)%size;/判断队列是否为空boolempty()returnfront=rear;/判断队列是否为满boolfull()return(rear+1)%size=front;/CirQueue结束/图的表示classGr
8、aphpublic:/单源最短路径问题的优先队列式分支限界法voidshortestPath(intv)/创建队列CirQueueqq;/定义源为初始扩展结点MinHeapNodee;e.i=v;e.length=0;distv=0;qq.queryIn(e);/搜索问题的解空间while(true)for(intj=1;j=n)break;MinHeapNodem=qq.getQuery();if(cm.ijinf)&(m.length+cm.ijdistj)/顶点i到顶点j可达，且满足控制约束distj=m.length+cm.ij;prevj=m.i;/加入活结点优先队列MinHeapN
9、odemi;mi.i=j;mi.length=distj;if(qq.full()break;qq.queryIn(mi);/元素入队/for循环结束if(qq.empty()break;qq.queryOut();/当该结点的孩子结点全部入队后，删除该结点/while循环结束/方法结束;/类结束intmain()Graphg;g.shortestPath(1);coutvv最短路径长为vvdistn-lvvendl;coutvv中间路径为：;for(inti=3;in;i+)coutpreviE-Q-M优先队列式分支限界法的搜索方式是根据活结点的优先级确定下一个扩展结点。结点的优先级常用一个与该结点有关的数值p来表示。最大优先队列规定p值较大的结点点的优先级较高。在算法实现时通常用一个最大堆来实现最大优先队列，体现最大效益优先的原则。类似地，最小优先队列规定p值较小的结点的优先级较高。在算法实现时，常用一个最小堆来实现，体现最小优先的原则。采用优先队列式分支定界算法解决具体问题时，应根据问题的特点选用最大优先或最小优先队列，确定各个结点点的p值
