《算法与设计：动态规划法》由会员分享，可在线阅读，更多相关《算法与设计：动态规划法（78页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析算法设计与分析广东白云学院广东白云学院广东白云学院广东白云学院 计算机科学系计算机科学系计算机科学系计算机科学系2010-20112010-2011学年学年学年学年 第第第第2 2学期学期学期学期第第第第3 3章章章章 动态规划法动态规划法动态规划法动态规划法本本 章章 目目 录录返回返回返回返回3.1概概述述3.2图问题中的动态规划法图问题中的动态规划法3.3组合问题中的动态规划法组合问题中的动态规划法3.4查找问题中的动态规划法查找问题中的动态规划法3.1 概概 述述 3.1.2最优化问题最优化问题3.1.3最优性原理最优性原理3.1.4动态规划法的设计思想动态规划法的设计思
2、想返回返回返回返回3.1.1动态规划法简介动态规划法简介n动态规划法与分治法类似，其基本思想也是将待动态规划法与分治法类似，其基本思想也是将待动态规划法与分治法类似，其基本思想也是将待动态规划法与分治法类似，其基本思想也是将待求解的问题分解成若干个子问题，先求解子问题，求解的问题分解成若干个子问题，先求解子问题，求解的问题分解成若干个子问题，先求解子问题，求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。然后从这些子问题的解得到原问题的解。然后从这些子问题的解得到原问题的解。然后从这些子问题的解得到原问题的解。3.1.1 3.1.1 动态规划法简介动态规划法简介n
3、与分治法不同的是，适合用动态规划求解的问题，与分治法不同的是，适合用动态规划求解的问题，与分治法不同的是，适合用动态规划求解的问题，与分治法不同的是，适合用动态规划求解的问题，经分解得到的子问题往往不是互相独立的。若用经分解得到的子问题往往不是互相独立的。若用经分解得到的子问题往往不是互相独立的。若用经分解得到的子问题往往不是互相独立的。若用分治法解这类问题，则分解得到的子问题太多，分治法解这类问题，则分解得到的子问题太多，分治法解这类问题，则分解得到的子问题太多，分治法解这类问题，则分解得到的子问题太多，以致于最后解决原问题需要耗费指数时间。在用以致于最后解决原问题需要耗费指数时间。在用以致
4、于最后解决原问题需要耗费指数时间。在用以致于最后解决原问题需要耗费指数时间。在用分治求解时，有些子问题被重复计算了多次。如分治求解时，有些子问题被重复计算了多次。如分治求解时，有些子问题被重复计算了多次。如分治求解时，有些子问题被重复计算了多次。如果能够果能够果能够果能够保存已解决的子问题的答案。在需要的时保存已解决的子问题的答案。在需要的时保存已解决的子问题的答案。在需要的时保存已解决的子问题的答案。在需要的时候再找出已求的答案，就可以避免大量的重复计候再找出已求的答案，就可以避免大量的重复计候再找出已求的答案，就可以避免大量的重复计候再找出已求的答案，就可以避免大量的重复计算算算算，从而简
5、化了算法。为了达到这个目的，可以，从而简化了算法。为了达到这个目的，可以，从而简化了算法。为了达到这个目的，可以，从而简化了算法。为了达到这个目的，可以用一个表来记录所有已解决的子问题答案。不管用一个表来记录所有已解决的子问题答案。不管用一个表来记录所有已解决的子问题答案。不管用一个表来记录所有已解决的子问题答案。不管该子问题以后是否被用到，只要他被计算过，就该子问题以后是否被用到，只要他被计算过，就该子问题以后是否被用到，只要他被计算过，就该子问题以后是否被用到，只要他被计算过，就将其结果填入表中。这就是动态规划法的基本思将其结果填入表中。这就是动态规划法的基本思将其结果填入表中。这就是动态
6、规划法的基本思将其结果填入表中。这就是动态规划法的基本思想。想。想。想。 图图图图中中中中每每每每个个个个顶顶顶顶点点点点代代代代表表表表一一一一个个个个城城城城市市市市，两两两两个个个个城城城城市市市市间间间间的的的的连连连连线线线线代代代代表表表表道道道道路路路路，连连连连线线线线上上上上的的的的数数数数值值值值代代代代表表表表道道道道路路路路的的的的长长长长度度度度。现现现现在在在在，想想想想从从从从城城城城市市市市A A A A到到到到达达达达城城城城市市市市E E E E，怎样走路程最短，最短路程的长度是多少怎样走路程最短，最短路程的长度是多少怎样走路程最短，最短路程的长度是多少怎样
7、走路程最短，最短路程的长度是多少? ? ? ? 多阶段决策过程最优化问题多阶段决策过程最优化问题多阶段决策过程最优化问题多阶段决策过程最优化问题n n最短路径的特性最短路径的特性最短路径的特性最短路径的特性: :最短路径的第最短路径的第最短路径的第最短路径的第k k阶段通过阶段通过阶段通过阶段通过X Xk k 点，则点，则点，则点，则这一最短路径在由这一最短路径在由这一最短路径在由这一最短路径在由X Xk k 出发到终点的那一部分路径，出发到终点的那一部分路径，出发到终点的那一部分路径，出发到终点的那一部分路径，对于起始点为对于起始点为对于起始点为对于起始点为X Xk k 到终点的所有可能的路
8、径来说必定到终点的所有可能的路径来说必定到终点的所有可能的路径来说必定到终点的所有可能的路径来说必定也是路径最短的也是路径最短的也是路径最短的也是路径最短的. .n n利用倒推方法求解利用倒推方法求解利用倒推方法求解利用倒推方法求解A A到到到到E E的最短距离。把从的最短距离。把从的最短距离。把从的最短距离。把从A A到到到到E E的的的的全过程分成四个阶段，用全过程分成四个阶段，用全过程分成四个阶段，用全过程分成四个阶段，用k k表示阶段变量，第表示阶段变量，第表示阶段变量，第表示阶段变量，第1 1阶段阶段阶段阶段有一个初始状态有一个初始状态有一个初始状态有一个初始状态A A，两条可供选择
9、的支路，两条可供选择的支路，两条可供选择的支路，两条可供选择的支路ABABl l、ABAB2 2；第；第；第；第2 2阶段有两个初始状态阶段有两个初始状态阶段有两个初始状态阶段有两个初始状态B B1 1、B B2 2，B B1 1有三条可供选有三条可供选有三条可供选有三条可供选择的支路，择的支路，择的支路，择的支路，B B2 2有两条可供选择的支路有两条可供选择的支路有两条可供选择的支路有两条可供选择的支路。用。用。用。用dkdk( (x xk k，x xk+1k+1) )表示在第表示在第表示在第表示在第k k阶段由初始状态阶段由初始状态阶段由初始状态阶段由初始状态x xk k 到下阶段的到下
10、阶段的到下阶段的到下阶段的初始状态初始状态初始状态初始状态x xk+1k+1的路径距离，的路径距离，的路径距离，的路径距离，Fk(xFk(xk k) )表示从第表示从第表示从第表示从第k k阶段的阶段的阶段的阶段的x xk k 到终点到终点到终点到终点E E的最短距离。的最短距离。的最短距离。的最短距离。 求从求从求从求从A A到到到到E E的最短路问题的最短路问题的最短路问题的最短路问题Fk(AFk(A) ) ，可以转化为两个性质完全相同，可以转化为两个性质完全相同，可以转化为两个性质完全相同，可以转化为两个性质完全相同，但规模较小的问题，即分别从但规模较小的问题，即分别从但规模较小的问题，
11、即分别从但规模较小的问题，即分别从B1B1、B2B2到到到到E E的最短路问题的最短路问题的最短路问题的最短路问题Fk(B1)Fk(B1)和和和和Fk(B2)Fk(B2)，这时有：，这时有：，这时有：，这时有： Fk(AFk(A)=mind1(A,B1)+ Fk(B1),d1(A,B2)+ Fk(B2)=mind1(A,B1)+ Fk(B1),d1(A,B2)+ Fk(B2)同样，同样，同样，同样， 计算计算计算计算Fk(B1) Fk(B1) ，又可以转化为性质完全相同，但规模更小的，又可以转化为性质完全相同，但规模更小的，又可以转化为性质完全相同，但规模更小的，又可以转化为性质完全相同，但规
12、模更小的问题，即分别从问题，即分别从问题，即分别从问题，即分别从C1C1、C2C2、C3C3到到到到E E的最短路问题的最短路问题的最短路问题的最短路问题Fk(C1)Fk(C1)、 Fk(C2)Fk(C2)和和和和 Fk(C3)Fk(C3)，最后，归结为，最后，归结为，最后，归结为，最后，归结为Fk(D1)Fk(D1)、 Fk(D2)Fk(D2)两个子问题。两个子问题。两个子问题。两个子问题。由于由于由于由于Fk(D1)Fk(D1)、 Fk(D2)Fk(D2)是已知的，因此，可以从这两个值开始，是已知的，因此，可以从这两个值开始，是已知的，因此，可以从这两个值开始，是已知的，因此，可以从这两个
13、值开始，逆向递归计算出逆向递归计算出逆向递归计算出逆向递归计算出Fk(AFk(A) )的值。最终，可以得到从的值。最终，可以得到从的值。最终，可以得到从的值。最终，可以得到从A A到到到到E E的最短路径。的最短路径。的最短路径。的最短路径。 动态规划法就是根据动态规划法就是根据动态规划法就是根据动态规划法就是根据最优性原理，以最优性原理，以最优性原理，以最优性原理，以自底向上自底向上自底向上自底向上的方式从子问题的方式从子问题的方式从子问题的方式从子问题的最优解逐步构造出整个问题的最优解。（的最优解逐步构造出整个问题的最优解。（的最优解逐步构造出整个问题的最优解。（的最优解逐步构造出整个问题
14、的最优解。（逆向递归的方法逆向递归的方法逆向递归的方法逆向递归的方法）S1S1S1S1：K=4K=4K=4K=4，有：，有：，有：，有： F4(D1)=3F4(D1)=3F4(D1)=3F4(D1)=3，F4(D2)=4F4(D2)=4F4(D2)=4F4(D2)=4，F4(D3)=3F4(D3)=3F4(D3)=3F4(D3)=3S2: K=3S2: K=3S2: K=3S2: K=3，有：，有：，有：，有： F3(C1)=mind3(C1,D1)+F4(D1),d3(C1,D2)+F4(D2)F3(C1)=mind3(C1,D1)+F4(D1),d3(C1,D2)+F4(D2)F3(C1)
15、=mind3(C1,D1)+F4(D1),d3(C1,D2)+F4(D2)F3(C1)=mind3(C1,D1)+F4(D1),d3(C1,D2)+F4(D2) =min8,10=8 =min8,10=8 =min8,10=8 =min8,10=8 F3(C2)=d3(C2,D1)+F4(D1)=5+3=8 F3(C2)=d3(C2,D1)+F4(D1)=5+3=8 F3(C2)=d3(C2,D1)+F4(D1)=5+3=8 F3(C2)=d3(C2,D1)+F4(D1)=5+3=8 F3(C3)=d3(C3,D3)+F4(D3)=8+3=11 F3(C3)=d3(C3,D3)+F4(D3)=
16、8+3=11 F3(C3)=d3(C3,D3)+F4(D3)=8+3=11 F3(C3)=d3(C3,D3)+F4(D3)=8+3=11 F3(C4)=d3(C4,D3)+F4(D3)=3+3=6 F3(C4)=d3(C4,D3)+F4(D3)=3+3=6 F3(C4)=d3(C4,D3)+F4(D3)=3+3=6 F3(C4)=d3(C4,D3)+F4(D3)=3+3=6S2: K=2S2: K=2S2: K=2S2: K=2，有：，有：，有：，有： F2(B1)=mind2(B1,C1)+F3(C1),d2(B1,C2)+F3(C2),d2(B1,C3)F2(B1)=mind2(B1,C1
17、)+F3(C1),d2(B1,C2)+F3(C2),d2(B1,C3)F2(B1)=mind2(B1,C1)+F3(C1),d2(B1,C2)+F3(C2),d2(B1,C3)F2(B1)=mind2(B1,C1)+F3(C1),d2(B1,C2)+F3(C2),d2(B1,C3) +F3(C3)=min9,14,14=9 +F3(C3)=min9,14,14=9 +F3(C3)=min9,14,14=9 +F3(C3)=min9,14,14=9 F2(B2)=mind2(B2,c2)+F3(C2),d2(B2,C4)+F3(C4) F2(B2)=mind2(B2,c2)+F3(C2),d2(
18、B2,C4)+F3(C4) F2(B2)=mind2(B2,c2)+F3(C2),d2(B2,C4)+F3(C4) F2(B2)=mind2(B2,c2)+F3(C2),d2(B2,C4)+F3(C4) =min16,10=10 =min16,10=10 =min16,10=10 =min16,10=10S4S4S4S4：k=1k=1k=1k=1，有：，有：，有：，有： F1( A)=mind1(A,B1)+F2(B1),d1(A,B2)+F2(B2)F1( A)=mind1(A,B1)+F2(B1),d1(A,B2)+F2(B2)F1( A)=mind1(A,B1)+F2(B1),d1(A,
19、B2)+F2(B2)F1( A)=mind1(A,B1)+F2(B1),d1(A,B2)+F2(B2) =min14,13=13 =min14,13=13 =min14,13=13 =min14,13=13因此由因此由因此由因此由A A到到到到E E的全过程的最短路径为的全过程的最短路径为的全过程的最短路径为的全过程的最短路径为 AB2AB2一一一一C4D3EC4D3E, , , ,最短路程长度为最短路程长度为最短路程长度为最短路程长度为1313。 数塔问题数塔问题数塔问题数塔问题 有形如图所示的一个数塔，从顶部出发，在每一结点可以有形如图所示的一个数塔，从顶部出发，在每一结点可以有形如图所示
20、的一个数塔，从顶部出发，在每一结点可以有形如图所示的一个数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，选择向左走或是向右走，一直走到底层，要求找出一条路径，选择向左走或是向右走，一直走到底层，要求找出一条路径，选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的数值和最大。使路径上的数值和最大。使路径上的数值和最大。使路径上的数值和最大。 算法设计过程如下：算法设计过程如下：算法设计过程如下：算法设计过程如下： 1.1.1.1.阶段划分：阶段划分：阶段划分：阶段划分： 第一步对于第五层的数据，我们做如下决策：第一步对于第五层的数据，我们做如下
21、决策：第一步对于第五层的数据，我们做如下决策：第一步对于第五层的数据，我们做如下决策： 对经过第四层对经过第四层对经过第四层对经过第四层2 2 2 2的路径选择第五层的的路径选择第五层的的路径选择第五层的的路径选择第五层的19191919， 对经过第四层对经过第四层对经过第四层对经过第四层18181818的路径选择第五层的的路径选择第五层的的路径选择第五层的的路径选择第五层的10101010， 对经过第四层对经过第四层对经过第四层对经过第四层9 9 9 9的路径也选择第五层的的路径也选择第五层的的路径也选择第五层的的路径也选择第五层的10101010， 对经过第四层对经过第四层对经过第四层对经
22、过第四层5 5 5 5的路径选择第五层的的路径选择第五层的的路径选择第五层的的路径选择第五层的16161616。 以上的决策结果将五阶数塔问题变为以上的决策结果将五阶数塔问题变为以上的决策结果将五阶数塔问题变为以上的决策结果将五阶数塔问题变为4 4 4 4阶子问题，递推出阶子问题，递推出阶子问题，递推出阶子问题，递推出第四层与第五层的和为第四层与第五层的和为第四层与第五层的和为第四层与第五层的和为: : : : 21(2+19),28(18+10),19(9+10),21(5+16) 21(2+19),28(18+10),19(9+10),21(5+16) 21(2+19),28(18+10)
23、,19(9+10),21(5+16) 21(2+19),28(18+10),19(9+10),21(5+16)。 用同样的方法还可以将用同样的方法还可以将用同样的方法还可以将用同样的方法还可以将4 4 4 4阶数塔问题阶数塔问题阶数塔问题阶数塔问题, , , ,变为变为变为变为3 3 3 3阶数塔问题。阶数塔问题。阶数塔问题。阶数塔问题。 最后得到的最后得到的最后得到的最后得到的1 1 1 1阶数塔问题，就是整个问题的最优解。阶数塔问题，就是整个问题的最优解。阶数塔问题，就是整个问题的最优解。阶数塔问题，就是整个问题的最优解。 2 2 2 2存储、求解：存储、求解：存储、求解：存储、求解： 1
24、) 1) 1) 1) 原始信息存储原始信息存储原始信息存储原始信息存储 原始信息有层数和数塔中的数据，层数用一个整型变量原始信息有层数和数塔中的数据，层数用一个整型变量原始信息有层数和数塔中的数据，层数用一个整型变量原始信息有层数和数塔中的数据，层数用一个整型变量 n n n n 存储，数塔中的数据用二维数组存储，数塔中的数据用二维数组存储，数塔中的数据用二维数组存储，数塔中的数据用二维数组datadatadatadata，存储成如下的下三角存储成如下的下三角存储成如下的下三角存储成如下的下三角阵阵阵阵: : : : 9 9 9 9 12 15 12 15 12 15 12 15 10 6 8
25、 10 6 8 10 6 8 10 6 8 2 18 9 5 2 18 9 5 2 18 9 5 2 18 9 5 19 7 10 4 16 19 7 10 4 16 19 7 10 4 16 19 7 10 4 16 2) 2) 2) 2) 动态规划过程存储动态规划过程存储动态规划过程存储动态规划过程存储 用二维数组用二维数组用二维数组用二维数组d d d d存储各阶段的决策结果。二维数组存储各阶段的决策结果。二维数组存储各阶段的决策结果。二维数组存储各阶段的决策结果。二维数组d d d d的存的存的存的存储内容如下：储内容如下：储内容如下：储内容如下：dnjdnjdnjdnj=datanj
26、=datanj=datanj=datanj j=1,2, j=1,2, j=1,2, j=1,2,n,n,n,n； dijdijdijdij=max(di+1j=max(di+1j=max(di+1j=max(di+1j，di+1j+1)+dataijdi+1j+1)+dataijdi+1j+1)+dataijdi+1j+1)+dataij i=n-1,n-2,i=n-1,n-2,i=n-1,n-2,i=n-1,n-2,1 1 1 1，j=1,2,j=1,2,j=1,2,j=1,2,i,i,i,i； 最后最后最后最后d11d11d11d11存储的就是问题的结果。存储的就是问题的结果。存储的就是
27、问题的结果。存储的就是问题的结果。 数组数组数组数组data data data data 数组数组数组数组d d d d 9 599 599 599 59 12 15 50 49 12 15 50 49 12 15 50 49 12 15 50 49 10 6 8 38 34 29 10 6 8 38 34 29 10 6 8 38 34 29 10 6 8 38 34 29 2 18 9 5 21 28 19 21 2 18 9 5 21 28 19 21 2 18 9 5 21 28 19 21 2 18 9 5 21 28 19 21 19 7 10 4 16 19 7 10 4 16
28、 19 7 10 4 16 19 7 10 4 16 19 7 10 4 16 19 7 10 4 16 19 7 10 4 16 19 7 10 4 16 数塔及动态规划过程数据数塔及动态规划过程数据数塔及动态规划过程数据数塔及动态规划过程数据 输出输出输出输出data11 data11 data11 data11 9 9 9 9 b=d11-data11=59-9=50 b=d11-data11=59-9=50 b=d11-data11=59-9=50 b=d11-data11=59-9=50 b b b b与与与与d21,d22d21,d22d21,d22d21,d22比较比较比较比较,
29、b,b,b,b与与与与d21d21d21d21相等输出相等输出相等输出相等输出data21data21data21data2112121212 b=d21-data21=50-12=38 b=d21-data21=50-12=38 b=d21-data21=50-12=38 b=d21-data21=50-12=38 b b b b与与与与d31,d32 d31,d32 d31,d32 d31,d32 比较比较比较比较b b b b与与与与d31d31d31d31相等输出相等输出相等输出相等输出data31data31data31data3110101010 b=d31-data31=38-1
30、0=28 b=d31-data31=38-10=28 b=d31-data31=38-10=28 b=d31-data31=38-10=28 b b b b与与与与d41,d42 d41,d42 d41,d42 d41,d42 比较比较比较比较b b b b与与与与d42d42d42d42相等输出相等输出相等输出相等输出data42data42data42data4218181818 b=d42-data42=28-18=10 b=d42-data42=28-18=10 b=d42-data42=28-18=10 b=d42-data42=28-18=10 b b b b与与与与d52,d53
31、 d52,d53 d52,d53 d52,d53 比较比较比较比较b b b b与与与与d53d53d53d53相等输出相等输出相等输出相等输出data53data53data53data5310101010“ 3) 3) 3) 3) 最优解路径求解及存储最优解路径求解及存储最优解路径求解及存储最优解路径求解及存储为了设计简洁的算法，用三维数组为了设计简洁的算法，用三维数组为了设计简洁的算法，用三维数组为了设计简洁的算法，用三维数组a50503a50503a50503a50503存储以上确定的三个数组的信息。存储以上确定的三个数组的信息。存储以上确定的三个数组的信息。存储以上确定的三个数组的信
32、息。 a50501a50501a50501a50501代替数组代替数组代替数组代替数组datadatadatadata， a50502a50502a50502a50502代替数组代替数组代替数组代替数组d, d, d, d, a50503 a50503 a50503 a50503记录解路径。记录解路径。记录解路径。记录解路径。 for (i=n-1 ; i=1;for (i=n-1 ; i=1; i-)i-) for (j=1; for (j=1; j=i;jai+1j+12)if (ai+1j2ai+1j+12) aij2=aij2+ai+1j2;aij2=aij2+ai+1j2; aij3
33、=0;aij3=0; elseelse aij2=aij2+ai+1j+12;aij2=aij2+ai+1j+12; aij3=1;aij3=1; coutcout最大值最大值最大值最大值=a112;=a112;j=1;j=1;coutendlcoutendl路径路径路径路径:;:;for( i=1 ;for( i=1 ; i= n-1;i= n-1; i+)i+) coutaij1;coutaij1;j=j+aij3;j=j+aij3; coutanj1;coutB2AB2一一一一C4D3EC4D3E, , , ,最短路程长度为最短路程长度为最短路程长度为最短路程长度为1313。 多段图的最
34、短路径问题的填表形式。多段图的最短路径问题的填表形式。多段图的最短路径问题的填表形式。多段图的最短路径问题的填表形式。 用一个数组用一个数组用一个数组用一个数组costncostn作为存储子问题解的表格，作为存储子问题解的表格，作为存储子问题解的表格，作为存储子问题解的表格，costicosti表示从顶点表示从顶点表示从顶点表示从顶点i i到终点到终点到终点到终点n-1n-1的最短路径，数组的最短路径，数组的最短路径，数组的最短路径，数组pathnpathn存储状态，存储状态，存储状态，存储状态，pathipathi表示从顶点表示从顶点表示从顶点表示从顶点i i到终点到终点到终点到终点n-1n
35、-1的的的的路径上顶点路径上顶点路径上顶点路径上顶点i i的下一个顶点。则：的下一个顶点。则：的下一个顶点。则：的下一个顶点。则： costicosti=mincmincij ij+costj+costj(ijn(ijn且且且且顶顶顶顶点点点点j j是是是是顶顶顶顶点点点点i i的邻接点的邻接点的邻接点的邻接点)( (式式式式3.5)3.5)pathipathi=使使使使c cij ij+costj+costj 最小的最小的最小的最小的jj( (式式式式3.63.6） 算法算法算法算法多段图的最短路径多段图的最短路径多段图的最短路径多段图的最短路径1 1初始化：数组初始化：数组初始化：数组初始
36、化：数组costncostn初始化为最大值，数组初始化为最大值，数组初始化为最大值，数组初始化为最大值，数组pathnpathn初始化为初始化为初始化为初始化为- - - -1 1；2 2for(i=nfor(i=n- - - -2;i=0;i2;i=0;i-) )2.12.1对顶点对顶点对顶点对顶点i i的每一个邻接点的每一个邻接点的每一个邻接点的每一个邻接点j j，根据式根据式根据式根据式2.52.5计算计算计算计算costi;costi;2.22.2根据式根据式根据式根据式2.62.6计算计算计算计算pathi;pathi;33输出最短路径长度输出最短路径长度输出最短路径长度输出最短路径
37、长度cost0;cost0;4.4.输出最短路径经过的顶点：输出最短路径经过的顶点：输出最短路径经过的顶点：输出最短路径经过的顶点：4.1i=04.1i=04.24.2循环直到循环直到循环直到循环直到pathi=npathi=n- - - -1 14.2.14.2.1输出输出输出输出pathi;pathi;4.2.2i=pathi;4.2.2i=pathi; 算法主要由三部分组成：第一部分是初始化部分，其时算法主要由三部分组成：第一部分是初始化部分，其时算法主要由三部分组成：第一部分是初始化部分，其时算法主要由三部分组成：第一部分是初始化部分，其时间性能为间性能为间性能为间性能为O O( (n
38、 n) )；第二部分是依次计算各个顶点到终点的最短第二部分是依次计算各个顶点到终点的最短第二部分是依次计算各个顶点到终点的最短第二部分是依次计算各个顶点到终点的最短路径，由两层嵌套的循环组成，外层循环执行路径，由两层嵌套的循环组成，外层循环执行路径，由两层嵌套的循环组成，外层循环执行路径，由两层嵌套的循环组成，外层循环执行n-1n-1次，内层次，内层次，内层次，内层循环对所有出边进行计算，并且在所有循环中，每条出边只循环对所有出边进行计算，并且在所有循环中，每条出边只循环对所有出边进行计算，并且在所有循环中，每条出边只循环对所有出边进行计算，并且在所有循环中，每条出边只计算一次。假定图的边数为
39、计算一次。假定图的边数为计算一次。假定图的边数为计算一次。假定图的边数为mm，则这部分的时间性能是则这部分的时间性能是则这部分的时间性能是则这部分的时间性能是O O( (mm) )；第三部分是输出最短路径经过的顶点，其时间性能是第三部分是输出最短路径经过的顶点，其时间性能是第三部分是输出最短路径经过的顶点，其时间性能是第三部分是输出最短路径经过的顶点，其时间性能是O O( (n n) )。所以，算法所以，算法所以，算法所以，算法6.26.2的时间复杂性为的时间复杂性为的时间复杂性为的时间复杂性为O O( (n n+ +mm) )。 返回返回返回返回3.2.2TSP问题问题TSPTSP问题问题是
40、指旅行家要旅行是指旅行家要旅行是指旅行家要旅行是指旅行家要旅行n n个城市，要求各个个城市，要求各个个城市，要求各个个城市，要求各个城市城市城市城市经历经历且且且且仅经历仅经历一次然后回到出一次然后回到出一次然后回到出一次然后回到出发发城市，并要求城市，并要求城市，并要求城市，并要求所走的路程最短。所走的路程最短。所走的路程最短。所走的路程最短。各个城市各个城市各个城市各个城市间间的距离可以用代价矩的距离可以用代价矩的距离可以用代价矩的距离可以用代价矩阵阵来表示。来表示。来表示。来表示。C C= =367367523523642642375375带权图的代价矩阵带权图的代价矩阵带权图的代价矩阵
41、带权图的代价矩阵 设设设设s s, ,s s1 1, ,s s2 2, , ,s sp p, ,s s是从是从是从是从s s出发的一条路径长度最出发的一条路径长度最出发的一条路径长度最出发的一条路径长度最短的简单回路，假设从短的简单回路，假设从短的简单回路，假设从短的简单回路，假设从s s到下一个城市到下一个城市到下一个城市到下一个城市s s1 1已经求出，已经求出，已经求出，已经求出，则问题转化为求从则问题转化为求从则问题转化为求从则问题转化为求从s s1 1到到到到s s的最短路径，显然的最短路径，显然的最短路径，显然的最短路径，显然s s1 1, ,s s2 2, , ,s sp p,
42、,s s一定构成一条从一定构成一条从一定构成一条从一定构成一条从s s1 1到到到到s s的最短路径。的最短路径。的最短路径。的最短路径。 如若不然，设如若不然，设如若不然，设如若不然，设s s1 1, ,r r1 1, ,r r2 2, , ,r rq q, ,s s是一条从是一条从是一条从是一条从s s1 1到到到到s s的最的最的最的最短路径且经过短路径且经过短路径且经过短路径且经过n n-1-1个不同城市，则个不同城市，则个不同城市，则个不同城市，则s s, ,s s1 1, ,r r1 1, ,r r2 2, , ,r rq q, ,s s将是一条从将是一条从将是一条从将是一条从s
43、s出发的路径长度最短的简单回出发的路径长度最短的简单回出发的路径长度最短的简单回出发的路径长度最短的简单回路且比路且比路且比路且比s s, ,s s1 1, ,s s2 2, , ,s sp p, ,s s要短，从而导致矛盾。所以，要短，从而导致矛盾。所以，要短，从而导致矛盾。所以，要短，从而导致矛盾。所以，TSPTSP问题满足最优性原理。问题满足最优性原理。问题满足最优性原理。问题满足最优性原理。证明证明证明证明TSPTSP问题满足最优性原理问题满足最优性原理问题满足最优性原理问题满足最优性原理 假设从顶点假设从顶点假设从顶点假设从顶点i i出发，令出发，令出发，令出发，令d d( ( i
44、i, , V V ) )表示从顶点表示从顶点表示从顶点表示从顶点i i 出出出出发经过发经过发经过发经过V V 中各个顶点一次且仅一次，最后回到出中各个顶点一次且仅一次，最后回到出中各个顶点一次且仅一次，最后回到出中各个顶点一次且仅一次，最后回到出发点发点发点发点 i i 的最短路径长度，开始时，的最短路径长度，开始时，的最短路径长度，开始时，的最短路径长度，开始时，V V V V i i ，于，于，于，于是，是，是，是，TSPTSP问题的动态规划函数为：问题的动态规划函数为：问题的动态规划函数为：问题的动态规划函数为： d d( ( i i, ,V V )=)=minminc cikik+
45、+d d( (k k, ,V V k k)()(k kV V ) ) （式（式（式（式3.73.7） d d( (k k, )=, )=c ckiki( (k k i i) ) （式（式（式（式3.83.8）这是最后一个阶段的决策，而：这是最后一个阶段的决策，而：这是最后一个阶段的决策，而：这是最后一个阶段的决策，而： d d(1,2,3)=min(1,2,3)=minc c1212+ +d d(2,3),(2,3),c c1313+ + d d(3,2)(3,2) d d(2,1,3)=min(2,1,3)=minc c2121+ +d d(1,3),(1,3),c c2323+ + d d
46、(3,1)(3,1) d d(3,1,2)=min(3,1,2)=minc c3131+ +d d(1,2),(1,2),c c3232+ + d d(2,1)(2,1)这一阶段的决策又依赖于下面的计算结果：这一阶段的决策又依赖于下面的计算结果：这一阶段的决策又依赖于下面的计算结果：这一阶段的决策又依赖于下面的计算结果： d d(1,2)=(1,2)= c c1212+ +d d(2,)(2,)d d(2,3)=(2,3)=c c2323+ +d d(3,)(3,) d d(3,2)=(3,2)= c c3232+ +d d(2,)(2,)d d(1,3)=(1,3)= c c1313+ +d
47、 d(3,)(3,) d d(2,1)=(2,1)=c c2121+ +d d(1,)(1,)d d(3,1)=(3,1)=c c3131+ +d d(1,)(1,)从城市从城市从城市从城市0 0出发经城市出发经城市出发经城市出发经城市1 1、2 2、3 3然后回到城市然后回到城市然后回到城市然后回到城市0 0的最短路径长度是：的最短路径长度是：的最短路径长度是：的最短路径长度是：d d(0,(0,1,2,3)=min1,2,3)=minc c0101+ +d d(1,2,3),(1,2,3),c c0202+ +d d(2,1,3),(2,1,3),c c0303+ +d d(3,1,2)(
48、3,1,2)而下式可以直接获得（括号中是该决策引起的状态转移）：而下式可以直接获得（括号中是该决策引起的状态转移）：而下式可以直接获得（括号中是该决策引起的状态转移）：而下式可以直接获得（括号中是该决策引起的状态转移）：d(1,)=cd(1,)=c1010=5(10)d(2,)=c=5(10)d(2,)=c2020=6(20)d(3,)=c=6(20)d(3,)=c3030=3(30)=3(30)再向前倒推，有：再向前倒推，有：再向前倒推，有：再向前倒推，有：d d(1,(1,2)=2)=c c1212+ +d d(2,(2,)=2+6=8(12)=2+6=8(12) d d(1,(1,3)=
49、3)= c c1313+ +d d(3,(3,)=3+3=6(13)=3+3=6(13)d d(2,(2,3)=3)=c c2323+ +d d(3,(3,)=)=2+32+3=5(=5(2323) ) d d(2,(2,1)=1)= c c2121+ +d d(1,(1,)=4+5=9(21)=4+5=9(21)d d(3,(3,1)=1)=c c3131+ +d d(1,(1,)=7+5=12(31)=7+5=12(31)d d(3,(3,2)=2)= c c3232+ +d d(2,(2,)=5+6=11(32)=5+6=11(32)再向前倒退，有：再向前倒退，有：再向前倒退，有：再向前
50、倒退，有：d d(1,2,3)=min(1,2,3)=minc c1212+ +d d(2,3),(2,3),c c1313+ + d d(3,2)=min(3,2)=min2+52+5,3+11=7(,3+11=7(1212) )d d(2,(2,1,1,3)=min3)=minc c2121+ +d d(1,(1,3),3),c c2323+ + d d(3,(3,1)=min4+6,1)=min4+6,2+12=10(21)2+12=10(21)d d(3,(3,1,1,2)=min2)=minc c3131+ +d d(1,(1,2),2),c c3232+ + d d(2,(2,1)
51、=min7+8,1)=min7+8,5+9=14(32)5+9=14(32)最后有：最后有：最后有：最后有：d d(0,(0,1,1,2,2,3)=min3)=minc c0101+ + d d(1,(1, 2,2,3),3),c c0202+ + d d(2,(2,1,1,3),3),c c0303+ + d d(3,(3,1,1,2)2)=min=min3+73+7,6+10,7+14=10(,6+10,7+14=10(0101) ) 所所所所以以以以，从从从从顶顶顶顶点点点点0 0出出出出发发发发的的的的TSPTSP问问问问题题题题的的的的最最最最短短短短路路路路径径径径长长长长度度度度
52、为为为为1010，路路路路径径径径是是是是0123001230。 假设假设假设假设n n个顶点用个顶点用个顶点用个顶点用0 0n-1n-1的数字编号，首先生成的数字编号，首先生成的数字编号，首先生成的数字编号，首先生成1 1n-1n-1个元素的个元素的个元素的个元素的子集存放在数组子集存放在数组子集存放在数组子集存放在数组V2V2n-1n-1 中，设数组中，设数组中，设数组中，设数组dn2dn2n-1n-1 存放迭代结果，存放迭代结果，存放迭代结果，存放迭代结果，其中其中其中其中dijdij表示从顶点表示从顶点表示从顶点表示从顶点i i经过子集经过子集经过子集经过子集VjVj中的顶点中的顶点中
53、的顶点中的顶点一次且仅一次，一次且仅一次，一次且仅一次，一次且仅一次，最后回到出发点最后回到出发点最后回到出发点最后回到出发点0 0的最短路径长度。的最短路径长度。的最短路径长度。的最短路径长度。jji i1122331,21,21,31,32,32,31,2,1,2,330 0 10101 15 5 8 86 6 7 7 2 26 69 9 5 5 1010 3 33 312121111 1414 动态规划法求解动态规划法求解动态规划法求解动态规划法求解TSPTSP问题的填表过程问题的填表过程问题的填表过程问题的填表过程算法算法算法算法TSPTSP问题问题问题问题 1 1for(i=1;in
54、;i+)/for(i=1;in;i+)/初始化第初始化第初始化第初始化第0 0列列列列di0=ci0;di0=ci0;2 2for(j=1;j2for(j=1;j2n-1n-1- - - -1;j+)1;j+)for(i=1;in;i+)/for(i=1;i)V V( (n n- - - -1 1,C,C) )，表明第表明第表明第表明第n n个物品被装入背包，前个物品被装入背包，前个物品被装入背包，前个物品被装入背包，前n n- - - -1 1个物品被装入容量个物品被装入容量个物品被装入容量个物品被装入容量为为为为C C- - - -w wn n的背包中；否则，第的背包中；否则，第的背包中；
55、否则，第的背包中；否则，第n n个物品没有被装入背包，前个物品没有被装入背包，前个物品没有被装入背包，前个物品没有被装入背包，前n n- - - -1 1个物品被装入容量为个物品被装入容量为个物品被装入容量为个物品被装入容量为C C的背包中。依此类推，直到确定第的背包中。依此类推，直到确定第的背包中。依此类推，直到确定第的背包中。依此类推，直到确定第1 1个个个个物品是否被装入背包中为止。由此，得到如下函数：物品是否被装入背包中为止。由此，得到如下函数：物品是否被装入背包中为止。由此，得到如下函数：物品是否被装入背包中为止。由此，得到如下函数： （式（式（式（式3.133.13） 设设设设n
56、n个个个个物物物物品品品品的的的的重重重重量量量量存存存存储储储储在在在在数数数数组组组组wnwn中中中中，价价价价值值值值存存存存储储储储在在在在数数数数组组组组vnvn中中中中，背背背背包包包包容容容容量量量量为为为为C C，数数数数组组组组Vn+1C+1Vn+1C+1存存存存放放放放迭迭迭迭代代代代结结结结果果果果，其其其其中中中中VijVij表表表表示示示示前前前前i i个个个个物物物物品品品品装装装装入入入入容容容容量量量量为为为为j j的的的的背背背背包包包包中中中中获获获获得得得得的的的的最最最最大大大大价价价价值值值值，数数数数组组组组xnxn存存存存储储储储装装装装入入入入背
57、背背背包包包包的的的的物物物物品品品品，动动动动态态态态规规规规划划划划法法法法求求求求解解解解0/10/1背背背背包包包包问问问问题题题题的的的的算算算算法法法法如下：如下：如下：如下： 算法算法算法算法0/10/1背包问题背包问题背包问题背包问题intint KnapSack(intKnapSack(intn,n,intintw,w,intintv)v)for(i=0;i=n;i+)/for(i=0;i=n;i+)/初始化第初始化第初始化第初始化第0 0列列列列Vi0=0;Vi0=0;for(j=0;j=C;j+)/for(j=0;j=C;j+)/初始化第初始化第初始化第初始化第0 0行行
58、行行V0j=0;V0j=0;for(i=1;i=n;i+)/for(i=1;i=n;i+)/计算第计算第计算第计算第i i行，进行第行，进行第行，进行第行，进行第i i次迭代次迭代次迭代次迭代for(j=1;j=C;j+)for(j=1;j=C;j+)if(jif(j0;i-)for(i=n;i0;i-)if(VijVi-1j)if(VijVi-1j)xixi=1;=1;j=j=j-wij-wi;elsexi=0;elsexi=0;returnVnC;/returnVnC;/返回背包取得的最大价值返回背包取得的最大价值返回背包取得的最大价值返回背包取得的最大价值 在算法中，第一个在算法中，第一
59、个在算法中，第一个在算法中，第一个forfor循环的时间性能是循环的时间性能是循环的时间性能是循环的时间性能是O O( (n n) )，第二个第二个第二个第二个forfor循环的时间性能是循环的时间性能是循环的时间性能是循环的时间性能是O O( (C C) )，第三个循环是两第三个循环是两第三个循环是两第三个循环是两层嵌套的层嵌套的层嵌套的层嵌套的forfor循环，其时间性能是循环，其时间性能是循环，其时间性能是循环，其时间性能是O O( (n nC C) )，第四个第四个第四个第四个forfor循环的时间性能是循环的时间性能是循环的时间性能是循环的时间性能是O O( (n n) )，所以，算
60、法所以，算法所以，算法所以，算法6.36.3的时间复的时间复的时间复的时间复杂性为杂性为杂性为杂性为O O( (n nC C) )。 返回返回返回返回3.3.2最长公共子序列问题最长公共子序列问题对对对对给给给给定定定定序序序序列列列列X X=(=(x x1 1, , x x2 2, x xmm) )和和和和序序序序列列列列Z Z=(=(z z1 1, ,z z2 2,z zk k) )，Z Z是是是是X X的的的的子子子子序序序序列列列列当当当当且且且且仅仅仅仅当当当当存存存存在在在在一一一一个个个个严严严严格格格格递递递递增增增增下下下下标标标标序序序序列列列列( (i i1,1,i i2
61、,2,ikik) )，使使使使得得得得对对对对于于于于所所所所有有有有j j=1,=1,2,2,k k，有，有，有，有z zj j= =x xij ij（11ij ij mm）。）。）。）。 给定两个序列给定两个序列给定两个序列给定两个序列X X和和和和Y Y，当另一个序列当另一个序列当另一个序列当另一个序列Z Z既是既是既是既是X X的的的的子序列又是子序列又是子序列又是子序列又是Y Y的子序列时，称的子序列时，称的子序列时，称的子序列时，称Z Z是序列是序列是序列是序列X X和和和和Y Y的公共的公共的公共的公共子序列。最长公共子序列问题就是在序列子序列。最长公共子序列问题就是在序列子序列
62、。最长公共子序列问题就是在序列子序列。最长公共子序列问题就是在序列X X和和和和Y Y的的的的公共子序列中查找长度最长的公共子序列。公共子序列中查找长度最长的公共子序列。公共子序列中查找长度最长的公共子序列。公共子序列中查找长度最长的公共子序列。 证明最长公共子序列问题满足最优性原理。证明最长公共子序列问题满足最优性原理。证明最长公共子序列问题满足最优性原理。证明最长公共子序列问题满足最优性原理。设设设设序序序序列列列列X X=x x1 1, ,x x2 2,x xmm 和和和和Y Y=y y1 1, ,y y2 2,y yn n 的的的的最最最最长长长长公公公公共共共共子子子子序序序序列列列
63、列为为为为Z Z=z z1 1, ,z z2 2,z zk k ，记记记记X Xk k为为为为序序序序列列列列X X中中中中前前前前k k个个个个连连连连续续续续字字字字符符符符组组组组成成成成的的的的子子子子序序序序列列列列，Y Yk k为为为为序序序序列列列列Y Y中中中中前前前前k k个个个个连连连连续续续续字字字字符符符符组组组组成成成成的的的的子子子子序序序序列列列列，Z Zk k为为为为序序序序列列列列Z Z中前中前中前中前k k个连续字符组成的子序列，显然有下式成立：个连续字符组成的子序列，显然有下式成立：个连续字符组成的子序列，显然有下式成立：个连续字符组成的子序列，显然有下式
64、成立：（1 1）若若若若x xmm= =y yn n，则则则则z zk k= =x xmm= =y yn n，且且且且Z Zk k-1-1是是是是X Xmm-1-1和和和和Y Yn n-1-1的的的的最最最最长长长长公公公公共共共共子序列；子序列；子序列；子序列；（2 2）若）若）若）若x xmm y yn n且且且且z zk k x xmm，则，则，则，则Z Z是是是是X Xmm-1-1和和和和Y Y的最长公共子序列；的最长公共子序列；的最长公共子序列；的最长公共子序列；（3 3）若）若）若）若x xmm y yn n且且且且z zk k y yn n，则，则，则，则Z Z是是是是X X和和
65、和和Y Yn n-1-1的最长公共子序列。的最长公共子序列。的最长公共子序列。的最长公共子序列。 可可可可见见见见，两两两两个个个个序序序序列列列列的的的的最最最最长长长长公公公公共共共共子子子子序序序序列列列列包包包包含含含含了了了了这这这这两两两两个个个个序序序序列列列列的的的的前缀序列的最长公共子序列。前缀序列的最长公共子序列。前缀序列的最长公共子序列。前缀序列的最长公共子序列。要要要要找找找找出出出出序序序序列列列列X X=x x1 1, ,x x2 2,x xmm 和和和和Y Y=y y1 1, ,y y2 2,y yn n 的的的的最最最最长长长长公公公公共共共共子子子子序序序序列
66、列列列，可可可可按按按按下下下下述述述述递递递递推推推推方方方方式式式式计计计计算算算算：当当当当x xmm= =y yn n时时时时，找找找找出出出出X Xmm-1-1和和和和Y Yn n- -1 1的的的的最最最最长长长长公公公公共共共共子子子子序序序序列列列列，然然然然后后后后在在在在其其其其尾尾尾尾部部部部加加加加上上上上x xmm即即即即可可可可得得得得到到到到X X和和和和Y Y的的的的最最最最长长长长公公公公共共共共子子子子序序序序列列列列；当当当当x xmm y yn n时时时时，必必必必须须须须求求求求解解解解两两两两个个个个子子子子问问问问题题题题：找找找找出出出出X Xm
67、m-1-1和和和和Y Y的的的的最最最最长长长长公公公公共共共共子子子子序序序序列列列列以以以以及及及及X Xmm和和和和Y Yn n-1-1的的的的最最最最长长长长公公公公共共共共子子子子序序序序列列列列，这这这这两两两两个个个个公公公公共共共共子子子子序序序序列列列列中中中中的的的的较较较较长长长长者者者者即即即即为为为为X X和和和和Y Y的的的的最最最最长长长长公公公公共共共共子子子子序序序序列列列列。用用用用LijLij表表表表示示示示子子子子序序序序列列列列X Xi i和和和和Y Yj j的的的的最最最最长长长长公公公公共共共共子子子子序序序序列列列列的的的的长长长长度度度度，可可
68、可可得得得得如如如如下动态规划函数：下动态规划函数：下动态规划函数：下动态规划函数：L00=Li0=L0j=0(1im,1jn)L00=Li0=L0j=0(1im,1jn)（式（式（式（式3.143.14）（式（式（式（式3.153.15） 由此，把序列由此，把序列由此，把序列由此，把序列X X=x x1 1, ,x x2 2, , ,x xmm 和和和和Y Y=y y1 1, ,y y2 2, , ,y yn n 的最长公共子序列的搜索分为的最长公共子序列的搜索分为的最长公共子序列的搜索分为的最长公共子序列的搜索分为mm个阶段，个阶段，个阶段，个阶段，第第第第1 1阶段，按照式阶段，按照式阶
69、段，按照式阶段，按照式3.153.15计算计算计算计算X X1 1和和和和Y Yj j的最长公共子序的最长公共子序的最长公共子序的最长公共子序列长度列长度列长度列长度L1jL1j（1 1j jn n），第），第），第），第2 2阶段，按照式阶段，按照式阶段，按照式阶段，按照式3.153.15计计计计算算算算X X2 2和和和和Y Yj j的最长公共子序列长度的最长公共子序列长度的最长公共子序列长度的最长公共子序列长度L2jL2j（1 1j jn n），），），），依此类推，最后在第依此类推，最后在第依此类推，最后在第依此类推，最后在第mm阶段，计算阶段，计算阶段，计算阶段，计算X Xmm和和和
70、和Y Yj j的最长公的最长公的最长公的最长公共子序列长度共子序列长度共子序列长度共子序列长度LmjLmj（1 1j jn n），则），则），则），则LmnLmn就是就是就是就是序列序列序列序列X Xmm和和和和Y Yn n的最长公共子序列的长度。的最长公共子序列的长度。的最长公共子序列的长度。的最长公共子序列的长度。 为了得到序列为了得到序列为了得到序列为了得到序列X Xmm和和和和Y Yn n具体的最长公共子序列，设二维具体的最长公共子序列，设二维具体的最长公共子序列，设二维具体的最长公共子序列，设二维表表表表Sm+1n+1Sm+1n+1，其中其中其中其中SijSij表示在计算表示在计算表
71、示在计算表示在计算LijLij的过程中的的过程中的的过程中的的过程中的搜索状态，并且有：搜索状态，并且有：搜索状态，并且有：搜索状态，并且有： （式（式（式（式3.163.16） 若若若若Sij=1Sij=1，表明表明表明表明a ai i= =b bj j，则下一个搜索方向是则下一个搜索方向是则下一个搜索方向是则下一个搜索方向是SiSi- - - -1j1j- - - -11；若；若；若；若Sij=2Sij=2，表明表明表明表明a ai ib bj j且且且且LijLij- - - -11LiLi- - - -1j1j，则下一则下一则下一则下一个搜索方向是个搜索方向是个搜索方向是个搜索方向是S
72、ijSij- - - -11；若；若；若；若Sij=3Sij=3，表明表明表明表明a ai ib bj j且且且且LijLij- - - -11LiLi- - - -1j1j，则下一个搜索方向是则下一个搜索方向是则下一个搜索方向是则下一个搜索方向是SiSi- - - -1j1j。 (a)长度矩度矩阵L(b)状状态矩矩阵S0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 90 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 90 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0
73、0 0 0 0 0 0 0 0 0 0 01 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 0 0 1 1 2 2 2 2 2 2 1 1 2 2 2 2 2 2 2 22 2 0 0 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 22 2 0 0 3 3 2 2 1 1 1 1 2 2 1 1 2 2 1 1 1 13 3 0 0 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 23 3 0 0 3 3 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 24 4 0 0 1 1 2 2 3 3 3
74、 3 3 3 3 3 3 3 3 3 3 34 4 0 0 3 3 3 3 1 1 1 1 3 3 1 1 3 3 1 1 1 15 5 0 0 1 1 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 45 5 0 0 3 3 3 3 3 3 2 2 2 2 2 2 1 1 2 2 2 26 6 0 0 1 1 2 2 3 3 4 4 4 4 4 4 4 4 5 5 5 56 6 0 0 3 3 3 3 1 1 1 1 3 3 1 1 2 2 1 1 1 1例：序列例：序列例：序列例：序列X X=(=(a a, ,b b, ,c c, ,b b, ,d d, ,b b) )，Y Y
75、=(=(a a, ,c c, ,b b, ,b b, ,a a, ,b b, , d d, , b b, ,b b) )，建立，建立，建立，建立两个两个两个两个(m+1)(n+1)(m+1)(n+1)的二维表的二维表的二维表的二维表L L和表和表和表和表S S，分别存放搜索过程中，分别存放搜索过程中，分别存放搜索过程中，分别存放搜索过程中得到的子序列的长度和状态。得到的子序列的长度和状态。得到的子序列的长度和状态。得到的子序列的长度和状态。算法算法算法算法最长公共子序列问题最长公共子序列问题最长公共子序列问题最长公共子序列问题intint CommonOrder(intCommonOrder(
76、intm,m,intintn,n,intintx,x,intinty,y,intintz)z)for(j=0;j=n;j+)/for(j=0;j=n;j+)/初始化第初始化第初始化第初始化第0 0行行行行L0j=0;L0j=0;for(i=0;j=m;i+)/for(i=0;j=m;i+)/初始化第初始化第初始化第初始化第0 0列列列列Li0=0;Li0=0;for(i=1;i=m;i+)for(i=1;i=m;i+)for(j=1;j=n;j+)for(j=1;j=Li1=Li- - - -1j)Lij=Lij1j)Lij=Lij- - - -1;Sij=2;1;Sij=2;elseLij=
77、LielseLij=Li- - - -1j;Sij=3;1j;Sij=3;i=m;j=n;k=Lmn;i=m;j=n;k=Lmn;for(i0&j0)for(i0&j0)if(Sij=1)zk=xi;kif(Sij=1)zk=xi;k-;i;i-;j;j-;elseif(Sij=2)jelseif(Sij=2)j-; ;elseielsei-; ;returnLmn;returnLmn;第一个第一个第一个第一个forfor循环的时间性能是循环的时间性能是循环的时间性能是循环的时间性能是O O( (n n) )；第二个第二个第二个第二个forfor循环的时间性能是循环的时间性能是循环的时间性能是
78、循环的时间性能是O O( (mm) )；第三个循环是两层嵌套的第三个循环是两层嵌套的第三个循环是两层嵌套的第三个循环是两层嵌套的forfor循环，其时间性能是循环，其时间性能是循环，其时间性能是循环，其时间性能是O O( (mmn n) )；第四个第四个第四个第四个forfor循环的时间性能是循环的时间性能是循环的时间性能是循环的时间性能是O O( (k k) )，而，而，而，而k kminminmm, ,n n ，所所所所以，算法以，算法以，算法以，算法6.46.4的时间复杂性是的时间复杂性是的时间复杂性是的时间复杂性是O O( (mmn n) )。 返回返回返回返回 设设设设 r r1 1
79、, ,r r2 2, , ,r rn n 是是是是n n个个个个记记记记录录录录的的的的集集集集合合合合，其其其其查查查查找找找找概概概概率率率率分分分分别别别别是是是是 p p1 1, , p p2 2, , , , p pn n ，最最最最优优优优二二二二叉叉叉叉查查查查找找找找树树树树（OptimalOptimal BinaryBinarySearchSearchTreesTrees）是是是是以以以以这这这这n n个个个个记记记记录录录录构构构构成成成成的的的的二二二二叉叉叉叉查查查查找找找找树树树树中中中中具具具具有有有有最最最最少平均比较次数的二叉查找树，即少平均比较次数的二叉查找树
80、，即少平均比较次数的二叉查找树，即少平均比较次数的二叉查找树，即 最最最最小小小小，其其其其中中中中p pi i是是是是记记记记录录录录r ri i的的的的查查查查找找找找概概概概率率率率，c ci i是是是是在在在在二二二二叉叉叉叉查查查查找找找找树树树树中中中中查找查找查找查找r ri i的比较次数。的比较次数。的比较次数。的比较次数。 最优二叉查找树最优二叉查找树最优二叉查找树最优二叉查找树 3.4查找问题中的动态规划法查找问题中的动态规划法返回返回返回返回ABCD(a)(b)(c)二叉查找树示例二叉查找树示例二叉查找树示例二叉查找树示例BCDAABCD例如，集合例如，集合例如，集合例如
81、，集合 A A, ,B B, ,C C, ,D D 的查找概率是的查找概率是的查找概率是的查找概率是0.1,0.2,0.4,0.30.1,0.2,0.4,0.3， (a)(a)的平均比较次数是的平均比较次数是的平均比较次数是的平均比较次数是0.110.110.22+0.43+0.34=2.90.22+0.43+0.34=2.9，(b)(b)的平均比较次数是的平均比较次数是的平均比较次数是的平均比较次数是0.120.120.21+0.42+0.33=2.10.21+0.42+0.33=2.1，(c)(c)的平均比较次数是的平均比较次数是的平均比较次数是的平均比较次数是0.130.130.22+0
82、.41+0.32=1.70.22+0.41+0.32=1.7。将由将由将由将由 r r1 1, ,r r2 2, , ,r rn n 构成的二叉查找树记为构成的二叉查找树记为构成的二叉查找树记为构成的二叉查找树记为T T(1,(1,n n) )，其中其中其中其中r rk k（1 1k kn n）是是是是T T(1,(1,n n) )的根结点，则其左子树的根结点，则其左子树的根结点，则其左子树的根结点，则其左子树T T(1,(1,k k- - - -1)1)由由由由 r r1 1, , ,r rk k-1-1 构成，其右子构成，其右子构成，其右子构成，其右子树树树树T T( (k k+1,+1,
83、n n) )由由由由 r rk k+1+1, , ,r rn n 构成。构成。构成。构成。证明最优二叉查找树满足最优性原理证明最优二叉查找树满足最优性原理证明最优二叉查找树满足最优性原理证明最优二叉查找树满足最优性原理rkT(1,n)以以以以r rk k为根的二叉查找树为根的二叉查找树为根的二叉查找树为根的二叉查找树T(k+1,n)T(1,k- -1)若若若若T T(1,(1,n n) )是最优二叉查找树，则其左是最优二叉查找树，则其左是最优二叉查找树，则其左是最优二叉查找树，则其左子树子树子树子树T T(1,(1,k k-1)-1)和右子树和右子树和右子树和右子树T T( (k k+1,+1
84、,n n) )也是也是也是也是最优二叉查找树，如若不然，假设最优二叉查找树，如若不然，假设最优二叉查找树，如若不然，假设最优二叉查找树，如若不然，假设TT(1,(1,k k-1)-1)是比是比是比是比T T(1,(1,k k-1)-1)更优的二叉查更优的二叉查更优的二叉查更优的二叉查找树，则找树，则找树，则找树，则TT(1,(1,k k-1)-1)的平均比较次数小的平均比较次数小的平均比较次数小的平均比较次数小于于于于T T(1,(1,k k-1)-1)的平均比较次数，从而由的平均比较次数，从而由的平均比较次数，从而由的平均比较次数，从而由TT(1,(1,k k-1)-1)、r rk k和和和
85、和T T( (k k+1,+1,n n) )构成的二叉构成的二叉构成的二叉构成的二叉查找树查找树查找树查找树TT(1,(1,n n) )的平均比较次数小于的平均比较次数小于的平均比较次数小于的平均比较次数小于T T(1,(1,n n) )的平均比较次数，这与的平均比较次数，这与的平均比较次数，这与的平均比较次数，这与T T(1,(1,n n) )是最优二叉查找树的假设相矛盾。是最优二叉查找树的假设相矛盾。是最优二叉查找树的假设相矛盾。是最优二叉查找树的假设相矛盾。 设设设设T T( (i i, ,j j) )是由记录是由记录是由记录是由记录 r ri i, , ,r rj j(1(1i ij
86、jn n) )构成的二叉查构成的二叉查构成的二叉查构成的二叉查找树，找树，找树，找树，C C( (i i, ,j j) )是这棵二叉查找树的平均比较次数。虽然最后是这棵二叉查找树的平均比较次数。虽然最后是这棵二叉查找树的平均比较次数。虽然最后是这棵二叉查找树的平均比较次数。虽然最后的结果是的结果是的结果是的结果是C C(1,(1,n n) )，但遵循动态规划法的求解方法但遵循动态规划法的求解方法但遵循动态规划法的求解方法但遵循动态规划法的求解方法, ,需要求出需要求出需要求出需要求出所有较小子问题所有较小子问题所有较小子问题所有较小子问题C C( (i i, ,j j) )的值，考虑从的值，考
87、虑从的值，考虑从的值，考虑从 r ri i, , ,r rj j 中选择一个记中选择一个记中选择一个记中选择一个记录录录录r rk k作为二叉查找树的根结点，可以得到如下关系：作为二叉查找树的根结点，可以得到如下关系：作为二叉查找树的根结点，可以得到如下关系：作为二叉查找树的根结点，可以得到如下关系： 因此，得到如下动态规划函数：因此，得到如下动态规划函数：因此，得到如下动态规划函数：因此，得到如下动态规划函数： C C( (i i, ,i i-1)=0(1-1)=0(1i i n n+1)+1)（式（式（式（式6.176.17）C C( (i i, ,i i)=)=p pi i (1(1i
88、i n n)（式（式（式（式6.186.18）C C( (i i, ,j j)=min)=minC C( (i i, ,k k-1)+-1)+C C( (k k+1,+1,j j)+(1)+(1i i j j n n, ,i i k k j j) )（式（式（式（式6.196.19）设设设设一一一一个个个个二二二二维维维维表表表表Cn+1n+1Cn+1n+1，其其其其中中中中CijCij表表表表示示示示二二二二叉叉叉叉查查查查找找找找树树树树T(i,T(i,j) j)的的的的平平平平均均均均比比比比较较较较次次次次数数数数。注注注注意意意意到到到到在在在在式式式式6.196.19中中中中，当当
89、当当k=1k=1时时时时，求求求求CijCij需需需需要要要要用用用用到到到到Ci0Ci0，当当当当k=nk=n时时时时，求求求求CijCij需需需需要要要要用用用用到到到到Cn+1jCn+1j，所所所所以以以以，二二二二维维维维表表表表Cn+1n+1Cn+1n+1行行行行下下下下标标标标的的的的范范范范围围围围为为为为1 1n+1n+1，列列列列下下下下标标标标的的的的范围为范围为范围为范围为0 0n n。 为为为为了了了了在在在在求求求求出出出出由由由由 r r1 1, ,r r2 2, ,r rn n 构构构构成成成成的的的的二二二二叉叉叉叉查查查查找找找找树树树树的的的的平平平平均均均
90、均比比比比较较较较次次次次数数数数的的的的同同同同时时时时得得得得到到到到最最最最优优优优二二二二叉叉叉叉查查查查找找找找树树树树，设设设设一一一一个个个个二二二二维维维维表表表表Rn+1n+1Rn+1n+1，其其其其下下下下标标标标范范范范围围围围与与与与二二二二维维维维表表表表C C相相相相同同同同，RijRij表表表表示示示示二二二二叉叉叉叉查找树查找树查找树查找树T(i,j)T(i,j)的根结点的序号。的根结点的序号。的根结点的序号。的根结点的序号。 例例例例如如如如，集集集集合合合合 A A, ,B B, ,C C, ,D D 的的的的查查查查找找找找概概概概率率率率是是是是0.1,
91、0.1,0.2,0.2,0.4,0.4,0.30.3，二维表，二维表，二维表，二维表C C和和和和R R的初始情况如图的初始情况如图的初始情况如图的初始情况如图6.136.13所示。所示。所示。所示。 0 01 12 23 34 41 10 00.10.1 2 2 0 00.20.2 3 3 0 00.40.4 4 4 0 00.30.35 5 0 0 0 01 12 23 34 41 1 1 1 2 2 2 2 3 3 3 3 4 4 4 45 5 在二维表在二维表在二维表在二维表C C和和和和R R中只需计算主对角线以上的元素。中只需计算主对角线以上的元素。中只需计算主对角线以上的元素。中
92、只需计算主对角线以上的元素。首先计算首先计算首先计算首先计算C C(1,2)(1,2)： 在前两个记录构成的最优二叉查找树的根结点的序号是在前两个记录构成的最优二叉查找树的根结点的序号是在前两个记录构成的最优二叉查找树的根结点的序号是在前两个记录构成的最优二叉查找树的根结点的序号是2 2。按对角线逐条计算每一个按对角线逐条计算每一个按对角线逐条计算每一个按对角线逐条计算每一个C(i,j)C(i,j)和和和和R(i,j)R(i,j)，得到最终表。得到最终表。得到最终表。得到最终表。 0 01 12 23 34 41 10 00.10.10.40.41.11.11.71.72 2 0 00.20.
93、20.80.81.41.43 3 0 00.40.41.01.04 4 0 00.30.35 5 0 0 0 01 12 23 34 41 1 1 12 2 2 23 33 32 2 2 23 33 33 3 3 33 34 4 4 45 5 (a)(a)二维表二维表C(b)C(b)二维表二维表R R(b)(b)最终表的状态最终表的状态d d=1=1d d=2=2d d=3=3d d=1=1d d=2=2d d=3=3设设设设n n个个个个字字字字符符符符的的的的查查查查找找找找概概概概率率率率存存存存储储储储在在在在数数数数组组组组pnpn中中中中，动动动动态态态态规规规规划划划划法法法法求
94、求求求解解解解最优二叉查找树的算法如下：最优二叉查找树的算法如下：最优二叉查找树的算法如下：最优二叉查找树的算法如下：算法算法算法算法最优二叉查找树最优二叉查找树最优二叉查找树最优二叉查找树 doubledoubleOptimalBST(intOptimalBST(int n,n,doubledoublepp,doubledoubleCC,intint R R)for(i=1;i=n;i+)/for(i=1;i=n;i+)/按式按式按式按式6.176.17和式和式和式和式6.186.18初始化初始化初始化初始化 Cii-1=0;Cii-1=0;CiiCii=pipi; ;RiiRii=i;=i
95、;Cn+1n=0;Cn+1n=0;for(d=1;dn;d+)/for(d=1;dn;d+)/按对角线逐条计算按对角线逐条计算按对角线逐条计算按对角线逐条计算for(i=1;i=n-d;i+)for(i=1;i=n-d;i+)j=i+d;j=i+d;min=;mink=i;sum=0;min=;mink=i;sum=0;for(k=i;k=j;k+)for(k=i;k=j;k+)sum=sum=sum+pksum+pk; ;if(Cik-1+Ck+1jmin)if(Cik-1+Ck+1jmin)min=Cik-1+Ck+1j;min=Cik-1+Ck+1j;mink=k;mink=k;CijCij=min+sum;=min+sum;RijRij=mink;=mink;returnC1n;returnC1n; 返回返回返回返回
