算法的设计（第3章蛮力法）.pptVIP

第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中是否含有子串P m i c r o s o f w i n d o w s t s o f t 3.1 字符串匹配 蛮力法：从左到右扫描T，检查T中是否含有子串P m i c r o s o f w i n d o w s t s o f t 3.1 字符串匹配 蛮力法：从左到右扫描T，检查T中是否含有子串P m i c r o s o f w i n d o w s t s o f t 3.1 字符串匹配 蛮力法：从左到右扫描T，检查T中是否含有子串P m i c r o s o f w i n d o w s t s o f t 匹配成功，返回位置索引5 3.1 字符串匹配 [字符串匹配算法] Algorithm Brute_Match(T, P: string) begin let i = 0, n = |T|, m = |P|; while (i ≤ n?m) do let j = 0; while (j m) do if (T[i+j] ≠ P[j]) then break; j ? j + 1; if (j = m) then return i; //匹配成功 i ? i + 1; return ?1; end 时间复杂度O(m(m?n))：存在改进可能？ 3.2 矩阵相乘 输入：m×n型矩阵A和n×p型矩阵B 输出：C = A×B 3.2 矩阵相乘 [矩阵相乘算法] Algorithm MatrixMultiple(A, B: int[,]) begin let (m,n) = |A|, (n,p)= |B|, C = new int[m,p]; for i = 0 to m-1 do for j = 0 to p?1 do for k = 0 to n?1 do C[i,j]) ? C[i,j] + A[i,k]*B[k,j]; return C; end 时间复杂度O(mnp)：不存在改进可能 3.3 子集和问题 输入：一组n个整数的集合S，以及一个目标数z 输出：判断是否存在S的一个子集S*，其元素之和等于z 3.3 子集和问题 蛮力法：检查S的每个子集 S’，直至找到一个元素之和等于z的子集，失败则返回空集。 时间复杂度O(2n) [子集和问题的蛮力算法] Algorithm Brute_Subset(z: int; S: int[]) begin foreach S’ ? Powerset(S) do if (Sum(S’) = z) then return S; return Φ; end 3.4 冒泡排序 冒泡排序过程 令 k = 1; for i = 1 to n?k do if (A[i?1] A[i]) then A[i?1] ? A[i] 当k = n时算法结束；否则令 k = k+1, 转第2步 [排序问题] 输入：任意一个长度为n的数组A 输出：这组数的一个重排列A′ ，其满足A′[0]≤A′[1]≤…≤A′[n?1] 3.4 冒泡排序 [冒泡排序算法] Algorithm BubbleSort(A: int[]) begin let n = |A|; for k = 1 to n-1 do for i = 1 to n?k do if (A[i-1] A[i]) then (A[i-1], A[i]) ? (A[i], A[i-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中所有顶点对之间的距离，并取其中距离最小的一对顶点。 时间复杂