第三章-2算法

设5n和]10,2,10,1,5,10[p，求矩阵的最优计算次序。练习解：20010210]5][4[543pppm4]5][4[s202101]4][3[432pppm3]4][3[s40}40,300min{1021020]5][5[]4][3[101012000]5][4[]3][3[min]5][3[542532pppmmpppmmm4]5][3[s501015]3][2[321pppm2]3][2[s30}150,30min{2105050]4][4[]3][2[215200]4][3[]2][2[min]4][2[431421pppmmpppmmm2]4][2[s90}130,350,90min{]5][5[]4][2[]5][4[]3][2[]5][3[]2][2[min]5][2[541531521pppmmpppmmpppmmm2]5][2[s501510]2][1[210pppm1]2][1[s150}150,550min{]3][3[]2][1[]3][2[]1][1[min]3][1[320310pppmmpppmmm2]3][1[s90}350,90,130min{]4][4[]3][1[]4][3[]2][1[]4][2[]1][1[min]4][1[430420410pppmmpppmmpppmmm2]4][1[s190}290,1350,190,590min{]5][5[]4][1[]5][4[]3][1[]5][3[]2][1[]5][2[]1][1[min]5][1[540530520510pppmmpppmmpppmmpppmmm2]5][1[s123450000020020505040309015090190m[i][j]1234500000123442222212345s[i][j]12345A1A2A3A4A5()()()用动态规划法解矩阵链乘问题。已知：n=5，矩阵的维数为)25,35,10,50,30,20(),,,,,(543210ppppppp作业1)求m[i,j]2)最少乘法次数?3)最优加括号方式?((A1(A2A3))(A4A5))347500300002100028000347500150002550031250017500212500875001234512345jm§3.2动态规划算法的基本要素基本要素：1)最优子结构性质2)子问题重叠性质最优子结构当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。nAAA21nkkkAAAAAA2121假设由最优解导出的其子问题的解不是最优的;构造出比原问题最优解更好的解；矛盾n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)子问题重叠每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。1:412341:12:41:23:42:23:42:34:41:34:41:12:23:34:41:12:31:23:33:34:42:23:31:12:22:23:3备忘录方法与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。与动态规划算法一样，备忘录方法耗时)(3nO。疑问☺什么时候用动态规划方法？当所有子问题都至少要解一次时，用动态规划算法。什么时候用备忘录方法？当子问题空间的部分子问题不必求解时，用备忘录方法较为有利。练习：如图：从0A点要铺设一条管道到6A点，中间必须经过5个中间站。第一站可以在1A、1B两地中任选一个，类似地，第二、三、四、五站可供选择的地点分别是：},,,{2222DCBA，},,{333CBA，},,{444CBA，},{55BA。连接两地间管道的距离（或造价）用连线上的数字表示，要求选一条从0A到6A的铺管线路，使总距离最短（或总造价最小）。0A1A2A3A4A6A1B2B3B2C2D4C5B5A4B3C5133836234281876334356365图153262思路1：穷举搜索法从0A到6A共有2×3×2×2×2×l＝48种不同路径。通过48×5＝240次加法，47次比较，可求出从0A到6A的最短路径。思路2：动态规划假设6510ASSA是从0A到6A的最短路径，若存在)5,,1(6iAGi，其路径长度比6ASi更短，则路径610AGSAi比6510ASSA更短，矛盾。具有最优子结构性质令]][[yxf表示从x到y的最短路径，1)6k65654]][[AAAAf65653]][[BBABf5k2)7}35,43min{]][[),(]][[),(min]][[6554655464ABfBAdAAfAAdAAf654AAA5}32,45min{]][[),(]][[),(min]][[6554655464ABfBBdAAfABdABf654ABB9}36,46min{]][[),(]][[),(min]][[6554655464ABfBCdAAfACdACf654ABC4k3)7}52,72min{]][[),(]][[),(min]][[6443644363ABfBAdAAfAAdAAf6543ABBA6}92,51min{]][[),(]][[),(min]][[6443644363ACfCBdABfBBdABf6543ABBB8}93,53min{]][[),(]][[),(min]][[6443644363ACfCCdABfBCdACf6543ABBC3k4)13}68,76min{]][[),(]][[),(min]][[6332633262ABfBAdAAfAAdAAf65432ABBAA10}65,73min{]][[),(]][[),(min]][[6332633262ABfBBdAAfABdABf65432ABBAB9}63,83min{]][[),(]][[),(min]][[6332633262ABfBCdACfCCdACf65432ABBBC12}68,84min{]][[),(]][[),(min]][[6332633262ABfBDdACfCDdADf65432ABBCD2k5)654321ABBABA16}136,97,108min{]][[),(]][[),(]][[),(min]][[62216221622161ADfDBdACfCBdABfBBdABf654321ABBBCB13}96,103,131min{]][[),(]][[),(]][[),(min]][[62216221622161ACfCAdABfBAdAAfAAdAAf1k6)18}168,135min{]][[),(]][[),(min]][[6110611060ABfBAdAAfAAdAAf6543210ABBABAA运算次数：15次比较，28次加法。而且还得到其它各点到A6的最短路径和最短距离。0A1A3A6A2B5B4B533232§3.3最长公共子序列给定序列},,,{21mxxxX和},,,{21kzzzZ，若存在一个严格递增的下标序列},,,{21kiii，使得对所有),,2,1(kjj，均有ijjxz，则称序列Z是序列X的子序列。例1.给定序列X=A,B,C,B,D,A,B和Z=B,C,D,B。下标序列为2,3,5,7解：Z最长公共子序列子序列：BCDBABCBDAB子序列Z是序列X中删去若干元素后得到的序列。最长公共子序列例1.给定序列X=A,B,C,B,D,A,B和Z=B,C,D,B。Z给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。公共子序列：例2.序列X=A,B,C,B,D,A,B，Y={B,D,C,A,B,A},Z1={B,C,A}，Z2=B,C,B,A。最长公共子序列ABCBDABBDCABAZ1Z1是X和Y的一个公共子序列例2.序列X=A,B,C,B,D,A,B，Y={B,D,C,A,B,A},Z1={B,C,A}，Z2=B,C,B,A。Z2是X和Y的一个最长公共子序列Z2是X和Y的一个公共子序列ABCBDABBDCBA最长公共子序列AZ2问题给定两个序列},,,{21mxxxX和},,,{21nyyyY，要求找出X和Y的一个最长公共子序列。思路一：穷举搜索法穷举搜索法需要指数时间。思路二：动态规划法设序列},,,{21mxxxX和},,,{21nyyyY的最长公共子序列为},,,{21kzzzZ，则则1kZ是1mX和1nY的最长公共子序列；Z是1mX和Y的最长公共子序列nmyx1)nmkyxzmkxznkyzZ是mX和1nY的最长公共子序列nmyx2)分析最优解的结构证明：(1)反证法mkxz若},,,,{21mkxzzz，则是X和Y的长度为(k+1)的公共子序列矛盾1kZ1nY1mX是和长度为(k-1)公共子序列1nY1mX和有长度大于(k-1)公共子序列W若},{mxW是X和Y的长度大于k的公共子序列矛盾分析最优解的结构(2)若1mX和Y有长度大于k的公共子序列W，则W也是X和Y的长度大于k的公共子序列。矛盾最长公共子序列问题具有最优子结构性质。子问题的递归结构用]][[jic记录序列iX和jY的最长公共子序列的长度。由最优子结构性质建立递归关系如下：]}1][[],][1[max{;0,01]1][1[0,00]][[jicjicyxjijicjijicji构造最长公共子序列首先从]][[nmb开始，依其值在数组b中搜索，1]][[jib2]][[jib3]][[jib练习给定两个序列为X=A,B,C,B,D,A,B和Y=B,D,C,A,B,A，求最长公共子序列？001122334455667000000000000001)1i1j0]}0][1[],1][0[max{]1][1[ccc2]1][1[b2j0]}1][1[],2][0[max{]2][1[ccc2]2][1[b3j0]}2][1[],3][0[max{]3][1[ccc2]3][1[b4j11]3][0[]4][1[cc1]4][1[b5j1}1,0max{]}4][1[],5][0[max{]5][1[ccc3]5][1[b6j11]5][0[]6][1[cc1]6][1[b}{1AX}{1BY},{2DBY},,{3CDBY},,,{4ACDBY},,,,{5BACDBY0011223344556670000000000000000112233445566700000000000000000111111122112222112233122233122334122344222131133213221322122213212222222121122212BCBA练习：序列},,,,,,,,{},,,,,,{bbdbabb