《算法分析与设计》word版.docx

重庆邮电大学研究生堂下考试答卷2015-2016学年第 1 学期考试科目 算法分析与设计 姓 名 胡飘 年 级 研一 学 号 S150231023 专 业 计算机技术 2015 年 12月 31日算法是求解问题类的、机械的、统一的方法，常用于计算、数据处理（英语：Data processing）和自动推理。可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。一、 单源最短路径问题在现实生活中，求最短路径的问题比比皆是，其中最为常见的就是单源最短路径问题。比如：乘汽车旅行的人总希望找出到目的地的尽可能的短的行程。如果有一张地图并在图上标出每对十字路口之间的距离，如何找出这一最短行程？物流配送中，如何设计最短路径来节省物流成本等的问题。针对这些类似的问题，本文设计出相应的问题模型，然后对模型使用不同的算法进行结果的分析对比。问题模型如下:01243 60 100 30 10 10 60 50Dijkstra算法: 采用贪心算法范式进行设计，又称为单源最短路径，所谓单源是在一个有向图中，从一个顶点出发，求该顶点至所有可到达顶点的最短路径问题。要顺利实现算法，要求理解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)。则与P(i,j)是从i到j的最短路径相矛盾。由上述性质可知，如果存在一条从i到j的最短路径(Vi.Vk,Vj)，Vk是Vj前面的一顶点。那么(Vi.Vk)也必定是从i到k的最短路径。为了求出最短路径，Dijkstra就提出了以最短路径长度递增，逐次生成最短路径的算法。譬如对于源顶点V0，首先选择其直接相邻的顶点中长度最短的顶点Vi，那么当前已知可得从V0到达Vj顶点的最短距离distj=mindistj,disti+matrixij。根据这种思路，假设存在G=，源顶点为V0，U=V0,disti记录V0到i的最短距离，pathi记录从V0到i路径上的i前面的一个顶点。1.从V-U中选择使disti值最小的顶点i，将i加入到U中；2.更新与i直接相邻顶点的dist值(distj=mindistj,disti+matrixij)；3.知道U=V，停止。该算法的主要实现代码（本文使用的C+,操作系统为wind10家庭版）如下：#include #include#include#define M 100#define N 100using namespace std;typedef struct node int matrixNM; /邻接矩阵 int n; /顶点数 int e; /边数 MGraph; void DijkstraPath(MGraph g,int *dist,int *path,int v0) /v0表示源顶点 int i,j,k; bool *visited=(bool *)malloc(sizeof(bool)*g.n); for(i=0;i0&i!=v0) disti=g.matrixv0i; pathi=v0; /path记录最短路径上从v0到i的前一个顶点 else disti=INT_MAX; /若i不与v0直接相邻，则权值置为无穷大 pathi=-1; visitedi=false; pathv0=v0; distv0=0; visitedv0=true; for(i=1;ig.n;i+) /循环扩展n-1次 int min=INT_MAX; int u; for(j=0;jg.n;j+) /寻找未被扩展的权值最小的顶点 if(visitedj=false&distjmin) min=distj; u=j; visitedu=true; for(k=0;k0&min+g.matrixukdistk) distk=min+g.matrixuk; pathk=u; void showPath(int *path,int v,int v0) /打印最短路径上的各个顶点 stack s; int u=v; while(v!=v0) s.push(v); v=pathv; s.push(v); while(!s.empty() couts.top()ne&e!=0) int i,j; int s,t,w; /表示存在一条边s-t,权值为w MGraph g; int v0; int *dist=(int *)malloc(sizeof(int)*n); int *path=(int *)malloc(sizeof(int)*n); for(i=0;iN;i+) for(j=0;jM;j+) g.matrixij=0; g.n=n; g.e=e; for(i=0;istw; g.matrixst=w; cinv0; /输入源顶点 DijkstraPath(g,dist,path,v0); for(i=0;in;i+) if(i!=v0) showPath(path,i,v0); coutdistiendl; finish=clock(); cout 算法的执行时间为：(double)(finish - start) / CLOCKS_PER_SEC endl; return 0;运行结果如下： 算法执行效率的对比分析：综述以上对Dijkstra算法的理论分析和所采用的数据存储结构可知，本次实验是用权重矩阵来表示有向图，优先队列用无序数组来实现，所以该算法的时间复杂度为O(n*n)。该实验的算法执行时间为0.002ms。Bellman-ford算法：是求含负权图的单源最短路径算法，效率很低，但代码很容易写。即进行持续地松弛（原文是这么写的，为什么要叫松弛，争议很大），每次松弛把每条边都更新一下，若n-1次松弛后还能更新，则说明图中有负环，无法得出结果，否则就成功完成。Bellman-ford算法有一个小优化：每次松弛先设一个标识flag，初值为FALSE，若有边更新则赋值为TRUE，最终如果还是FALSE则直接成功退出。Bellman-ford算法浪费了许多时间做没有必要的松弛，而SPFA算法用队列进行了优化，效果十分显著，高效难以想象。SPFA还有SLF，LLL，滚动数组等优化。该算法的理论分析如下：1,.初始化：将除源点外的所有顶点的最短距离估计值 dv +, ds 0;2.迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次）3.检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在 dv中。该算法的主要实现代码（本文使用的C+,操作系统为wind10家庭版）如下：#include #include #include #include #include #include using namespace std;const int maxnum = 100;const int maxint = 99999;typedef struct Edgeint u, v; / 起点，重点int weight; / 边的权值Edge;Edge edgemaxnum; / 保存边的值int distmaxnum; / 结点到源点最小距离int nodenum, edgenum, source; / 结点数，边数，源点 void init() cin nodenum edgenum source; / 输入结点数，边数，源点for(int i=1; i=nodenum; +i)disti = maxint;distsource = 0;for( i=1; i edgei.u edgei.v edgei.weight;if(edgei.u = source) /注意这里设置初始情况distedgei.v = edgei.weight;void relax(int u, int v, int weight) / 松弛计算if(distv distu + weight)distv = distu + weight;bool Bellman_Ford()for(int i=1; i=nodenum-1; +i)for(int j=1; j=edgenum; +j)relax(edgej.u, edgej.v, edgej.weight);bool flag = 1;/ 判断是否有负环路for( i=1; i distedgei.u + edgei.weight)flag = 0;break;return flag;int main()clock_t start,finish; init();start = clock();if(Bellman_Ford()for(int i = 1 ;i nodenum; i+)cout disti endl;finish = clock(); cout 算法的执行时间为：(double)(finish - start) / CLOCKS_PER_SEC endl;return 0;运行结果如下：算法执行效率的对比分析：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算法偏于动态规划无代码很容易写效率很低二、 字符串匹配问题字符串匹配（string match)是在实际工程中经常会碰到的问题，通常其输入是原字符串(String)和子串（又称模式，Pattern)组成，输出为子串在原字符串中的首次出现的位置。通常精确的字符串搜索算法包括暴力搜索(Brute force)，KMP, BM(Boyer Moore), sunday, robin-karp 以及 bitap。下面分析这几种方法并给出其实现。假设原字符串长度M，字串长度为N。Brute force算法：属于一种蛮力算法，是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。该算法的主要思想：首先S1和T1比较，若相等，则再比较S2和T2，一直到TM为止；若S1和T1不等，则S向右移动一个字符的位置，再依次进行比较。如果存在k，1kN，且Sk+1k+M=T1M，则匹配成功；否则失败。该算法最坏情况下要进行M*(N-M+1)次比较，时间复杂度为O(M*N)。该算法的主要实现代码如下：int bf(const char *text, const char *find)if (text = /0 | find = /0) return -1; int find_len = strlen(find); int text_len = strlen(text); if (text_len find_len) return -1; 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算法中，对于每一个模式串我们会事先计算出模式串的内部匹配信息，在匹配失败时最大的移动模式串，以减少匹配次数。该算法的主要实现代码如下：int kmp(const char *text, const char *find) if (text = /0 | find = /0) return -1; int find_len = strlen(find); int text_len = strlen(text); if (text_len find_len) return -1; int mapfind_len; memset(map, 0, find_len*sizeof(int); map0 = 0; map1 = 0; int i = 2; int j = 0; for (i=2; ifind_len; i+) while (1) if (findi-1 = findj) j+;if (findi = findj) mapi = mapj; elsemapi = j; break; else if (j = 0) mapi = 0; break; j = mapj; i = 0; j = 0; for (i=0; itext_len;) if (texti = findj) i+;j+; elsej = mapj; if (j = 0) i+; if (j = (find_len) return i-j; return -1;Boyer Moore算法：由Bob Boyer和J Strother Moore设计于1977年，其是字符串匹配算法中的经典。该算法的主要思想是常规的匹配算法移动模式串的时候是从左到右，而进行比较的时候也是从左到右的。该算法的主要实现代码如下：int bm(const char *text, const char *find)if (text = /0 | find = /0) return -1; int i, j, k; int text_len = strlen(text); int find_len = strlen(find); if (text_len find_len) return -1; int delta_1CHAR_MAX; for (i=0; iCHAR_MAX; i+)delta_1i = find_len; for (i=0; i=0; i-) int len = (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 | findi != findj-len) rpri = j - len + 1; break; for (k=1; j(len-1) & klen; k+) if (strncmp(find+i+k, find, len-k) = 0) rpri = 0 - k; break; if (j(len-1) & k = len) rpri = 0 - len; int delta_2find_len; for (i=0; ifind_len; i+) delta_2i = find_len - rpri; i = find_len - 1; j = find_len - 1; while (i delta_2j) i += delta_1texti; else i += delta_2j; j = find_len - 1; if (j = -1) return i+1; return -1;Sunday算法：是Daniel M.Sunday于1990年提出的字符串模式匹配。该算法的主要思想：在匹配过程中，模式串并不被要求一定要按从左向右进行比较还是从右向左进行比较，它在发现不匹配时，算法能跳过尽可能多的字符以进行下一步的匹配，从而提高了匹配效率。假设在发生不匹配时SiTj，1iN，1jM。此时已经匹配的部分为u，并假设字符串u的长度为L。很明显，该算法在字符串匹配时总共分为三种情况: 1）SL+i+1肯定要参加下一轮的匹配，并且TM至少要移动到这个位置(即模式串T至少向右移动一个字符的位置)。2）SL+i+1在模式串T中没有出现。这个时候模式串T0移动到SL+i+1之后的字符的位置。3）SL+i+1在模式串中出现。这里SL+i+1从模式串T的右侧，即按TM-1、TM-2、T0的次序查找。如果发现SL+i+1和T中的某个字符相同，则记下这个位置，记为k，1kM，且Tk=SL+i+1。此时，应该把模式串T向右移动M-k个字符的位置，即移动到Tk和SL+i+1对齐的位置。该算法的主要实现代码如下：int sunday(const char *text, const char *find)if (t