《算法分析与设计》word版

《《算法分析与设计》word版》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、重庆邮电大学研究生堂下考试答卷2015-2016学年第1学期考试科目算法分析与设计姓名胡飘年级研一学号S150231023专业计算机技术2015年12月31日算法是求解问题类的、机械的、统一的方法，常用于计算、数据处理（英语：Dataprocessing）和自动推理。可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并

2、停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。一、单源最短路径问题在现实生活中，求最短路径的问题比比皆是，其中最为常见的就是单源最短路径问题。比如：乘汽车旅行的人总希望找出到目的地的尽可能的短的行程。如果有一张地图并在图上标出每对十字路口之间的距离，如何找出这一最短行程？物流配送中，如何设计最短路径来节省物流成本等的问题。针对这些类似的问题，本文设计出相应的问题模型，然后对模型使用不同的算法进行结果的分析对比。问题模型如下:01243601003010106050Dijkstra算

3、法:采用贪心算法范式进行设计，又称为单源最短路径，所谓单源是在一个有向图中，从一个顶点出发，求该顶点至所有可到达顶点的最短路径问题。要顺利实现算法，要求理解Dijstra的算法，同时还要理解图的一些基本概念，图由节点和边构成，将节点和边看成对象，每个对象有自己的特有属性。该算法的理论分析如下：最短路径的最优子结构性质:如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径，k和s是这条路径上的一个中间顶点，那么P(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。假设P(i,j)={Vi....Vk..V

4、s...Vj}是从顶点i到j的最短路径，则有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是从k到s的最短距离，那么必定存在另一条从k到s的最短路径P'(k,s)，那么P'(i,j)=P(i,k)+P'(k,s)+P(s,j)

5、法。譬如对于源顶点V0，首先选择其直接相邻的顶点中长度最短的顶点Vi，那么当前已知可得从V0到达Vj顶点的最短距离dist[j]=min{dist[j],dist[i]+matrix[i][j]}。根据这种思路，假设存在G=，源顶点为V0，U={V0},dist[i]记录V0到i的最短距离，path[i]记录从V0到i路径上的i前面的一个顶点。1.从V-U中选择使dist[i]值最小的顶点i，将i加入到U中；2.更新与i直接相邻顶点的dist值(dist[j]=min{dist[j],dist[i]+matrix[i][j]})

6、；3.知道U=V，停止。该算法的主要实现代码（本文使用的C++,操作系统为wind10家庭版）如下：#include#include#include#defineM100#defineN100usingnamespacestd;typedefstructnode{intmatrix[N][M];//邻接矩阵intn;//顶点数inte;//边数}MGraph;voidDijkstraPath(MGraphg,int*dist,int*path,intv0)//v0表示源顶点{inti,j,k

7、;bool*visited=(bool*)malloc(sizeof(bool)*g.n);for(i=0;i0&&i!=v0){dist[i]=g.matrix[v0][i];path[i]=v0;//path记录最短路径上从v0到i的前一个顶点}else{dist[i]=INT_MAX;//若i不与v0直接相邻，则权值置为无穷大path[i]=-1;}visited[i]=false;path[v0]=v0;dist[v0]=0;}visited[v0]=true;f

8、or(i=1;i