单源最短路径分支限界

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到目

3、标顶点t之间的最短路径。下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中,每一个结点旁边的数字表示该结点所对应的当前路长。Ca324eh55,126gm567107r1172. 算法思想解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是 结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。结点 s被扩展后，它的儿子结点被依次插入 堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最

4、优路径长度，则将该顶点作为活结点插 入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。3. 剪枝策略在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。在算法中，利用结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到达图 G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树的剪枝情况。经过不同 的路徑到 达相同的三.程序设计：#in clude<iostream>using n amespa

5、ce std;const int size = 100;con st int inf = 5000;/ 两点距离上界/第一组测试参数const int n = 6;/图顶点个数加 1int prevn;/图的前驱顶点int dist = 0,0,5000,5000,5000,5000;/最短距离数组int cnn = 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;/* 第二组测试参数const int

6、n = 5; /图顶点个数加 1int prevn; / 图的前驱顶点int dist = 0,0,5000,5000,5000;int cn=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 ;*/class MinHeapNodepublic :int i;/ 顶点编号int length; / 当前路长;/循环队列class CirQueueprivate:int front,rear;MinHeapNode datasize; public:CirQueue()front = rear = 0;

7、/元素入队操作void queryIn(MinHeapNode e)if(rear +1)%size != front)rear = (rear+1)%size; / 队尾指针在循环意义下加 1 datarear = e; / 在队尾插入元素/元素出队操作MinHeapNode queryOut()if(rear != front)front = (front+1)%size; / 队列在循环意义下加 1 return datafront;/读取队头元素，但不出队MinHeapNode getQuery()if(rear != front)return data(front+1)%size;/

8、判断队列是否为空bool empty()return front = rear;/判断队列是否为满bool full()return (rear +1)%size = front;/CirQueue 结束/图的表示class Graphpublic:/单源最短路径问题的优先队列式分支限界法void shortestPath(int v)/ 创建队列CirQueue qq;/定义源为初始扩展结点MinHeapNode e;e.i = v;e.length = 0;distv = 0;qq.queryIn(e);/搜索问题的解空间while(true)for(int j = 1;j<n;j+

9、)if(j>=n)break;MinHeapNode m = qq.getQuery();if(cm.ij<inf)&&(m.length + cm.ij < distj)/顶点i到顶点j可达，且满足控制约束distj = m.length + cm.ij;prevj = m.i;/加入活结点优先队列MinHeapNode mi;mi.i = j;mi.length = distj;if(qq.full()break;qq.queryIn(mi);/元素入队/for 循环结束if(qq.empty()break;qq.queryOut(); /当该结点的孩子结

10、点全部入队后，删除该结点/while 循环结束/ 方法结束;/ 类结束int main()Graph g;g.shortestPath(1);cout<<" 最短路径长为"<<distn-1<<endl;cout<<" 中间路径为："for(int i =3;i<n;i+)cout<<previ<<" "cout<<endl<<"欢迎使用本系统"<<endl; return 0;contInue'C:Prcgram Files (x86)Microsoft Visual S1=1S e恵用翔间迎;统> 系 石为本五算法优缺点：每一步的扩散为当前耗散度的最优。队列式分支限界法的搜索解空间树的方式类似于解空间树的宽度优先搜索，不同的是队 列式分支限界法不搜索以不可行结点（已经被判定不能导致可行解或不能导致最优解的结 点）为根的子树。按照规则，这样的结点不被列入活结点表。A->E->Q->M优先队列式分支限界法的搜索方式是根据活结点的优先级确定下一个扩展结点。结点的 优先级常用一个与该结点有关的数值p来表