分治.贪心.动态规划算法要点复习

分治法

1 分割成独立的子问题 2 递归解决子问题 3 合并求得初始问题的解 动态规划算法

1. 描述最优解的结构特征 2. 定义最优解决方案的递归形式

3. 以自底向上的方式计算最优解决方案的值 4. 从计算信息构造出最优解决方案 贪婪算法步骤 1. 确定问题的优化结构 2. 得到递归解

3. 证明某个最优选择是贪婪选择 4. 贪婪选择将产生唯一一个非空子问题 5. 用递归算法实现贪婪策略 6. 将递归算法转换为迭代算法 贪婪算法设计

1. 通过作出某种贪婪选择，将初始优化问题转换为唯一的一个子问题来求解

2. GREEDY CHOICE（证明贪婪选择）

作出该贪婪选择后，可以保证初始优化问题存在最优解 3. OPTIMAL SUBSTRUCTURE（证明优化基础） 贪婪选择+唯一子问题=最优解 贪婪算法正确性

1. 贪婪选择特性（局部最优导致全局最优）

2. 优化基础的特性（贪婪选择+唯一子问题的最优解⇒初始问题的最优解） 作业选择 • 贪婪选择特性

存在最优解包含贪婪选择，即Sij 在选择最先完成的作业am • 优化基础

If an optimal solution to subproblem Sij includes activity ak ⇒ it must

contain optimal solutions to Sik and Skj

Solution to Sij=(Solution to Sik)∪{ak}∪(Solution to Skj) 动态规划解）

Similarly, am + optimal solution to Smj ⇒ optimal sol. Solution to Sij = {am} ∪ (Solution to Smj) （贪婪选择解）

动态规划与贪婪算法比较 • Dynamic programming –每步选择–选择与子问题解相关

–自底向上，即从规模下的子问题逐步求解规模大的子问题 • Greedy algorithm

– 首先作出贪婪选择– 求解贪婪选择后产生的唯一子问题 – 后续贪婪选择与前面的选择有关，但与子问题的解无关 – 自顶向下，问题规模逐步缩小

动态规划和分治法 •子问题非独立

–子问题求解依赖其子问题的解

–分治法通过递归方式解决性质相同的子问题

–动态规划每次解决一个子问题，并将结果存储在表格中4 • 适合优化问题

–通过适当的选择来获得问题的最优解

–找到具有最优解决方案及其最优值：装配线排程方案以及

该方案的生产时间

–导致最优的解决方案可能不止一个

• （允许负权值边）

– 如果从源顶点s 没有可抵达的负权值回路，返回‘真’）（其余的返回‘假’，无解

– 遍历所有的边|V–1|次，每次对每条边执行一次缩短运算 – 对图进行拓扑排序)(依据拓扑排序对边进行缩短操作 于每一个顶点, 对始于该顶点的每条边进行缩短操作) (DGA中没有负权值回路, 因此存在最短路径) – (不存在负权值边界)

– (S: 集合中顶点的最短路径已经确定) (Q: V – S, 极小优先队列)

• (d[v]) (Q中的值是最短路径的估计)

•重复的从Q 中选择具有最短估计距离的顶点进行处理 The Ford-Fulkerson Method (不断的增大流, 直到达到流的极大值)(通过剩余流和剩余流图实现)

增量算法（An Incremental Algorithm）

Alg.: GREEDY-ACTIVITY-SELECTOR(s, f, n) 1. A ← {a1} 2. i ← 1

3. for m ← 2 to n

4. do if sm ≥ fi ► activity am is compatible with ai 5. then A ← A ∪ {am}

6. i ← m ► ai is most recent addition to A 7. return A 动态规划： 装配线排程 e1 + a1,1 if j = 1

f1[j] = min(f1[j - 1] + a1,j ,f2[j -1] + t2,j-1 + a1,j) if j ≥ 2 矩阵链相乘

m[i,j]=0 if i = j min{m[i,k]+m[k+1,j]+pi-1pkpj} if i

9. q ← m [i , k ] + m [k +1, j ] + pI -1pkpj ; 10. if q

LCS-Length(X , Y ) 1. m ← length[X ]; 2. n ← length[Y ]; 3. for i ← 1 to m 4. c [i , 0] ← 0; 5. for j ← 0 to n 6. c [0, j ] ← 0;

7. for i ← 1 to m 8. for j ← 1 to n 9. if xi = yj

10. c [i , j ] ← c [i -1, j -1]+1 11. b [i , j ] ← “ ⊥” 12. else if c [i -1,j] ≥ c [i , j -1] 13. c [i,j] ← c[i -1, j ] 14. b [i , j ] ← `` ↑ '' 15. else c [i , j ] ← c [i , j -1] 16. b [i , j ] ← “ ← “ 17. return c and b