欢迎来到天天文库
浏览记录
ID:59300079
大小:315.50 KB
页数:5页
时间:2020-09-06
《单源最短路径(分支限界法).doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、算法分析与设计实验报告第7次实验姓名学号班级时间12.26上午地点四合院实验名称分支界限法求最短路径实验目的(1)掌握并运用分支限界法基本思想(2)运用分支限界法实现单源最短路径问题。实验原理给定下示有向图,利用分支限界法的思想,计算并输出其单源最短路径。实验步骤1算法从图G的源顶点s和空优先队列开始。结点s被扩展后,它的儿子结点被依次插入堆中;2算法每次从堆中取出具有最小当前路长的结点作为当前扩展结点,并依次检查与当前扩展结点相邻的所有顶点;3如果从当前扩展结点i到j有边可达,且从源出发,途经i再到j的所相应路径长度,小于
2、当前最优路径长度,则将该顶点作为活结点插入到活结点优先队列中;4结点扩展过程一直继续到活结点优先队列为空时为止关键代码voidshorest(intv){priority_queueheap;HeapNodeenode(v,0);for(inti=1;i<=n;i++)dist[i]=MAX;dist[v]=0;//搜索问题的解空间while(1){for(intj=1;j<=n;j++)if(a[enode.i][j]3、顶点I到J是可达的,并且满足控制约束{dist[j]=enode.length+a[enode.i][j];HeapNodenode(j,dist[j]);heap.push(node);//加入活节点优先队列}if(heap.empty())break;//优先队列为空else{enode=heap.top();heap.pop();}}}测试结果随机数产生图的权值:实验心得通过这次实验,我回顾了分支界限法求解最短路径问题,在其中加入了舍伍德随机化取值过程,使数据分布更加均匀,让我熟悉了随机化算法,也让结果更加公平可靠。本4、次实验在书本有详细的算法,很容易实现了上面的图形,同时仿照了回溯算法中随机取值产生权值的方法生成了一个图,并且通过改进,实现了随机选择源点的方法进行求解最短路径。通过这次实验,不仅掌握了分支界限算法,还掌握了随机产生一个图并计算其最短路径的算法,让我觉得收获颇大。实验得分助教签名附录:完整代码#include#include#includeusingnamespacestd;#defineMAX9999//定义为无限大#defineN60intn,dist[N],a[N]5、[N];classHeapNode//最小堆来存储活节点表{public:inti,length;//顶点编号,当前的路径长度HeapNode(){}HeapNode(intii,intl){i=ii;length=l;}booloperator<(constHeapNode&node)const{returnlengthheap;HeapNodeenode(v,0);for(inti=1;i<=n;i++)d6、ist[i]=MAX;dist[v]=0;//搜索问题的解空间while(1){for(intj=1;j<=n;j++)if(a[enode.i][j]7、=heap.top();heap.pop();}}}intmain(){intv,i;cout<<"个数:";cin>>n;cout<<"源点:";cin>>v;for(inti=1;i<=n;i++)for(intj=1;j<=n;j++){if(i!=j){if((a[j][i]==0)8、9、(a[j][i]==MAX))a[i][j]=rand()%100+1;elsea[i][j]=MAX;if(a[i][j]>50)a[i][j]=MAX;}}cout<<"路径:"<10、){for(intj=1;j
3、顶点I到J是可达的,并且满足控制约束{dist[j]=enode.length+a[enode.i][j];HeapNodenode(j,dist[j]);heap.push(node);//加入活节点优先队列}if(heap.empty())break;//优先队列为空else{enode=heap.top();heap.pop();}}}测试结果随机数产生图的权值:实验心得通过这次实验,我回顾了分支界限法求解最短路径问题,在其中加入了舍伍德随机化取值过程,使数据分布更加均匀,让我熟悉了随机化算法,也让结果更加公平可靠。本
4、次实验在书本有详细的算法,很容易实现了上面的图形,同时仿照了回溯算法中随机取值产生权值的方法生成了一个图,并且通过改进,实现了随机选择源点的方法进行求解最短路径。通过这次实验,不仅掌握了分支界限算法,还掌握了随机产生一个图并计算其最短路径的算法,让我觉得收获颇大。实验得分助教签名附录:完整代码#include#include#includeusingnamespacestd;#defineMAX9999//定义为无限大#defineN60intn,dist[N],a[N]
5、[N];classHeapNode//最小堆来存储活节点表{public:inti,length;//顶点编号,当前的路径长度HeapNode(){}HeapNode(intii,intl){i=ii;length=l;}booloperator<(constHeapNode&node)const{returnlengthheap;HeapNodeenode(v,0);for(inti=1;i<=n;i++)d
6、ist[i]=MAX;dist[v]=0;//搜索问题的解空间while(1){for(intj=1;j<=n;j++)if(a[enode.i][j]7、=heap.top();heap.pop();}}}intmain(){intv,i;cout<<"个数:";cin>>n;cout<<"源点:";cin>>v;for(inti=1;i<=n;i++)for(intj=1;j<=n;j++){if(i!=j){if((a[j][i]==0)8、9、(a[j][i]==MAX))a[i][j]=rand()%100+1;elsea[i][j]=MAX;if(a[i][j]>50)a[i][j]=MAX;}}cout<<"路径:"<10、){for(intj=1;j
7、=heap.top();heap.pop();}}}intmain(){intv,i;cout<<"个数:";cin>>n;cout<<"源点:";cin>>v;for(inti=1;i<=n;i++)for(intj=1;j<=n;j++){if(i!=j){if((a[j][i]==0)
8、
9、(a[j][i]==MAX))a[i][j]=rand()%100+1;elsea[i][j]=MAX;if(a[i][j]>50)a[i][j]=MAX;}}cout<<"路径:"<10、){for(intj=1;j
10、){for(intj=1;j
此文档下载收益归作者所有