南京大学：《计算机问题求解》课程教学资源（PPT课件讲稿）动态规划

计算机问题求解一论题3-1 动态规划 2018年09月11日

计算机问题求解 – 论题3-1 - 动态规划 2018年09月11日

问题2 相比较快速排序的分治法递 归，为什么上面的例子采用 递归代价高昂？ QUICKSORT(A,p,r) 1 if p<r 2 g =PARTITION(A,p.r) 3 QUICKSORT(A,p.q-1) 4 QUICKSORT(A,q+1,r)

Rod Cutting Problem Therod-inrob is the following.Given a rod of lengthn inches and a table of prices pifori=1,2...determine the maximum revenueobtain- able byutin up the rod and selling the pieces. 一个样本输 入及其解： length i12345678910 price pi 158910171720 2430 =1 from solution 1 =1 (no cuts), r6 =17 from solution 6=6 (no cuts), r2=5 from solution 2 =2 (no cuts), 7=18 from solution 7 =1+6 or 7=2+2+3, r3 =8 from solution 3 =3 (no cuts), rs 22 from solution 8=2+6, r4 10 from solution 4=2+2, r9 25 from solution 9=3+6, rs 13 from solution 5=2+3, rio =30 from solution 10=10 (no cuts)

Rod Cutting Problem 一个样本输 入及其解： r7 :

问题1： 这个问题的解空间有多 大？为什么？

间题2： 如何搜素？压缩？解空间 似乎任何一个可行解， 都可能是最优解 和我们之前看到的“猜年龄”、“求直径”似乎都不一样

似乎任何一个可行解， 都可能是最优解 和我们之前看到的“猜年龄”、“求直径”似乎都不一样

间题2： 如何搜索？压缩？解空间 递归思维！

递归思维！

问题3： 如何递归？ 7 任何最优解中，我们总是要切第一刀的 In:

任何最优解中，我们总是要切第一刀的 r7 : rn : i

第一刀切下去之后： In 我们能够写出下面的公式吗？ rn=ri+rn-i 这个问题具有“最佳子结构”性质

rn : i rn =ri+rn-i 第一刀切下去之后： 我们能够写出下面的公式吗？ 这个问题具有“最佳子结构”性质

最优子结构： In max (Pn:r1 In-1,r2 +In-2,...,In-1+r1) 间题48 你能情助以上的式子解察一下什么是最优子 结构Optimal Substructure? 为什么榄。最优子结构特性是我们可以用递 归方法求解这个问惠的基础？

最优子结构：

递归的解法：扫描所有可能的割法 In max (Pn;r1 In-1,r2 +In-2,...,In-1+r1) max(P十Tn-i I<i≤月 问题5： CUT-ROD(p.n) 左边的两个式子 1 fn==0 2 return O 有什么区别？ 3 q.=-0∞ 4 for i Iton 5 q max(g.pli]CUT-ROD(p.n-i)) 6 retur 4

递归的解法：扫描所有可能的割法