算法分析复习
算法复习
基础
- 复杂度计算
- 解递归式
蛮力法
-
TSP
-
KMP
分治法
思想
划分同类子问题，递归求解子问题，然后合并子问题
典型问题
-
最大子段和
-
子问题
求解左边、右边最大字段和
求解跨越两边的最大字段和
-
代码实现
private static int maxSum(int[] arr, int left, int right) { int sum = 0; if (left == right) { sum = arr[left]; } else { int mid = (left + right) / 2; //左边子问题：左边连续数字和最大是多少 int leftSum = maxSum(arr, left, mid); //右边子问题：右边边连续数字和最大是多少 int rightSum = maxSum(arr, mid + 1, right); //以下是求解中间横跨的子序列的最大和的理解 //必要条件是分割线所在元素与分割线左侧或右侧必须是连续的情况下的数字和才有意义 //所以可以约定 m m±1 处的元素处于同一个序列 //所以分开计算才是合理的 可以保证上述前提成立 //如果从左端点或者右端点开始算是不能保证算出来的最大和对映的子序列包含横跨两部分的数 //以左边第一个数结尾的连续数字和最大是多少 int temp = 0; int lSum = 0; for (int i = mid; i >= left; i--) { temp += arr[i]; lSum = Math.max(lSum, temp); } //右边第一个数开始的连续数字和最大是多少 temp = 0; int rSum = 0; for (int i = mid + 1; i <= right; i++) { temp += arr[i]; rSum = Math.max(rSum, temp); } sum = Math.max(Math.max(leftSum, rightSum), rSum + lSum); } return sum; }
-
-
最近对
数据需要按x排序
-
子问题
求解左、右两边最近对
根据最近距离取中间左右x轴范围内的点，按y轴排序，计算每个点与分割线另一侧点之间的最短距离
-
代码
public static double doDivide(Point[] points, int start, int end) { int size = end - start + 1; if (size == 2) { return points[start].distanceOf(points[end]); } int m = start + size/2; int xm = points[m].x; double dis = Math.min(doDivide(points, start, m), doDivide(points, m, end)); List<Point> p1 = new ArrayList<>(size); List<Point> p2 = new ArrayList<>(size); for (int i = m; i>=start; i--) { if (xm - points[i].x < dis) { p1.add(points[i]); } else { break; } } for (int i = m + 1; i<=end; i++) { if (points[i].x - xm < dis) { p2.add(points[i]); } else { break; } } if (p1.isEmpty()) { return dis; } p1.sort(Comparator.comparingInt(p->p.y)); p2.sort(Comparator.comparingInt(p->p.y)); for (int i = 0; i < p1.size(); i++) { Point p1p = p1.get(i); int j = i < p2.size() ? i : p2.size() - 1; //search up for (; j < p2.size(); j++) { Point p2p = p2.get(j); if (Math.abs(p2p.y - p1p.y) >= dis) { break; } else { dis = Math.min(dis, p2p.distanceOf(p1p)); } } //search down for (; j >= 0; j--) { Point p2p = p2.get(j); if (Math.abs(p2p.y - p1p.y) >= dis) { break; } else { dis = Math.min(dis, p2p.distanceOf(p1p)); } } } return dis; } public static double divided(Point[] points) { Arrays.sort(points, Comparator.comparingInt(p -> p.x)); return doDivide(points, 0, points.length-1); }
-
减治法
思想
划分同类子问题，递归求解一部分子问题，舍弃不符合条件的子问题
典型问题
-
大根堆
添加：至于最后，向上调整
删除：与最后一个元素交换，向下调整
-
假币问题
按3取模，分成3堆，不够3的倍数则凑成3的倍数
-
二叉查找树
动态规划
与贪心法的联系与区别
都是划分子问题求局部最优解推导全局最优解，贪心法子问题没有重叠 动态规划子问题相互重叠
设计思想和步骤
将待求解问题分成多个互相重叠子问题，每个子问题求解时依赖于前面的子问题。
- 划分子问题
- 确定动态规划函数
- 填写表格
典型问题
-
多段图：
-
最优性原理证明：设s,s1,s2 … t是s->t的最短路径 设s->s1已求出则问题变为s1,s2…t的最短路径问题,在这个问题 内一定有一条最短路径 否则存在s,s1,r1,r2…t的最短路径与前提矛盾。因此满足最优性原理
-
动态规划函数：
{ d ( s , v ) = c s v < s , v > ∈ E d ( s , v ) = m i n { d ( s , u ) + c u v } < s , u > ∈ E \begin{cases} d(s,v)=c_{sv} & <s,v>\in E \\ d(s,v)=min\{d(s,u)+c_{uv}\} & <s,u>\in E \end{cases} {d(s,v)=csvd(s,v)=min{d(s,u)+cuv}<s,v>∈E<s,u>∈E
-
-
TSP: (P108)
-
最优性原理证明：设s,s1,s2…s是一条最短回路，设s->s1已知，则s1,s2…s构成一条s1->s的最短路径，否则存在 s1,r1,r2…s为一条经过n-1个城市的最短路径则s,s1,r1,r2…s是最短回路与前提矛盾。因此满足最优性原理
-
动态规划函数：
{ d ( k , { } ) = c k i d ( i , V ′ ) = m i n { c i k + d ( k , V ′ − { k } ) } k ∈ V ′ \begin{cases} d(k,\{\})=c_{ki} \\ d(i,V')=min\{c_{ik}+d(k,V'-\{k\})\} & k \in V' \end{cases} {d(k,{})=ckid(i,V′)=min{cik+d(k,V′−{k})}k∈V′ -
时间复杂度 O(2^n)
-
-
最长公共子序列：
-
最优性原理证明：两个序列X，Y有最长公共子序列Z，Z包含XY前缀序列的最长公共子序列，因此满足最优性原理
-
动态规划函数：
L ( i , j ) = { L ( i − 1 , j − 1 ) + 1 x i = y j , i ≥ 1 , j ≥ 1 m a x { L ( i − 1 , j ) , L ( i , j − 1 ) } x i ≠ y j , i ≥ 1 , j ≥ 1 L(i,j)= \begin{cases} L(i-1,j-1)+1 & x_i = y_j,i \geq 1, j \geq 1 \\ max\{L(i-1,j),L(i,j-1)\} & x_i \neq y_j,i \geq 1, j \geq 1 \end{cases} L(i,j)={L(i−1,j−1)+1max{L(i−1,j),L(i,j−1)}xi=yj,i≥1,j≥1xi=yj,i≥1,j≥1 -
代码实现
public class MaxPublicString { static int[][] record; public static int findPubStr(String p, String t) { p = " " + p; t = " " + t; int[][] dp = new int[p.length()][t.length()]; record = new int[p.length()][t.length()]; for (int i = 1; i < p.toCharArray().length; i++) { for (int j = 1; j < t.toCharArray().length; j++) { if (p.charAt(i) == t.charAt(j)) { dp[i][j] = dp[i - 1][j - 1] + 1; record[i][j] = 1; } else if (dp[i - 1][j] > dp[i][j - 1]) { dp[i][j] = dp[i-1][j]; record[i][j] = 3; } else { dp[i][j] = dp[i][j-1]; record[i][j] = 2; } } } return dp[p.length() - 1][t.length() - 1]; } public static String getPubStr(String p) { StringBuilder res = new StringBuilder(); for (int i = record.length - 1; i > 0 ;) { int[] nextRec = record[i]; for (int j = nextRec.length - 1; j > 0 ;) { if (record[i][j] == 1) { res.append(p.charAt(i-1)); i--; j--; } else if (record[i][j] == 2) { j--; } else { i--; } } } return res.reverse().toString(); } }
-
0/1背包：(货币兑换问题差不多）
-
最优性原理：设x1,x2…xn是一个最优解，则x2…xn是一个子问题的最优解，否则存在y1,y1…yn是子问题最优解且比 x1…xn更优导致矛盾，因此满足最优性原理
-
动态规划函数：
V ( i , j ) = { V ( i − 1 , j ) j < w i m a x { V ( i − 1 , j ) , V ( i − 1 , j − w i ) + v i } j ≥ w i V(i,j)= \begin{cases} V(i-1,j) & j < w_i \\ max\{V(i-1,j),V(i-1,j-w_i)+v_i\} & j \geq w_i \end{cases} V(i,j)={V(i−1,j)max{V(i−1,j),V(i−1,j−wi)+vi}j<wij≥wi
-
-
近似串匹配：
-
最优性原理：设样本P在文本T处有最优对应关系，则P的任意子串与T的对应关系也是最优的，因此满足最优性原理
-
动态规划函数：
D ( i , j ) = { m i n { D ( i − 1 , j − 1 ) , D ( i − 1 , j ) , D ( i , j − 1 ) } i > 0 , j > 0 , p i ≠ t j m i n { D ( i − 1 , j − 1 ) + 1 , D ( i − 1 , j ) + 1 , D ( i , j − 1 ) + 1 } i > 0 , j > 0 , p i = t j D(i,j)= \begin{cases} min\{D(i-1,j-1),D(i-1,j),D(i,j-1)\} & i>0,j>0,p_i \neq t_j\\ min\{D(i-1,j-1)+1,D(i-1,j)+1,D(i,j-1)+1\} & i>0,j>0,p_i = t_j \end{cases} D(i,j)={min{D(i−1,j−1),D(i−1,j),D(i,j−1)}min{D(i−1,j−1)+1,D(i−1,j)+1,D(i,j−1)+1}i>0,j>0,pi=tji>0,j>0,pi=tj
-
贪心法
典型问题
-
背包问题
最大价值策略、最小重量策略、最大单位重量策略
-
最小生成树
Prim、Kruskal
-
TSP
每次选择最短的边
-
图着色问题
选择一种颜色 尽可能为更多顶点着色直到完全冲突换下一种颜色，循环取色直到完全着色
-
多机调度问题
最长处理时间作业优先处理，把处理时间最长的任务分配给空闲的机器
回溯法
解空间树
按照对象的访问顺序找到的所有可能解则构成解空间书
设计思想
对解空间树进行深度搜索，并跳过不包含最优解的结点（约束条件）进行剪枝
典型问题
-
哈密顿回路
约束条件为两顶点之间需要存在边、除起点外每个点只能遍历一次
根据点的数量决定解空间树的层级，根据未访问点的数量决定解空间树一层有几种分支
-
八皇后
约束条件：皇后不能同列或者同斜线
根据行数决定解空间的层级，根据列数决定解空间树的每一层有多少种分支
-
0/1背包问题
约束条件：物品重量小于背包容量
解空间树每一层只有两种分支，根据物品数量决定层级
-
批处理调度
约束条件：一个任务在一个机器上只执行一次
解空间树为任务的全排列
分支限界法
-
多段图
-
上界：贪心法每次选择最短的边走
-
限界函数：
l b = ∑ j = 1 i c [ r i ] [ r j + 1 ] + m i n < r r + 1 , v p > ∈ E { c [ r i + 1 ] [ v p ] } + ∑ j = i + 2 k 第j段的最短边 lb=\sum_{j=1}^{i}c[r_i][r_{j+1}]+min_{<r_{r+1},v_p>\in E}\{c[r_{i+1}][v_p]\}+\sum_{j=i+2}^{k}\text{第j段的最短边} lb=j=1∑ic[ri][rj+1]+min<rr+1,vp>∈E{c[ri+1][vp]}+j=i+2∑k第j段的最短边
解释：已求解路径长度+已求解的最后一个点的最短边+所有剩余段内的最短边大于上界的节点可以舍弃，搜索空间树层级与段数有关，每段的分支与段内结点数有关
-
-
0/1背包
-
下界：按单位重量排序后 贪心法取满背包
-
限界函数：
u b = v + ( W − w ) × ( v i + 1 / w i + 1 ) ub=v+(W-w)\times(v_{i+1}/w_{i+1}) ub=v+(W−w)×(vi+1/wi+1)
解释：以获取的价值+剩余背包容量与剩余最大单位价值的乘积超过背包容量的解舍弃，解空间树的根节点为空背包状态，每层只有两种分支代表物品取和不取
-
-
任务分配
-
上界：贪心法从第一个人员开始取剩余任务完成时间最短的分配
-
限界函数：
l b = v + ∑ k = i + 1 n 第k行最小值 lb=v+\sum_{k=i+1}^{n}\text{第k行最小值} lb=v+k=i+1∑n第k行最小值
解释：已花费成本+剩余人员的最短完成时间之和（计算时任务可以重复）超过上界的节点可以舍弃 任务不能重复分配，解空间树根节点已花费成本=0，解空间树层级与人员数量有关，每层的分支数与任务数量有关，每个结点表示任务由某个人完成
-
-
批处理调度
-
上界：按最后一个机器对任务的处理时间按大到小分配得到上界方案
-
限界函数：（假设只有三个机器）
KaTeX parse error: Undefined control sequence: \and at position 128: …(\sum_{j\neq u \̲a̲n̲d̲ ̲j \not\in M}t_{…
解释：设已分配的任务集合为M，数量为k，初始状态下M为空k=0sum1=0,sum2=0sum1 = 第一台机器处理至当前准备分配的任务所需时间
sum2 = 第二台机器处理至当前准备分配的任务之前所需时间，需要综合考量前面机器的运行时间
lb 从前两台的运行时间得出以确定的等待时间 + 第二台处理未完成任务的总时间 + 第三台处理未完成且非当前分配的任务的最短处理时间得出。（在叶子结点处 “未完成且非当前分配” 的任务不存在，但根据书本描述，该任务可以为当前分配的任务。）
大于上界的节点舍弃，解空间树层级与任务数量有关，分支数量与剩余未分配任务数量有关，每个节点表示准备分配的任务
u，表示还没加入M中。
-