《分支限界法实验.docx》由会员分享，可在线阅读，更多相关《分支限界法实验.docx（11页珍藏版）》请在三一办公上搜索。
1、算法分析与设计实验报告第七次实验姓名学号班级时间12.26上午地点工训楼309实验名称实验目的分支限界法实验（单源最短路径）1. 掌握并运用分支限界法的基本思想2. 运用分支限界法实现单源最短路径问题问题描述：在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。实验原理 基本思想：下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。为了加速搜索的 进程，应采用有效地方式选择活结点进行扩展。按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。实验步骤关键代码（1）算法
2、从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次 插入堆中；（2） 算法每次从堆中取出具有最小当前路长的结点作为当前扩展结点，并依 次 检查与当前扩展结点相邻的所有顶点；（3） 如果从当前扩展结点i到j有边可达，且从源出发，途经i再到j的所相 应路径长度，小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中；（4）结点扩展过程一直继续到活结点优先队列为空时为止。单源最短路径问题的优先队列式分支限界法template vclass Typevoid Graph:shortest path( int v) _定义最小堆的容量为1000Mi nH eapvMi nH
3、eapNode H(1000);定义源为初始扩展结点Min HeapNode E;初始化源结点E.i=v;E.le ngth=0;distv=0;while (true )搜索问题的解空间for (int j=1;j=n ;j+)if (cEij!=0)&(Elength+cEijdistj) 顶点i到顶点j可达，且满足控制约束顶点i和j之间有边，且此路径小于原先从源点到j的路径长度distj=E.length+cE.ij;/ 更新 dist 数组prevj=E.i;加入活结点优先队列Mi nH eapNode N;N.i=j;N.le ngth=distj;H.Insert(N);插入到最小
4、堆中try H.DeleteMi n(E);取下一扩展结点catch ( int )break;/优先队列空if (H.currentsize=0)break;上述有向图的结果:测试结果006 R-A ，-jtO J-r3 ,rvMAu 5 -.1曰!.11至IWH至K 1 . 从IIfilp xuroln9nTmuxH*H_uxnw-_- 0兰9-9=-口=日理日址一务4 -1取实验分析在实验中并没有生成多组数据，进行比较，也没有利用随机生成函数，因为在这种有实际有关联的问题中，利用随机生成函数生成的数据是十分的不合适的，在此我 们只需要验证该程序是否正确即可。分支限界法求单源最短路径问题与
5、回溯法求单源最短路径问题其大致思想是一致的，都是利用解空间树，搜索子集树， 回溯法是利用深度优先搜索子集树，而分支限界法是利用广度优先搜索子集树，然后利用队列或优先队列，活结 最小堆存放可扩展的结点，然后将 点出堆，从而直到堆空为止，找到最优解。实验心得在这一章的分支限界法中，与上一章的回溯法很相似，都是利用解空间树进行搜索，从而 找到最优解。不同的是回溯法利用的是深度优先回溯寻找，能够找到所有的最优解；而分支限界法则是利用广度优先搜索子集树或者排序树，利用队列或 者优先级队列的数据结构组织所有满足的结点，这样只要找到一种最优解就可以了，想对于回溯法来说时间上相对利用的没有那么多。在这一章的学
6、习上，由于会利用最小堆/最大堆，所以代码看起来比较复杂，堆的实现也比较复杂，这是这一章我学习的一个难点，不过正在渐渐攻克。实验得分助教签名附录：完整代码(分支限界法)Shorest_path.cpp单源最短路径问题分支限界法求解#include #inelude #include #include MinHeap2.h using namespacestd;template class Graph /定义图类friend int main();public :void shortest_path( int ); private :intn,图的顶点数*prev;前驱顶点数组Type *c,图的
7、邻接矩阵*dist;最短距离数组;template class MinHeapNode /最小堆中的元素类型为MinHeapNode friend Graph;public :operator int () const return length;private :int i;/顶点编号Type length;/ 当前路长;/单源最短路径问题的优先队列式分支限界法template void Graph:shortest_path( int v) MinHeapMinHeapNode H(1000)/;/ 定义最小堆的容量为 1000/定义源为初始扩展结点MinHeapNode E;/初始化源结
8、点E.i=v;E.length=0;distv=0;while (true )/搜索问题的解空间 for (int j=1;j=n;j+)if (cEij!=0)&(Elength+cEijdistj)顶点i到顶点j可达，且满足控制约束顶点i和j之间有边，且此路径小于原先从源点i到j的路径长度distj=E.length+cE.ij; / 更新 dist 数组 prevj=E.i;/加入活结点优先队列MinHeapNode N;N.i=j;N.length=distj;H.Insert(N); /插入到最小堆中try H.DeleteMin(E); / 取下一扩展结点catch ( int )
9、break ;if (H.currentsize=0) / 优先队列空 break ;)int main() int n=11;int prev12=0,0,0,0,0,0,0,0,0,0,0,0; / 初始化前驱顶点数组intdist12=1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000 ; / 初始化最短距离数组cout 单源图的邻接矩阵如下：vvendl;int *c= new int *n+1;for (int i=1;iv=n;i+) /输入图的邻接矩阵ci= new int n+1;for (int j=1;jc
10、ij;int v=1; /源结点为1Graphvint G;G.n=n;G.c=c;G.dist=dist;G.prev=prev;clock_t start,end,over; / 计算程序运行时间的算法 start=clock();end=clock();over=end-start;start=clock();G.shortest_path(v); /调用图的最短路径查找算法/输出从源结点到目的结点的最短路径coutvv从 S 到 T 的最短路长是:vvdist11vve ndl;for (int i=2;i=n;i+) /输出每个结点的前驱结点 cout prev( i )= prev
11、i endl;for (int i=2;i=n;i+) /输出从源结点到其他结点的最短路径长度 cout 从 1 至ij i 的最短路长是：distiendl;for (int i=1;i=n;i+) 删除动态分配时的内存 delete ci;delete c;c=0;end=clock();printf( The time is %6.3f ,( double )(end-start-over)/CLK_TCK);/ 显示运行时间coutendl;system( pause);return 0;)MinHeap.h#include template class Graph;template
12、class MinHeap / 最小堆类 template friend class Graph;public :MinHeap(int maxheapsize=10); / 构造函数，堆的大小是 10MinHeap() delete heap; / 最小堆的析构函数 int Size() const return currentsize; /Size()返回最小堆的个数 T Max() if (currentsize) return heap1; /第一个元素出堆MinHeap& Insert( const T& x); /最小堆的插入函数 MinHeap& DeleteMin(T& x);
13、/ 最小堆的删除函数void Initialize(T x, int size, int ArraySize); / 堆的初始化 void Deactivate();void output(T a, int n);private :int currentsize,maxsize;T *heap;template void MinHeap:output(T a, int n) / 输出函数，输出 a数组的元素for (int i=1;i=n;i+) coutai ; coutendl;template MinHeap:MinHeap(int maxheapsize) maxsize=maxhea
14、psize; heap=newTmaxsize+1; / 仓|建堆 currentsize=0;template MinHeap& MinHeap:Insert( const T& x) if (currentsize=maxsize) /如果堆中的元素已经等于堆的最大大小return *this ; /那么不能在加入元素进入堆中int i= +currentsize;while (i!=1 & xheapi/2)heapi=heapi/2; i/=2;heapi=x; return * this ;)template MinHeap& MinHeap:DeleteMin(T& x) / 删除
15、堆顶元素 if (currentsize=0) cout Empty heap! endl; return * this ;x=heap1;T y=heapcurrentsize-;int i=1,ci=2;while (ci=currentsize) if (ciheapci+1) ci+;if (y=heapci)break ;heapi=heapci;i=ci;ci*=2;heapi=y;return * this ;template void MinHeap:Initialize(T x, int size, int ArraySize) / 堆的初始 化 delete heap;heap=x;currentsize=size;maxsize=ArraySize;for (int i=currentsize/2;i=1;i-) T y=heapi;int c=2*i;while (c=currentsize)if (cheapc+1) c+;if (y=heapc)break ;heapc/2=heapc;c*=2;heapc/2=y;)template void MinHeap:Deactivate() heap=0;)
