




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、算法分析与设计实验报告分支限界法实现单源最短路径班级: 11计算机1 姓名: 金李扬 日期: 5.22 1.问题描述以分支限界法实现单源最短路径1.以分支限界实现优先队列2.再以分支限界法的优先队列实现单元最短路径以该图为算法测试数据,获得链接矩阵如下:以-1代表无法到达的点-1 2 3 4 -1 -1 -1 -1 -1 -1 -1-1 -1 3 -1 7 2 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 9 2 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 3 3 -1 -1-1 -1 -1 -1 -
2、1 -1 1 -1 3 -1 -1-1 -1 -1 -1 -1 -1 -1 -1 5 1 -1-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -12.算法思想分支限界法基本思想:分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非最优
3、解的儿子结点被舍弃,其余儿子结点被加入活结点表中。此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。算法步骤1.用一极小堆来存储活结点表,其优先级是结点所对应的当前路长。2.算法从图G的源顶点s和空优先队列开始。结点s被扩展后,它的儿子结点被依次插入堆中。此后,算法从堆中取出具有最小当前路长的结点作为当前扩展结点,并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达,且从源出发,途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度,则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过
4、程一直继续到活结点优先队列为空时为止。剪枝函数1.在算法扩展结点的过程中,一旦发现一个结点的下界不小于当前找到的最短路长,则算法剪去以该结点为根的子树。2.在算法中,利用结点间的控制关系进行剪枝。从源顶点s出发,2条不同路径到达图G的同一顶点。由于两条路径的路长不同,因此可以将路长长的路径所对应的树中的结点为根的子树剪去。3.算法设计1.定义HEAPNODE结构体:typedef struct HeapNode int left, right; int weight; bool friend operator < (const HeapNode &a, const HeapNod
5、e &b) return a.weight > b.weight; int i,length; HeapNode() HeapNode(int ii,int l) i=ii; length=l; ;2.以堆实现优先队列类:#define MAXN 25500class priority_queue private : HeapNode rMAXN; int length; void heap_adjust(int s, int m) HeapNode rc = rs; for (int j = s << 1; j <= m; j <<= 1) if
6、(j < m && rj < rj+1) j+; if (!(rc < rj) break; rs = rj; s = j; rs = rc; public : priority_queue() length = 0; /*=下面是堆操作部分,建堆,堆排等=*/ void creat_heap() for (int i = length >> 1; i > 0; i-) heap_adjust(i, length); void set_size(int length) this->length = length; void set_va
7、lue(int id, HeapNode value) rid = value; void heap_sort() for (int i = length; i > 1; i-) HeapNode tmp = r1; r1 = ri; ri = tmp; heap_adjust(1, i - 1); bool is_heap() int len = length >> 1 - 1, j; if (len < 1) if (length = 1 | (!(r1 < rlength) && !(r1 < rlength - 1) return t
8、rue; return false; for (int i = 1; i <= len; i+) j = i << 1; if (rj < rj + 1) j+; if (ri < rj) return false; return true; /* 用堆实现的priority_queue */ void push(HeapNode rc) +length; rlength = rc; int s = length >> 1; for (int j = length; j > 1; j >>= 1) if (!(rs < rj)
9、break; HeapNode tmp = rs; rs = rj; rj = tmp; s >>= 1; void pop() HeapNode tmp = r1; r1 = rlength; rlength = tmp; heap_adjust(1, -length); HeapNode top() return r1; int size() return length; bool empty() if (length <= 0) return true; return false; ;3.分支限界法实现单源最短路径void shorest(int v) priority
10、_queue heap; HeapNode enode(v,0); for(int i=1; i<=n; i+) disti=MAX; distv=0; while(1) for(int j=1; j<=n; j+) if(aenode.ij<MAX && enode.length+aenode.ij<distj) distj=enode.length+aenode.ij; HeapNode node(j,distj); heap.push(node); if(heap.empty() break; else enode=heap.top(); heap.pop(); 4.主函数int main ()cout<<"请输入节点个数:" cin>>n;cout<<"请输入n*n的链接矩阵:"<<endl; for(int i=1; i<=n; i+) for(int j=1; j<=n; j+) cin>>aij; if(aij=-1) aij=MAX; shorest(
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 高端私人飞机航线申请与全球旅行定制服务合同
- 房产处分权与抵押权解除及清偿协议
- 外贸企业单证处理外包派遣及培训合同
- 跨国房地产投资运营管理合同
- 肺癌新辅助治疗进展与临床实践
- 灾害救援私人直升机航拍空域申请及影像记录合同
- 建筑幕墙胶缝更换与节能效果评估协议
- 数据库资源运营权授权与市场推广合同
- 妇科手术护理操作规范
- Web前端开发技术项目教程(HTML5 CSS3 JavaScript)(微课版) 课件 5.1.13任务操作视频
- 五年级数学竞赛试题原创
- 教师听课评价记录表
- 十字头夹具设计说明书
- 物理高考最后一课课件
- 04S202 室内消火栓安装
- 电解质紊乱的心电图表现
- 2022年修改后的银行业G32表填报说明
- 巨量-信息流(初级)认证考试(重点)题库(含答案)
- 三年级硬笔书法课课件
- 佳发教育考试网上巡查系统(标准版)
- 投融资部面试题本
评论
0/150
提交评论