算法分析与设计.docx
- 文档编号:9381884
- 上传时间:2023-05-18
- 格式:DOCX
- 页数:20
- 大小:47.78KB
算法分析与设计.docx
《算法分析与设计.docx》由会员分享,可在线阅读,更多相关《算法分析与设计.docx(20页珍藏版)》请在冰点文库上搜索。
算法分析与设计
重庆邮电大学研究生堂下考试答卷
2015-2016学年第1学期
考试科目算法分析与设计
姓名胡飘
年级研一
学号S150231023
专业计算机技术
2015年12月31日
算法是求解问题类的、机械的、统一的方法,常用于计算、数据处理(英语:
Dataprocessing)和自动推理。
可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。
或者看成按照要求设计好的有限的确切的计算序列,并且这样的步骤和序列可以解决一类问题。
算法中的指令描述的是一个计算,当其运行时能从一个初始状态和(可能为空的)初始输入开始,经过一系列有限而清晰定义的状态,最终产生输出并停止于一个终态。
一个状态到另一个状态的转移不一定是确定的。
随机化算法在内的一些算法,包含了一些随机输入。
一、单源最短路径问题
在现实生活中,求最短路径的问题比比皆是,其中最为常见的就是单源最短路径问题。
比如:
乘汽车旅行的人总希望找出到目的地的尽可能的短的行程。
如果有一张地图并在图上标出每对十字路口之间的距离,如何找出这一最短行程?
物流配送中,如何设计最短路径来节省物流成本等的问题。
针对这些类似的问题,本文设计出相应的问题模型,然后对模型使用不同的算法进行结果的分析对比。
问题模型如下:
0
1
2
4
3
60
100
3010
1060
50
Dijkstra算法:
采用贪心算法范式进行设计,又称为单源最短路径,所谓单源是在一个有向图中,从一个顶点出发,求该顶点至所有可到达顶点的最短路径问题。
要顺利实现算法,要求理解Dijstra的算法,同时还要理解图的一些基本概念,图由节点和边构成,将节点和边看成对象,每个对象有自己的特有属性。
该算法的理论分析如下:
最短路径的最优子结构性质:
如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,k和s是这条路径上的一个中间顶点,那么P(k,s)必定是从k到s的最短路径。
下面证明该性质的正确性。
假设P(i,j)={Vi....Vk..Vs...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)
则与P(i,j)是从i到j的最短路径相矛盾。
由上述性质可知,如果存在一条从i到j的最短路径(Vi.....Vk,Vj),Vk是Vj前面的一顶点。
那么(Vi...Vk)也必定是从i到k的最短路径。
为了求出最短路径,Dijkstra就提出了以最短路径长度递增,逐次生成最短路径的算法。
譬如对于源顶点V0,首先选择其直接相邻的顶点中长度最短的顶点Vi,那么当前已知可得从V0到达Vj顶点的最短距离dist[j]=min{dist[j],dist[i]+matrix[i][j]}。
根据这种思路,假设存在G=
1.从V-U中选择使dist[i]值最小的顶点i,将i加入到U中;
2.更新与i直接相邻顶点的dist值(dist[j]=min{dist[j],dist[i]+matrix[i][j]});
3.知道U=V,停止。
该算法的主要实现代码(本文使用的C++,操作系统为wind10家庭版)如下:
#include
#include
#include
#defineM100
#defineN100
usingnamespacestd;
typedefstructnode
{
intmatrix[N][M];//邻接矩阵
intn;//顶点数
inte;//边数
}MGraph;
voidDijkstraPath(MGraphg,int*dist,int*path,intv0)//v0表示源顶点
{
inti,j,k;
bool*visited=(bool*)malloc(sizeof(bool)*g.n);
for(i=0;i { if(g.matrix[v0][i]>0&&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; for(i=1;i { intmin=INT_MAX; intu; for(j=0;j { if(visited[j]==false&&dist[j] { min=dist[j]; u=j; } } visited[u]=true; for(k=0;k { if(visited[k]==false&&g.matrix[u][k]>0&&min+g.matrix[u][k] { dist[k]=min+g.matrix[u][k]; path[k]=u; } } } } voidshowPath(int*path,intv,intv0)//打印最短路径上的各个顶点 { stack intu=v; while(v! =v0) { s.push(v); v=path[v]; } s.push(v); while(! s.empty()) { cout< s.pop(); } } intmain(intargc,char*argv[]) { clock_tstart,finish; intn,e;//表示输入的顶点数和边数 while(cin>>n>>e&&e! =0) { inti,j; ints,t,w;//表示存在一条边s->t,权值为w MGraphg; intv0; int*dist=(int*)malloc(sizeof(int)*n); int*path=(int*)malloc(sizeof(int)*n); for(i=0;i for(j=0;j g.matrix[i][j]=0; g.n=n; g.e=e; for(i=0;i { cin>>s>>t>>w; g.matrix[s][t]=w; } cin>>v0;//输入源顶点 DijkstraPath(g,dist,path,v0); for(i=0;i { if(i! =v0) { showPath(path,i,v0); cout< } } finish=clock(); cout<<"算法的执行时间为: "<<(double)(finish-start)/CLOCKS_PER_SEC< } return0; } 运行结果如下: 算法执行效率的对比分析: 综述以上对Dijkstra算法的理论分析和所采用的数据存储结构可知,本次实验是用权重矩阵来表示有向图,优先队列用无序数组来实现,所以该算法的时间复杂度为O(n*n)。 该实验的算法执行时间为0.002ms。 Bellman-ford算法: 是求含负权图的单源最短路径算法,效率很低,但代码很容易写。 即进行持续地松弛(原文是这么写的,为什么要叫松弛,争议很大),每次松弛把每条边都更新一下,若n-1次松弛后还能更新,则说明图中有负环,无法得出结果,否则就成功完成。 Bellman-ford算法有一个小优化: 每次松弛先设一个标识flag,初值为FALSE,若有边更新则赋值为TRUE,最终如果还是FALSE则直接成功退出。 Bellman-ford算法浪费了许多时间做没有必要的松弛,而SPFA算法用队列进行了优化,效果十分显著,高效难以想象。 SPFA还有SLF,LLL,滚动数组等优化。 该算法的理论分析如下: 1,.初始化: 将除源点外的所有顶点的最短距离估计值d[v]←+∞,d[s]←0; 2.迭代求解: 反复对边集E中的每条边进行松弛操作,使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离;(运行|v|-1次) 3.检验负权回路: 判断边集E中的每一条边的两个端点是否收敛。 如果存在未收敛的顶点,则算法返回false,表明问题无解;否则算法返回true,并且从源点可达的顶点v的最短距离保存在d[v]中。 该算法的主要实现代码(本文使用的C++,操作系统为wind10家庭版)如下: #include #include #include #include #include #include usingnamespacestd; constintmaxnum=100; constintmaxint=99999; typedefstructEdge{ intu,v;//起点,重点 intweight;//边的权值 }Edge; Edgeedge[maxnum];//保存边的值 intdist[maxnum];//结点到源点最小距离 intnodenum,edgenum,source;//结点数,边数,源点 voidinit() { cin>>nodenum>>edgenum>>source;//输入结点数,边数,源点 for(inti=1;i<=nodenum;++i) dist[i]=maxint; dist[source]=0; for(i=1;i<=edgenum;++i) { cin>>edge[i].u>>edge[i].v>>edge[i].weight; if(edge[i].u==source)//注意这里设置初始情况 dist[edge[i].v]=edge[i].weight; } } voidrelax(intu,intv,intweight)//松弛计算 { if(dist[v]>dist[u]+weight) dist[v]=dist[u]+weight; } boolBellman_Ford() { for(inti=1;i<=nodenum-1;++i) for(intj=1;j<=edgenum;++j) relax(edge[j].u,edge[j].v,edge[j].weight); boolflag=1; //判断是否有负环路 for(i=1;i<=edgenum;++i) if(dist[edge[i].v]>dist[edge[i].u]+edge[i].weight) { flag=0; break; } returnflag; } intmain() { clock_tstart,finish; init(); start=clock(); if(Bellman_Ford()){ for(inti=1;i cout< finish=clock(); cout<<"算法的执行时间为: "<<(double)(finish-start)/CLOCKS_PER_SEC< } return0; } 运行结果如下: 算法执行效率的对比分析: Bellman-Ford算法从理论上来说,其在求单源最短路径问题上,可以判断有无负权回路,时效性也较好,时间复杂度为O(V*E)。 该实验的算法执行时间为0.001ms。 分析以上两种算法的代码和实验结果,将Bellman-Ford算法和Dijkstra算法这两种算法进行对比分析如下: 1.权值 Dijkstra算法无法对权值为负值的图进行求解最短路径,而Bellman-Ford算法可以判断图中是否存在负权回路,然后求出最短路径解。 因此,从算法的应用范围分析的话,Dijkstra算法显然有一定的局限性。 2.时间复杂度(仅考虑矩阵存储的图) 理论上,Dijkstra算法的时间复杂度为O(V*V+E),Bellman-Ford算法的时间复杂度为O(V*E),所以Bellman-Ford算法的时效性比Dijkstra算法的时效性更好;从以上的实验数据也可以看出来。 3.算法简单性 两个算法都是比较简单的。 由于本问题主要考虑现实生活中的简单单源最短路径问题,未涉及到负权的情形,并且两个算法都用到了“松弛计算”的方法寻找最短路径。 所以两个算法的简单性相当。 4.优缺点的对比 算法 所属类型 最优解 优点 缺点 Dijkstra算法 贪心策略 局部最优解,但并不一定是全局最优解 算法简明 效率低、运算中占用空间大 Bellman-Ford算法 偏于动态规划 无 代码很容易写 效率很低 二、字符串匹配问题 字符串匹配(stringmatch)是在实际工程中经常会碰到的问题,通常其输入是原字符串(String)和子串(又称模式,Pattern)组成,输出为子串在原字符串中的首次出现的位置。 通常精确的字符串搜索算法包括暴力搜索(Bruteforce),KMP,BM(BoyerMoore),sunday,robin-karp以及bitap。 下面分析这几种方法并给出其实现。 假设原字符串长度M,字串长度为N。 Bruteforce算法: 属于一种蛮力算法,是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和T的第二个字符;若不相等,则比较S的第二个字符和T的第一个字符,依次比较下去,直到得出最后的匹配结果。 该算法的主要思想: 首先S[1]和T[1]比较,若相等,则再比较S[2]和T[2],一直到T[M]为止;若S[1]和T[1]不等,则S向右移动一个字符的位置,再依次进行比较。 如果存在k,1≤k≤N,且S[k+1…k+M]=T[1…M],则匹配成功;否则失败。 该算法最坏情况下要进行M*(N-M+1)次比较,时间复杂度为O(M*N)。 该算法的主要实现代码如下: intbf(constchar*text,constchar*find) {if(text=='/0'||find=='/0')return-1; intfind_len=strlen(find); inttext_len=strlen(text); if(text_len char*s=text; char*p=s; char*q=find; while(*p! ='/0') {if(*p==*q){ p++; q++;} else {s++; p=s; q=find; } if(*q=='/0') {return(p-text)-(q-find); } } return-1; } KMP算法: 是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。 KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。 具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。 该算法的主要思想: 在KMP算法中,对于每一个模式串我们会事先计算出模式串的内部匹配信息,在匹配失败时最大的移动模式串,以减少匹配次数。 该算法的主要实现代码如下: intkmp(constchar*text,constchar*find) {if(text=='/0'||find=='/0')return-1; intfind_len=strlen(find); inttext_len=strlen(text); if(text_len intmap[find_len]; memset(map,0,find_len*sizeof(int));map[0]=0; map[1]=0;inti=2;intj=0; for(i=2;i {while (1){if(find[i-1]==find[j]){ j++;if(find[i]==find[j]){ map[i]=map[j];} else{map[i]=j;} break; }else{if(j==0) {map[i]=0;break;} j=map[j];}} } i=0;j=0; for(i=0;i {i++;j++;} else{j=map[j];if(j==0)i++;} if(j==(find_len))returni-j;} return-1; } BoyerMoore算法: 由BobBoyer和JStrotherMoore设计于1977年,其是字符串匹配算法中的经典。 该算法的主要思想是常规的匹配算法移动模式串的时候是从左到右,而进行比较的时候也是从左到右的。 该算法的主要实现代码如下: intbm(constchar*text,constchar*find) {if(text=='/0'||find=='/0')return-1; inti,j,k;inttext_len=strlen(text); intfind_len=strlen(find); if(text_len intdelta_1[CHAR_MAX]; for(i=0;i for(i=0;i intrpr[find_len];rpr[find_len-1]=find_len-1; for(i=find_len-2;i>=0;i--){intlen=(find_len-1)-i; for(j=find_len-2;j>=(len-1);j--){ if(strncmp(find+i+1,find+j-len+1,len)==0){ if((j-len)==-1||find[i]! =find[j-len]){ rpr[i]=j-len+1;break;} }} for(k=1;j<(len-1)&&k if(strncmp(find+i+k,find,len-k)==0){ rpr[i]=0-k;break;} } if(j<(len-1)&&k==len){rpr[i]=0-len;} } intdelta_2[find_len]; for(i=0;i i=find_len-1;j=find_len-1; while(i {i--;j--;}else{ if(delta_1[text[i]]>delta_2[j]) {i+=delta_1[text[i]]; } else { i+=delta_2[j]; } j=find_len-1; } if(j==-1) returni+1; } return-1; } Sunday算法: 是DanielM.Sunday于1990年提出的字符串模式匹配。 该算法的主要思想: 在匹配过程中,模式串并不被要求一定要按从左向右进行比较还是从右向左进行比较,它在发现不匹配时,算法能跳过尽可能多的字符以进行下一步的匹配,从而提高了匹配效率。 假设在发生不匹配时S[i]≠T[j],1≤i≤N,1≤j≤M。 此时已经匹配的部分为u,并假设字符串u的长度为L。 很明显,该算法在字符串匹配时总共分为三种情况: 1)S[L+i+1]肯定要参加下一轮的匹配,并且T[M]至少要移动到这个位置(即模式串T至少向右移动一个字符的位置)。 2)S[L+i+1]在模式串T中没有出现。 这个时候模式串T[0]移动到S[L+i+1]之后的字符的位置。 3)S[L+i+1]在模式串中出现。 这里S[L+i+1]从模式串T的右侧,即按T[M-1]、T[M-2]、…T[0]的次序查找。 如果发现S[L+i+1]和T中的某个字符相同,则记下这个位置,记为k,1≤k≤M,且T[k]=S[L+i+1]。 此时,应该把模式串T向右移动M-k个字符的位置,即移动到T[k]和S[L+i+1]对齐的位置。 该算法的主要实现代码如下: intsunday(constchar*text,constchar*find) {if(text=='/0'||find=='/0')return-1; charmap[CHAR_MAX]; inti;inttext_
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 分析 设计