算法设计(蛮力法)课件

第第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中是否含有子串Pm icrosofw in d o w stsoft3.1 字符串匹配蛮力法：从左到右扫描T，检查T中是否含有子串Pm icrosofw in d o w stsoft3.1 字符串匹配蛮力法：从左到右扫描T，检查T中是否含有子串Pm icrosofw in d o w stsoft3.1 字符串匹配蛮力法：从左到右扫描T，检查T中是否含有子串Pm icrosofw in d o w stsoft3.1 字符串匹配蛮力法：从左到右扫描T，检查T中是否含有子串Pm icrosofw in d o w stsoft3.1 字符串匹配蛮力法：从左到右扫描T，检查T中是否含有子串Pm icrosofw in d o w stsoft匹配成功，返回位置索引匹配成功，返回位置索引53.1 字符串匹配字符串匹配算法Algorithm Brute_Match(T,P:string)begin let i=0,n=|T|,m=|P|;while(i nm)do let j=0;while(j Ai)then Ai1 Ai3.当k=n时算法结束；否则令 k=k+1,转第2步 排序问题输入：任意一个长度为n的数组A输出：这组数的一个重排列A，其满足A0A1An13.4 冒泡排序冒泡排序算法Algorithm BubbleSort(A:int)begin let n=|A|;for k=1 to n-1 do for i=1 to nk do if(Ai-1 Ai)then (Ai-1,Ai)(Ai,Ai-1);end时间复杂度O(n2)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)：存在改进可能？最近点对问题的蛮力算法Algorithm Brute_ClosetPoints(P:Point)begin let d_best=+,n=|P|,a=b=-1;for i=0 to n-2 do for j=i+1 to n-1 do let(dx,dy)=(Pi.x-Pj.x,Pi.y-Pj.y);d=dx*dx+dy*dy;if(d v_best)then v_best v;S_best S;return(v_best,S_best);end3.5.3 子集和问题的最优化版本输入：一组n个整数的集合S，以及一个目标数z输出：S的一个子集S*，使其元素之和不大于z的情况下尽可能地大3.5.3 子集和问题的最优化版本蛮力法：检查S的每个子集 S，找出其中满足约束且元素之和最大的一个子集0-1背包的特殊情况3.5.4 最大独立集最大独立集/最小顶点覆盖图的独立集：图中两两互不相邻的顶点所组成的集合。输入：一个无向图G=输出：G中顶点数最多的一个独立集3.5.4 最大独立集最大独立集/最小顶点覆盖蛮力法：穷举V的所有子集V，判断每个子集是否为独立集，并从中选出规模最大的一个时间复杂度O(mn22n)最大独立集问题的蛮力算法Algorithm Brute_IndependentSet(V:set;E:set)begin let I=;foreach V Powerset(V)do let independent=true;foreach(u V)do foreach(v Vu)do if(u,v)E)then independent false;break;if(independent=false)then break;if(independent=true|V|I|)then I V;return I;end3.5.4 最大独立集/最小顶点覆盖最小顶点覆盖图G=顶点覆盖：V的一个子集V，它包含E中每条边的至少一个端点。输入：一个无向图G=输出：G中顶点数最少的一个顶点覆盖3.5.4 最大独立集/最小顶点覆盖最小顶点覆盖蛮力法：穷举V的所有子集V，判断每个子集是否为独立集，并从中选出规模最大的一个时间复杂度O(mn2n)最小顶点覆盖问题的蛮力算法Algorithm Brute_VertexCover(V:set;E:set)begin let C=V;foreach V Powerset(V)do let cover=true;foreach(u,v)E)do if(u V v V)then cover false;break;if(cover=true|V|C|)then C V;return C;end3.5.4 最大独立集/最小顶点覆盖最大独立集与最小顶点覆盖的关系？给定图G=，IV是G的一个独立集，当且仅当V I是G的一个顶点覆盖3.5.5 旅行商问题输入：一个加权连通图G=输出：通过G中所有顶点且距离最短的一条回路3.5.5 旅行商问题蛮力法：穷举图中n!条回路，并从中选出距离最短的一条时间复杂度O(n+1)!)旅行商问题的蛮力算法Algorithm Brute_TSP(G:Graph;w:int,)begin let d_best=+,L_best=;foreach L Perms(G.V)do let d=0;foreach(eL)do d d+we.a,e.b;d d+wL.tail,L.head;if(d d_best)then d_best d;L_best L;return L_best;end