分支限界法实验(单源最短路径).doc

《分支限界法实验(单源最短路径).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法分析与设计实验报告第七次实验姓名学号班级时间12.26上午地点工训楼309实验名称分支限界法实验(单源最短路径)实验目的1.掌握并运用分支限界法的基本思想2.运用分支限界法实现单源最短路径问题实验原理问题描述：在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。基本思想：下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。为了加速搜索的进程，应采用有效地方式选择活结点进行扩展

2、。按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。实验步骤（1）算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中；（2）算法每次从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点；（3）如果从当前扩展结点i到j有边可达，且从源出发，途经i再到j的所相应路径长度，小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中；（4）结点扩展过程一直继续到活结点优先队列为空时为止。关键代码//单源最短路径问题的优

3、先队列式分支限界法templatevoidGraph::shortest_path(intv){//定义最小堆的容量为1000MinHeap>H(1000);//定义源为初始扩展结点MinHeapNodeE;//初始化源结点E.i=v;E.length=0;dist[v]=0;while(true)//搜索问题的解空间{for(intj=1;j<=n;j++)if((c[E.i][j]!=0)&&(E.length

4、+c[E.i][j]N;N.i=j;N.length=dist[j];H.Insert(N);//插入到最小堆中}try{H.DeleteMin(E);//取下一扩展结点}catch(int){break;}if(H.curr

5、entsize==0)//优先队列空{break;}}}测试结果上述有向图的结果：实验分析在实验中并没有生成多组数据，进行比较，也没有利用随机生成函数，因为在这种有实际有关联的问题中，利用随机生成函数生成的数据是十分的不合适的，在此我们只需要验证该程序是否正确即可。分支限界法求单源最短路径问题与回溯法求单源最短路径问题其大致思想是一致的，都是利用解空间树，搜索子集树，回溯法是利用深度优先搜索子集树，而分支限界法是利用广度优先搜索子集树，然后利用队列或优先队列，最小堆存放可扩展的结点，然后将活结点

6、出堆，从而直到堆空为止，找到最优解。实验心得在这一章的分支限界法中，与上一章的回溯法很相似，都是利用解空间树进行搜索，从而找到最优解。不同的是回溯法利用的是深度优先回溯寻找，能够找到所有的最优解；而分支限界法则是利用广度优先搜索子集树或者排序树，利用队列或者优先级队列的数据结构组织所有满足的结点，这样只要找到一种最优解就可以了，想对于回溯法来说时间上相对利用的没有那么多。在这一章的学习上，由于会利用最小堆/最大堆，所以代码看起来比较复杂，堆的实现也比较复杂，这是这一章我学习的一个难点，不过正在渐

7、渐攻克。实验得分助教签名附录：完整代码（分支限界法）Shorest_path.cpp//单源最短路径问题分支限界法求解#include#include#include#include"MinHeap2.h"usingnamespacestd;templateclassGraph//定义图类{friendintmain();public:voidshortest_path(int);private:intn,//图的顶点数

8、*prev;//前驱顶点数组Type**c,//图的邻接矩阵*dist;//最短距离数组};templateclassMinHeapNode//最小堆中的元素类型为MinHeapNode{friendGraph;public:operatorint()const{returnlength;}private:inti;//顶点编号Typelength;//当前路长};//单源最短路径问题的优先队列式分支限界法templatevoidGraph