《单源最短路径1 分支限界》由会员分享，可在线阅读，更多相关《单源最短路径1 分支限界（7页珍藏版）》请在金锄头文库上搜索。
1、 一、实验名称：单源最短路径问题 时间：X 年 X 月 X 日，星期 3，第三、四节 地点：0#601 二、实验目的及要求 1、掌握分支限界法解题步骤： 1 在问题的边带权的解空间树中进行广度优先搜索 2 找一个叶结点使其对应路径的权最小(最大) 3 当搜索到达一个扩展结点时,一次性扩展它的所有儿子 4 将满足约束条件且最小耗费函数 目标函数限界的儿子,插入活结点 表中 5 从活结点表中取下一结点同样扩展直到找到所需的解或活动结点表 为空为止 三、实验环境 Window 下的 vs2010 四、实验内容 单源最短路径问题 以一个例子来说明单源最短路径问题：在下图所给的有向图 G 中，每一边都有
2、一个非负边权。 求图 G 的从源顶点 s 到目标顶点 t 之间的最短路径 五、算法描述及实验步骤 算法思想：解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。 算法从图 G 的源顶点 s 和空优先队列开始。结点 s 被扩展后，它的儿子结点被依次插入堆中。 算法每次从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。 如果从当前扩展结点 i 到 j 有边可达，且从源出发，途经 i 再到 j 的所相应路径长度，小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。 结点扩展过程一直继续到活结点优先队列
3、为空时为止二单源最短路径问题 1.问题描述 下面以一个例子来说明单源最短路径问题：在下图所给的有向图 G 中，每一边都有一个非负边权。要求图 G 的从源顶点 s 到目标顶点 t 之间的最短路径。下图是用优先队列式分支限界法解有向图 G 的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。2. 算法思想 解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。算法从图 G 的源顶点 s 和空优先队列开始。结点 s 被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检
4、查与当前扩展结点相邻的所有顶点。如果从当前扩展结点 i 到顶点 j 有边可达，且从源出发，途经顶点 i 再到顶点 j 的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。 这个结点的扩展过程一直继续到活结点优先队列为空时为止。3. 剪枝策略 在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。 在算法中，利用结点间的控制关系进行剪枝。从源顶点 s 出发，2 条不同路径到达图G 的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。 下图是用优先队列式分支限界法解有向图 G
5、的单源最短路径问题产生的解空间树的剪枝情况。三程序设计：#includeusing namespace std;const int size = 100;const 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,500
6、0,0,2,0,5000,5000,5000,5000,0;/*第二组测试参数const int 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;MinHeapNod
7、e datasize;public:CirQueue()front = rear = 0;/元素入队操作void queryIn(MinHeapNode e)if(rear +1)%size != front)rear = (rear+1)%size; /队尾指针在循环意义下加 1datarear = e; /在队尾插入元素/元素出队操作 MinHeapNode queryOut()if(rear != front)front = (front+1)%size; /队列在循环意义下加 1return datafront;/读取队头元素，但不出队MinHeapNode getQuery()if(
8、rear != front)return data(front+1)%size;/判断队列是否为空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);/搜
9、索问题的解空间 while(true)for(int j = 1;j=n)break;MinHeapNode m = qq.getQuery();if(cm.ijE-Q-M 优先队列式分支限界法的搜索方式是根据活结点的优先级确定下一个扩展结点。结点的优先级常用一个与该结点有关的数值 p 来表示。最大优先队列规定 p 值较大的结点点的优先级较高。在算法实现时通常用一个最大堆来实现最大优先队列，体现最大效益优先的原则。类似地，最小优先队列规定 p 值较小的结点的优先级较高。在算法实现时，常用一个最小堆来实现，体现最小优先的原则。采用优先队列式分支定界算法解决具体问题时，应根据问题的特点选用最大优先或最小优先队列，确定各个结点点的 p 值
