分治法
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 < j
Matrix-Chain-Order(p)
1. n ←length[p]-1;
2. for i ←1 to n
3. m[i, i] ←0;
4. for l ←2 to n
5. for i ←1 to n –l +1
6. j ←i + l -1;
7. m[i, j] ←∞;
8. for k ←i to j -1
9. q ←m[i, k] + m[k+1, j] + pI-1pkpj;
10. if q < m[i, j]
11. m[i, j] ←q;
12. s[i, j] ←k;
13. return m and s
最长共同子序列
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。