数据结构与算法动态规划课件.ppt

1、求解算法求解算法求解算法求解算法求解算法求解算法：求解算法施加的状态是变化的。求解算法施加的状态是变化的。当前状态只与直接前趋有关，对直接当前状态只与直接前趋有关，对直接 前趋施加求解算法，前趋施加求解算法，成为当前状态。成为当前状态。(Principle of Optimality):特定问题该原则不一定满足（罕见），因此，特定问题该原则不一定满足（罕见），因此，有必要检查该原则的适用性。有必要检查该原则的适用性。1.分阶段计算。对最优化问题，各阶段满足最优性原则。分阶段计算。对最优化问题，各阶段满足最优性原则。2.一般用一般用（规模减小），（规模减小），（规模增加）。（规模增加）。计算过程

2、：一阶段一阶段地向前推进，直到最终状态。计算过程：一阶段一阶段地向前推进，直到最终状态。5 级级4 级级3 级级2 级级1级级18 27 39 3267 46 5578 6791131112740141615824671312111378137816214187816131378781613781613781613781613PQPQPQPQPQPQF(5)F(4)F(3)F(2)F(3)F(1)F(2)F(1)F(0)F(0)F(1)F(2)F(1)F(0)F(1)计算计算 F(5)要重复计算要重复计算F(2)、F(3)，降低了，降低了时间效率时间效率 交叠子问题重复计算。交叠子问题重复计算

3、。8423109 6710384965484（区别于完全最短路径问题）（区别于完全最短路径问题）源点源点收点收点010000010000101234123410A 111111000111234123411101R 1111111100001111112342341234nR (0)010000010000101213124043R (1)01000010000110123401R(2)01000010000111112341R(3)01010001000011111234R(4)11100001111111121134R(0)()(1()(1)()1()(1)(1)/k(1(/.1.)/1/

4、)kkkkn nknRAinjnRifortodofortodofortoWarsheljRijRi kRkdoorandl AnnknretARrn Ruj 输输入入邻邻接接矩矩阵阵段段 循循环环行行循循环环列列循循环环返返回回传传递递闭闭包包。上上标标便便于于理理解解和和1为为1，和和0为为0行列看作比特串行列看作比特串2671332700016123414023W 10342567716169000012341234D 带权有向图带权有向图 权重矩阵权重矩阵 (0)03207016012341234D (1)032071230 1659 04D (2)9003205716901234D

5、26713(3)0320591046417019012366D(4)7010342056701616901234D()(1)/k/(1)/(1.,1.)1m ,i/nfortodofortodoDWinjnD ijFloyd WnnfortodoretWWkD ijD ikD kjDunrn 输输入入权权重重矩矩阵阵也也可可直直接接改改写写，此此步步省省略略段段 循循环环行行循循环环列列循循环环返返回回距距离离矩矩阵阵21()1nnc nCn 比较比较1次次比较比较2次次比较比较3次次比较比较4次次比较比较1次次比较比较2次次比较比较3次次 0.11+0.22+0.43+0.34 =0.21+

6、0.12+0.42+0.33 =一定存在平均比较次数最少的一定存在平均比较次数最少的 BSTka,.,ijaajiT1kiT 1jkT 1,.,naa1,.,npp1nT1,.,ikaa 最优最优BST1,.,kjaa 最优最优BST1111,.,.,.,.,.,ikkjjikkkkpppapaapaa 根根左左子子树树右右子子树树11,11111()()(,m)1inmi1(1)njkllrrl ir kjkllrrl irkjkkli kji kjC i krir kklp L ap L apCL ap L appjpip 整整树树平平均均左左子子树树（成成功功查查找找）右右子子树树（成成

7、功功查查找找）左左子子树树平平均均根根全全部部节节点点概概率率和和右右子子树树 1,11,minC kji kjjss iC i kCpjCki j 平平均均1i j n递推计算式递推计算式 1,11,miniijskijjsnC i jC i kjpC k 2121,12211,2min0.1:1,02,200.20.40.230.5:1,13,20.4100.3ssijksskCCpCCkpC 最最优优根根31311,331311:1,00.00.2,30.81,371.52:1,min1,20.4113,30.10.40.71.2:4,30.0013.7ssssijsskkCpkCCpC

8、CCkCp 最最优优根根k 根的下标。根的下标。的计算在下页的计算在下页3232,23322:2,13,300.340.61.0:2,24,302,3mi.200.n860.sisksjskkCCpCCpC 最最优优根根 1,11,miniijskijjsnC i jC i kjpC k 计算公式：计算公式：41414114,41411:1,00.01.022,42,43,43,41,:1,10.11.03:4,40.31.01.74:5,40.01.02.4min1,210.41,31.1ssssijsssksCCCCkCpkCpkCpkCpCCC 434344,33:3,24,40.01.

9、00.30.74:3,35,40.40.00.73,4min1.13ssijsksCCpkCCpCk 最最优优根根 1,11,miniijskijjsnC i jC i kjpC k 计算公式：计算公式：42422,422442:2,10.00.91.9:2,23,41.02,44,40.20.30.94:5,40min1.42,30.8.300.91.7ssssijsskkCpCCpkkCCCCp 最最优优根根414141,4141142,41.43,41.1:1,00.01.02.42:1,10.11.02.1:4,40.31.04:5,40.01.02.01,4min1,20.41.71

10、,31.131ssssijkssssCkCpkCCCCCpCppkkC 最最优优根根各段计算：如各段计算：如 C2,4=箭头表示一对箭头表示一对元素，将元素，将与与(p2+p3+p4)相加：相加：C2,4=0.5+(0.2+0.4+0.3)=1.4，如此计算，如此计算 Ci,j,1ijn=4实际计算时实际计算时 i、j 的范围的范围 i:1n-1，j:2n，红色数字表示。，红色数字表示。根表知，根表知，4 个键的最优根下标为个键的最优根下标为 3 即即 a3，左子树为，左子树为 a1 a2右子树为右子树为 a4，左子树的结构是什么？，左子树的结构是什么？再看根表，再看根表，a1 a2 构成的最

11、优子树根是构成的最优子树根是a2，因为，因为a1 a2，所以，所以，1 键是键是 2 键的左节点。键的左节点。,10,/11/(1.,1.,1.1,0.,1.1,0/1,0(11)(1.)2.)OptiC imalBST AiC i iP iR i iiC nndnindjidmn Pn Cnn Rinvafortodofortonnnndo C C对对角角元元C C次次对对角角元元R R次次对对角角元元C C对对角角元元最最后后一一个个元元素素加加入入节节点点序序列列范范围围：范范围围：()(),11,(1)(1,11,/,lkijminC i kC kjminvalkminkR i jkm

12、ifortodoiffortovalC i kC kjsumP isijsumsumPdnC i jminvalsumoreturnskCn 当当前前根根k k的的最最小小平平均均比比较较次次数数找找最最优优根根基基本本操操作作记记录录最最优优根根，此此句句教教材材上上错错为为概概率率和和)RRi,j可以限定在可以限定在Ri,j-1和和Ri+1,j之间，效率降至之间，效率降至平方型。平方型。11max(,)nniiiiiiwWxVvnxW物品数物品数承重量承重量说明：可按行（或列）填写此表。说明：可按行（或列）填写此表。按行或列填表计算的结果按行或列填表计算的结果444(3,5)(4,5)(3

13、,5)(3,5)(3,3)321522maxmaxmax37VVvVwVvV (1,)max(,)(1,)iiV ijVvjwi jV i 例如：例如：44244(3,5maxmax(3,5)32(4,537)1522wwVwVVv 放放入入未未放放入入33333(3,3)(2,322maxmax)2002(2,03)wwVvVwV 放放入入入入未未放放22142(1,3maxmax(1,3)12(2,322)1012wwVwVVv 放放入入未未放放入入11112(0,2)0(1,2)(0,maxmax2)12012wwVVvVw 放放未未放放入入入入最优解有最优解有w4最优解无最优解无w3最优解有最优解有w2最优解有最优解有w1最最 优优 解解 回回 溯计算溯计算本例只计算本例只计算20个有效值中的个有效值中的10个（背景涂色的数字）。个（背景涂色的数字）。带记忆功能算法的效率与自底带记忆功能算法的效率与自底向上效率类型一样，提高效率向上效率类型一样，提高效率不超过一个常数因子。不超过一个常数因子。0100000100010000021860320420330