欢迎来到天天文库
浏览记录
ID:55173476
大小:83.00 KB
页数:4页
时间:2020-04-30
《单源最短路径问题.doc》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、实验四单源最短路径问题一、实验目的:1、理解分支限界法的剪枝搜索策略;2、掌握分支限界法的算法柜架;3、掌握分支限界法的算法步骤;4、通过应用范例学习动态规划算法的设计技巧与策略;二、实验内容及要求:1、使用分支限界法解决单源最短路径问题。2、通过上机实验进行算法实现。3、保存和打印出程序的运行结果,并结合程序进行分析,上交实验报告。三、实验原理:分支限界法的基本思想:1、分支限界法与回溯法的不同:1)求解目标:回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最
2、优解。2)搜索方式的不同:回溯法以深度优先的方式搜索解空间树,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。2、分支限界法基本思想:分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。3、常见的两种分支限界法
3、:1)队列式(FIFO)分支限界法按照队列先进先出(FIFO)原则选取下一个节点为扩展节点。2)优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。四、程序代码#includeusingnamespacestd;intmatrix[100][100];//邻接矩阵boolvisited[100];//标记数组intdist[100];//源点到顶点i的最短距离intpath[100];//记录最短路的路径intsource;//源点intvertex_num;//顶点数intedge_num;//边数intd
4、estination;//终结点voidDijkstra(intsource){memset(visited,0,sizeof(visited));//初始化标记数组visited[source]=true;for(inti=0;i5、st=INT_MAX;for(intj=0;j6、cost_index][j]+min_cost>vertex_num;cout<<"请输入图的边数:";cin>>edge_num;for(inti=0;i7、cout<<"请输入边的信息:";intu,v,w;for(inti=0;i>u>>v>>w;matrix[u][v]=matrix[v][u]=w;}cout<<"请输入源点(<"<>source;Dijkstra(source);cout<<"请输入终结点(<"<>destination;cout<8、短距离是:"<
5、st=INT_MAX;for(intj=0;j6、cost_index][j]+min_cost>vertex_num;cout<<"请输入图的边数:";cin>>edge_num;for(inti=0;i7、cout<<"请输入边的信息:";intu,v,w;for(inti=0;i>u>>v>>w;matrix[u][v]=matrix[v][u]=w;}cout<<"请输入源点(<"<>source;Dijkstra(source);cout<<"请输入终结点(<"<>destination;cout<8、短距离是:"<
6、cost_index][j]+min_cost>vertex_num;cout<<"请输入图的边数:";cin>>edge_num;for(inti=0;i7、cout<<"请输入边的信息:";intu,v,w;for(inti=0;i>u>>v>>w;matrix[u][v]=matrix[v][u]=w;}cout<<"请输入源点(<"<>source;Dijkstra(source);cout<<"请输入终结点(<"<>destination;cout<8、短距离是:"<
7、cout<<"请输入边的信息:";intu,v,w;for(inti=0;i>u>>v>>w;matrix[u][v]=matrix[v][u]=w;}cout<<"请输入源点(<"<>source;Dijkstra(source);cout<<"请输入终结点(<"<>destination;cout<8、短距离是:"<
8、短距离是:"<
此文档下载收益归作者所有