实验四单源最短路径问题

《实验四单源最短路径问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实验四单源最短路径问题一、实验口的：1、理解分支限界法的剪枝搜索策略；2、掌握分支限界法的算法柜架；3、掌握分支限界法的算法步骤；4、通过应用范例学习动态规划算法的设计技巧与策略；二、实验内容及要求：1、使用分支限界法解决单源最短路径问题。2、通过上机实验进行算法实现。3、保存和打印出程序的运行结果，并结合程序进行分析，上交实验报告。三、实验原理：分支限界法的基本思想：1、分支限界法与回溯法的不同：1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所宥解，而分支限界法的求解目标则是找出满足

2、约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。2）搜索方式的不同：冋溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。2、分支限界法基本思想：分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空问树。在分支限界法屮，毎一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不町行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表屮取下

3、一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。3、常见的两种分支限界法：1)队列式(FIFO)分支限界法按照队列先进先出(FIFO)原则选取下一个节点为扩展节点。2)优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。四、程序代码：ttincludeusingnamespacestd;ftdefineMAX5000//定义无穷大classGraph/tpublic:voidShorestPath

4、s(int);voidShowDist();Graph();private:intn;//图的节点个数int氺prev;//存放顶点的前驱节点int氺氺c;//存放图的邻接矩阵classMinHeapNodefriendGraph;public:intgetl(){returni;}voidsetl(intii)length;}//顶点编号//当前路长intgetLengthO{returnvoidsetLength(intlen){length=len;}private:inti;intlengt

5、h;｝；classMinHeapfriendGraph;public:MinHeap();MinHeap(int);voidDeleteMin(MinHeapNode&);voidInsert(MinHeapNode);boolOutOfBounds();private:intlength;MinHeapNode*node;Graph::Graph()intwi=0;cout＜〈"请输入图的邻接矩阵：（无穷大请以5000代替）"〈〈endl;intyi=0;cin>〉n;c=newint*[n+l]

6、;dist=newint[n+1];prev=newint[n+1];for(wi=0;wi<=n;wi++)c[wi]=newint[n+1];if(wi==0){for(yi=0;yi<=n;yi++){c[wi][yi]=0;}}else{for(yi=0;yi<=n;yi++){if(yi==0){c[wi][yi]=0;}else{cin»c[wi][yi];}for(wi=0;wi<=n;wi++){dist[wi]=MAX;prev[wi]=0;}}voidGraph::ShowDis

7、tO{cout«"从源点到该节点的最短路径<〈〈endl;inti=0;inttemp=0;for(i=1;i<=n;i++){cout«〃dist["〈〈i〈〈"]="〈〈dist[i]«endl;}cout«〃从源点到终点的最短路径长度为:〃〈〈dist[n]«endl;cout«〃其路径为：〃；temp=n;while(temp!=0){if(prevEtemp]==0)cout«(temp);else{cout«(temp)〈〈〃〈-}temp=prev[temp];}cout<

8、}voidGraph::ShorestPaths(intv){MinHeapH(n);//最小堆MinHeapNodeE;//扩展节点E.i=v;E.length=0;dist[v]=0;//搜索问题的解空间树while(true){intj=0;for(j=1;j<=n;j++){cout〈〈"c["〈〈E.i〈〈"]r«j〈〈"]="«c[E.i][j]«endl;if((c[E.i][j]!=MAX)&&(c[E.i][j]!=0))//节点控制关系if(E.l