算法设计 教学课件 作者 郑宇军 石海鹤 陈胜勇 算法设计（第3章）.ppt

《算法设计 教学课件 作者 郑宇军 石海鹤 陈胜勇 算法设计（第3章）.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第3章蛮力法3.1字符串匹配3.2矩阵相乘3.3子集和问题3.4冒泡排序3.5若干最优化问题蛮力法一些问题只能采用蛮力法去求解蛮力法设计简单，用其求解一些小问题也是可接受的3.1字符串匹配输入：两个字符串T和P输出：T中P首次出现的位置（T中不包含P则返回−1）T(Text),P(Pattern)3.1字符串匹配蛮力法：从左到右扫描T，检查T中是否含有子串Pmicrosofwindowstsoft3.1字符串匹配蛮力法：从左到右扫描T，检查T中是否含有子串Pmicrosofwindowstsoft3.1字符串匹配蛮力法：从左到右扫描T，检查T中是否含有子串

2、Pmicrosofwindowstsoft3.1字符串匹配蛮力法：从左到右扫描T，检查T中是否含有子串Pmicrosofwindowstsoft3.1字符串匹配蛮力法：从左到右扫描T，检查T中是否含有子串Pmicrosofwindowstsoft3.1字符串匹配蛮力法：从左到右扫描T，检查T中是否含有子串Pmicrosofwindowstsoft匹配成功，返回位置索引53.1字符串匹配[字符串匹配算法]AlgorithmBrute_Match(T,P:string)beginleti=0,n=

3、T

4、,m=

5、P

6、;while(i≤n−m)doletj=0;w

7、hile(j

8、A

9、,(n,p)=

10、B

11、,C=newint[m,p];fori=0tom-1doforj=0top−1dofork=0ton−1doC[i,j])C[

12、i,j]+A[i,k]*B[k,j];returnC;end时间复杂度O(mnp)：不存在改进可能3.3子集和问题输入：一组n个整数的集合S，以及一个目标数z输出：判断是否存在S的一个子集S*，其元素之和等于z3.3子集和问题蛮力法：检查S的每个子集S’，直至找到一个元素之和等于z的子集，失败则返回空集。时间复杂度O(2n)[子集和问题的蛮力算法]AlgorithmBrute_Subset(z:int;S:int[])beginforeachS’Powerset(S)doif(Sum(S’)=z)thenreturnS';returnΦ;end3.4冒泡

13、排序冒泡排序过程令k=1;fori=1tonkdoif(A[i1]>A[i])thenA[i1]↔A[i]当k=n时算法结束；否则令k=k+1,转第2步[排序问题]输入：任意一个长度为n的数组A输出：这组数的一个重排列A′，其满足A′[0]≤A′[1]≤…≤A′[n−1]3.4冒泡排序[冒泡排序算法]AlgorithmBubbleSort(A:int[])beginletn=

14、A

15、;fork=1ton-1dofori=1ton−kdoif(A[i-1]>A[i])then(A[i-1],A[i])(A[i],A[i-1]);end时间复杂度O(n2

16、)3.5若干最优化问题最优化问题：在问题的可行域F中找到一个解x，使得某目标函数值f(x)最小或最大。约束条件：解x应满足某项约束c(x)=true连续优化问题：解的数量可能有无穷多组合优化问题：解的数量有限时，总是可以用蛮力法求解，但算法效率可能很低。3.5若干最优化问题最近点对问题0-1背包问题最优子集和问题最大独立集和最小顶点覆盖旅行商问题3.5.1最近点对问题输入：二维平面上n个点的集合P输出：其中距离最近的两个点3.5.1最近点对问题蛮力法：计算出P中所有顶点对之间的距离，并取其中距离最小的一对顶点。时间复杂度O(n2)：存在改进可能？[最近点对

17、问题的蛮力算法]AlgorithmBrute_ClosetPoints(P:Point[])beginletd_best=+∞,n=

18、P

19、,a=b=-1;fori=0ton-2doforj=i+1ton-1dolet(dx,dy)=(P[i].x-P[j].x,P[i].y-P[j].y);d=dx*dx+dy*dy;if(d

20、出：S的一个子集A，其重量之和不大于W，且价值之和尽可能大。3.5