《算法设计与分析》第07章v2.pptVIP

算法设计与分析 第2部分 算法设计策略 第7章 动态规划法 7.1 一般方法和基本要素 7.1.3? 多段图问题 多段图问题的特性 最优子结构特性 （s,v2,v3,…,vk-1,t) 与 (v2,v3,…,vk-1,t) 定义cost(i,j)， 1?ik cost(k,t)=0 cost(i,j) = min { c(j,p) + cost(i+1,p) } 重叠子问题特性 1 — k段图的自后向前递推求解 递推关系式 cost(5,t)=0 cost(4,8)=?，cost(4,9)，cost(4,10) cost (3,5)=?， cost(3,6)， cost(3,7) 课堂练习 用分治法思想求解K段图问题 与上述动态规划法进行比较 2 — k段图的自前向后递推求解 递推关系式 cost(1,s)=0 cost(i,j)=? 动态规划法的实质也是将较大问题分解为较小的同类子问题，这一点上它与分治法和贪心法类似。但动态规划法有自己的特点。分治法的子问题相互独立，相同的子问题被重复计算，动态规划法解决这种子问题重叠现象。贪心法要求针对问题设计最优量度标准，但这在很多情况下并不容易。动态规划法利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解，动态规划则可以处理不具备贪心准则的问题。 7.1.1 一般方法 7.1.2 基本要素 7.1.4 资源分配问题 7.1.4 资源分配问题 向后递推的动态规划算法？ 7.1.5 关键路径问题（略） 工程安排 最短工期 关键路径 关键活动 在关键路径上的活动 注意结点的编号 7.1.5 关键路径问题 最优子结构特性？ 子问题重叠？ 7.2 每对结点间的最短路径 单源最短路径问题 贪心法求解 6.6.3 迪杰斯特拉算法 7.2.1? ?结点对间最短路径问题描述 7.2.2 动态规划法求解 7.2.3?弗洛伊德算法 7.2.4 算法正确性 结点对间最短路径问题 弗洛伊德算法 N次迪杰斯特拉算法 7.3 矩阵连乘 7.3.1? 问题描述 7.3.2 动态规划法求解 求解过程 为避免重复计算，自底向上求解 m[i][j] m[i][k], k=i,i+1,…j-1 m[k+1][j], k=i+1,…j-1 7.3.3?矩阵连乘算法 7.3.4? 备忘录方法 7.5 最优二叉有哪些信誉好的足球投注网站树 7.5.1 问题描述 二叉有哪些信誉好的足球投注网站树的代价 二叉有哪些信誉好的足球投注网站树平均有哪些信誉好的足球投注网站时间 {a1,…,an, E0,…,En} cost(T)= 递推关系 cost(T)= cost(L)+cost(R)+p1+…+pn +q0+q1+…+qn 7.5.2?动态规划法求解 7.5.3 最优二叉有哪些信誉好的足球投注网站树算法 7.6 0/1背包 7.6.1? 问题描述 7.6.2? 动态规划法求解 7.6.3? 0/1背包算法框架 7.6.5 性能分析 7.7 流水作业调度 7.7.1 问题描述 7.7.2 动态规划法求解 最优调度求解方案 可以设计下列作业排列方法。这样做能得到最优调度方案 (1)如果min{a0,a1,…,an?1, b0,b1,…,bn?1}是ai，则ai应是最优排列的第一个作业； (2)如果min{a0, a1, …, an-1, b0, b1,…, bn?1}是bj，则bj应是最优排列的最后一个作业； (3) 继续（1）和（2）的做法，直到完成所有作业的排列。 7.7.3 Johnson算法 动态规划法 小结 求最优化问题 最优子结构原理 递推关系 分析子问题的重叠性 自底向上计算（最优解值） 构造最优解 与分治法、贪心法比较 备忘录方法 例7－7 设n＝4且（a1,a2,a3,a4）=(Mon,Thu,Tue,Wed)。又设p(1:4)=(3,3,1,1)和q(0:4)＝(2,3,1,1,1)。这里p和q都已乘了16。 【程序7－7】构造最优二叉有哪些信誉好的足球投注网站树 int Find(int i, int j, int **r, float**c) //找出I,j之间使代价最小的根 { float min=INFTY; int k; for (int m=i+1;m=j;m++) if ((c[i][m-1]+c[m][j])min) { min=c[i][m-1]+c[m][j];k=m; } return k; } void CreateOBST(float* p, float* q,