算法设计动态规划ppt课件.ppt

《算法设计动态规划ppt课件.ppt》由会员分享，可在线阅读，更多相关《算法设计动态规划ppt课件.ppt（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、动态规划法动态规划法 12/28/20221经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用方法概述:发展及研究内容n动态规划(dynamic programming)是运筹学的一个分是运筹学的一个分支，支，20世纪世纪50年代初美国数学家年代初美国数学家R.E.Bellman等人等人在研究在研究多阶段决策过程(multistep decision process)的的优化问题时，提出了著名的时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一，把多阶段过程转化为一系

2、列单阶段问题，逐个求解，创立了解决这类系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法过程优化问题的新方法动态规划。动态规划。n动态规划问世以来，在经济管理、生产调度、动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了工程技术和最优控制等方面得到了广泛的应用广泛的应用。例如最短路线、资源分配、设备更新等问题，例如最短路线、资源分配、设备更新等问题，用动态规划比用其它方法求解更为方便。用动态规划比用其它方法求解更为方便。12/28/20222经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务

3、的费用方法概述:发展及研究内容n虽然动态规划主要虽然动态规划主要用于求解以时间划分阶段的用于求解以时间划分阶段的动态过程的优化问题动态过程的优化问题，但是一些与时间无关的，但是一些与时间无关的静态规划静态规划(如线性规划、非线性规划如线性规划、非线性规划)，可以人可以人为地引进时间因素为地引进时间因素，把它视为多阶段决策过程，把它视为多阶段决策过程，也可以也可以用动态规划方法方便地求解用动态规划方法方便地求解。12/28/20223经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用方法概述:基本思想 n动态规划的思

4、想实质是动态规划的思想实质是分治思想和和解决冗余。n与分治法类似的是，将原问题分解成若干个子与分治法类似的是，将原问题分解成若干个子问题，先求解子问题，然后从这些子问题的解问题，先求解子问题，然后从这些子问题的解得到原问题的解。得到原问题的解。n与分治法不同的是，经分解的子问题往往不是与分治法不同的是，经分解的子问题往往不是互相独立的。若用分治法来解，有些共同部分互相独立的。若用分治法来解，有些共同部分（子问题或子子问题）被重复计算了很多次。（子问题或子子问题）被重复计算了很多次。n如果能够保存已解决的子问题的答案，在需要如果能够保存已解决的子问题的答案，在需要时再查找，这样就可以避免重复计算

5、、节省时时再查找，这样就可以避免重复计算、节省时间。动态规划法用一个表来记录所有已解的子间。动态规划法用一个表来记录所有已解的子问题的答案。问题的答案。n这就是动态规划法的基本思路。具体的动态规这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表方式。划算法多种多样，但它们具有相同的填表方式。12/28/20224经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用方法概述:求解步骤 1、找出最优解的性质，并刻画其结构特征；、找出最优解的性质，并刻画其结构特征；2、递归地定义最优值（写出动态规

6、划方程）；、递归地定义最优值（写出动态规划方程）；3、以自底向上的方式计算出最优值；、以自底向上的方式计算出最优值；4、根据计算最优值时记录的信息，构造最优解。、根据计算最优值时记录的信息，构造最优解。注：注：步骤步骤1-3是动态规划算法的基本步骤。在只需要是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤求出最优值的情形，步骤4可以省略；可以省略；若需要求出问题的一个最优解，则必须执行步骤若需要求出问题的一个最优解，则必须执行步骤4，步骤，步骤3中记录的信息是构造最优解的基础中记录的信息是构造最优解的基础12/28/20225经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加

7、赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用方法概述:适用条件 动态规划法的有效性依赖于问题本身所具有的动态规划法的有效性依赖于问题本身所具有的两个重要性质两个重要性质n最优子结构最优子结构：当问题的最优解包含了其子问题：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。的最优解时，称该问题具有最优子结构性质。n重叠子问题重叠子问题：在用递归算法自顶向下解问题时，：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了题被反复计算多次。动态规划算法正是利用

8、了这种子问题的重叠性质，对每一个子问题只解这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。尽可能多地利用这些子问题的解。12/28/20226经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用方法概述:最优性原理及举例 nBellman给出这个原理作为动态规划的适用条给出这个原理作为动态规划的适用条件，后来件，后来Morin在在19821982年证明了这只是一个充年证明了这只是一个充分条件而非必要条件。分条件而非必

9、要条件。Bellman的原定义如下：的原定义如下：n An optimal policy has the property that whatever the initial state and initial decision are,then remaining decisions must constitute an optimal policy with regard to the state resulting from first decision.n最优性原理又称为最优子结构性质最优性原理又称为最优子结构性质：n 如果有一决策序列包含有非最优的决策子序列，则该决如果有一决策序列包

10、含有非最优的决策子序列，则该决策序列一定不是最优的。即一个最优策略的子策略总是最策序列一定不是最优的。即一个最优策略的子策略总是最优的。优的。12/28/20227经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用方法概述:最优性原理及举例（续）n例例1：设：设G是一个有向加权图，则是一个有向加权图，则G从顶点从顶点i到顶点到顶点j之间的最短路径具有最优子结构之间的最短路径具有最优子结构性质。性质。n证明：（反证）证明：（反证）n 设设iipiq j是一条最短路径，但其中子是一条最短路径，但其中子路径路径ipiq

11、j不是最优的，假设最优的路径不是最优的，假设最优的路径为为ipiq jn 则我们重新构造一条路径：则我们重新构造一条路径：iipiq jn 显然该路径长度小于显然该路径长度小于iipiq j，与，与iipiq j是顶点是顶点i到顶点到顶点j的最短路径相矛盾的最短路径相矛盾.n 所以，原问题满足最优性原理。所以，原问题满足最优性原理。n 12/28/20228经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用方法概述:设计技巧n动态规划的设计技巧：阶段的划动态规划的设计技巧：阶段的划分和状态的表示；分和状态的表示；n

12、在动态规划的设计过程中，阶段在动态规划的设计过程中，阶段的划分和状态的表示是非常重要的划分和状态的表示是非常重要的两步，这两步会直接影响该问的两步，这两步会直接影响该问题的计算复杂性，有时候阶段划题的计算复杂性，有时候阶段划分或状态表示的不合理还会使得分或状态表示的不合理还会使得动态规划法不适用。动态规划法不适用。12/28/20229经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用方法概述:存在的问题 n空间溢出的问题，是动态规划解决问空间溢出的问题，是动态规划解决问题时一个普遍遇到的问题；题时一个普遍遇到的问

13、题；n动态规划需要很大的空间以存储中间动态规划需要很大的空间以存储中间产生的结果，这样可以使包含同一个产生的结果，这样可以使包含同一个子问题的所有问题共用一个子问题解，子问题的所有问题共用一个子问题解，从而体现动态规划的优越性，但这是从而体现动态规划的优越性，但这是以牺牲空间为代价的，为了有效地访以牺牲空间为代价的，为了有效地访问已有结果，数据也不易压缩存储，问已有结果，数据也不易压缩存储，因而空间矛盾是比较突出的。因而空间矛盾是比较突出的。12/28/202210经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用

14、l例例1：多段图的最短路问题：多段图的最短路问题多段图：设多段图：设G=是一个有向连通图，是一个有向连通图，其中其中|V|=n,|E|=m,V有划分有划分V1,V2,Vk，这里这里V1=s,s称为源点，称为源点，Vk=t,t称为称为终点，其中终点，其中k 2。对于每条有向边。对于每条有向边 E都存在都存在Vi V，使得，使得u Vi和和v Vi+1,其中其中1ik且每条边且每条边均均附有代价附有代价C(u,v)，则称，则称G是一个是一个k段图。段图。12/28/202211经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服

15、务的费用123456789101112s97324212711118654356425V1V2V3V4V5t12/28/202212经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用l最短路：从源点最短路：从源点s到终点到终点t的整条路上的的整条路上的代价之和为最小。代价之和为最小。每个子集每个子集Vi构成图中的一段。由于构成图中的一段。由于E的的约束，每条从约束，每条从s到到t的路径都是从第一段的路径都是从第一段开始，然后顺次经过第开始，然后顺次经过第2段，第段，第3段，段，最后在第，最后在第k段终止。对于每条从

16、段终止。对于每条从s到到t的的路径，可以把它看成在路径，可以把它看成在k-2个阶段中做出个阶段中做出的某个决策序列的相应结果。的某个决策序列的相应结果。12/28/202213经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用l假设假设s,v2,v3,vk-1,t是一条从是一条从s到到t的最短的最短路径，还假定从源点路径，还假定从源点s（初始状态）开始，已做初始状态）开始，已做出了到结点出了到结点v2的决策（初始决策），因此的决策（初始决策），因此v2就是就是初始决策所产生的状态。如果把初始决策所产生的状态。如果把

17、v2看成是原问题看成是原问题的一个子问题的初始状态，解这个子问题就是的一个子问题的初始状态，解这个子问题就是找出一条由找出一条由v2到到t的最短路径。这条路径显然是的最短路径。这条路径显然是 v2,v3,vk-1,t，否则设否则设v2,q3,qk-1,t是一条由是一条由v2到到t的更短路径，则的更短路径，则s,v2,q3,qk-1,t是一条比路径是一条比路径s,v2,v3,vk-1,t 更短的由更短的由s到到t的路径，与的路径，与假设矛盾，故最优化原理成立。假设矛盾，故最优化原理成立。12/28/202214经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿

18、的金额为消费者购买商品的价款或接受服务的费用cost(i,j)=minC(j,r)+cost(i+1,r)rVi+1 EjrtViVi+1最短最短最短最短向前处理法：设向前处理法：设P(i,j)是从是从Vi中的点中的点j到到t的一条最短路，的一条最短路，cost(i,j)是这条路线的是这条路线的耗费。由后向前推算，得到耗费。由后向前推算，得到12/28/202215经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用123456789101112s97324212711118654356425V1V2V3V4V5tc

19、ost(4,9)=4cost(i,j)=minC(j,r)+cost(i+1,r)cost(4,10)=2 cost(4,11)=5cost(3,6)=min6+cost(4,9),5+cost(4,10)=min6+4,5+2=7从第从第3段的顶点段的顶点6到到t的最短路径是的最短路径是6-10-t5+212/28/202216经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用123456789101112s97324212711118654356425V1V2V3V4V5tcost(3,7)=min4+cost

20、(4,9),3+cost(4,10)=min4+4,3+2=5从第从第3段的顶点段的顶点7到到t的最短路径是的最短路径是7-10-t cost(3,8)=7从第从第3段的顶点段的顶点8到到t的最短路径是的最短路径是8-10-t12/28/202217经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用123456789101112s97324212711118654356425V1V2V3V4V5tcost(2,2)=7 从第从第2段顶点段顶点2到到t的最短路是的最短路是2-7-10-tcost(2,3)=9从第从第

21、2段顶点段顶点3到到t的最短路是的最短路是3-6-10-tcost(2,4)=18从第从第2段顶点段顶点4到到t的最短路是的最短路是4-8-10-tcost(2,5)=15从第从第2段顶点段顶点5到到t的最短路是的最短路是5-8-10-tcost(1,1)=16 从第从第1段顶点段顶点1到到t的最短路径由两条：的最短路径由两条：1-2-7-10-t和和1-3-6-10-t12/28/202218经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用从从s到到t的一条最短路径的代价为的一条最短路径的代价为16。用用D(i

22、,j)表示使表示使C(j,r)+cost(i+1,r)取得最小值取得最小值的的r，则在上述求解过程中同时得到：则在上述求解过程中同时得到：D(3,6)=10,D(3,7)=10,D(3,8)=10D(2,2)=7,D(2,3)=6,D(2,4)=8D(2,5)=8,D(1,1)=2设从设从s到到t的最短路径为的最短路径为s,w2,w3,wk-1,t则有则有w2=D(1,1)=2w3=D(2,D(1,1)=D(2,2)=7w4=D(3,D(2,D(1,1)=D(3,D(2,2)=D(3,7)=10所以这条路径是1-2-7-10-t所以这条路径是所以这条路径是1-2-7-10-t12/28/202

23、219经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用为了便于描述算法，对一个为了便于描述算法，对一个k段图的顶点，按段图的顶点，按段的顺序给它的每个顶点编号。设图中有段的顺序给它的每个顶点编号。设图中有n个个顶点，则编号为顶点，则编号为1，2，n。首先，给首先，给s编为编为1号；然后给号；然后给V2中的各个顶点分别编为中的各个顶点分别编为2，3，|V2|+1号；以此类推，最后号；以此类推，最后t编号为编号为n。这样编号使这样编号使Vi+1中的任何顶点的编号大于中的任何顶点的编号大于Vi中中所有顶点的编号。所有顶

24、点的编号。于是，可以按于是，可以按n-1,n-2,1的顺序计算出的顺序计算出cost(i,j)和和D(i,j)。算法中可以利用顺序编号算法中可以利用顺序编号的特点，而不再考虑顶点所在的段。的特点，而不再考虑顶点所在的段。12/28/202220经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用设顶点的编号已知，边已知及边的代价函设顶点的编号已知，边已知及边的代价函数数C(i,j)已知。用已知。用costi表示顶点表示顶点i到到t的最小的最小代价，代价，1i n。用。用Di表示从顶点表示从顶点i到到t的最的最短路径上

25、顶点短路径上顶点i的后继顶点号，用的后继顶点号，用Pi表示表示最短路径经过第最短路径经过第i级的顶点号，级的顶点号，1i k12/28/202221经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用求两点间最短路径的算法：求两点间最短路径的算法：Procedure Fgraph1.for i 1 to n costi 0；2.for j=n-1 step 1 to 1 do 3.找顶点找顶点r,使使 E,且且C(j,r)+costr最小；最小；4.costjC(j,r)+costr;5.Dj r;6.P1 1;Pk

26、 n;7.for j=2 to k-1 do Pj DPj-1 O(n+|E|)12/28/202222经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用123456789101112s97324212711118654356425V1V2V3V4V5t（从前）向后：设从前）向后：设BPij是从源点是从源点s到到Vi中顶点中顶点j的最小成本路径，的最小成本路径，bcost(i,j)是这是这条路径的代价条路径的代价bcost(i,j)=minbcost(i-1,r)+C(r,j)r Vi-1 E12/28/20222

27、3经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用l格路问题：求从起点格路问题：求从起点O(0,0)到终点到终点E(m,n)的最短路。则分别用穷举法和动态的最短路。则分别用穷举法和动态规划法的加法次数和比较次数各是多少？规划法的加法次数和比较次数各是多少？E(m,n)O(0,0)xy12/28/202224经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用E(m,n)O(0,0)xy12/28/202225经营者提供商品或者服务有欺诈

28、行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用E(m,n)O(0,0)xymn个点个点 12/28/202226经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用l例例2：货郎担问题：货郎担问题12431052091289 13156810 10 15 205 9 106 13 128 8 9 v1 v2v3v4v1 v2 v3 v412/28/202227经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买

29、商品的价款或接受服务的费用不失一般性，考虑以结点不失一般性，考虑以结点1为起点和终为起点和终点的一条哈密顿回路。每一条这样的路点的一条哈密顿回路。每一条这样的路线都由一条边线都由一条边和一条由结点和一条由结点k到结到结点点1的路径组成，其中的路径组成，其中kV-1,而这条而这条由结点由结点k到结点到结点1的路径通过的路径通过V-1，k的的每个结点各一次。如果这条周游路线是每个结点各一次。如果这条周游路线是最优的，则这条由结点最优的，则这条由结点k到结点到结点1的路径的路径必定是通过必定是通过V-1，k的每个结点各一次的每个结点各一次的由的由k到到1的最短路径。的最短路径。12/28/20222

30、8经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用l设设T(i,S)是由结点是由结点 i出发，经过结点集出发，经过结点集S中中每个结点各一次并回到初始结点每个结点各一次并回到初始结点1的一条最的一条最短路径长度，则短路径长度，则T(1,V-1)就是一条最优的就是一条最优的周游路线长度。动态规划模型：周游路线长度。动态规划模型：T(1,V-1)=mind1k+T(k,V-1,k)2 k n T(i,s)=mindij+T(j,S-j)j S,i S12/28/202229经营者提供商品或者服务有欺诈行为的，应当按照

31、消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 10 15 205 9 106 13 128 8 9 v1 v2v3v4v1 v2 v3 v4T(1,2,3,4)=mind12+T(2,3,4),d13+T(3,2,4),d14+T(4,2,3)T(2,3,4)=mind23+T(3,4),d24+T(4,3)T(3,4)=d34+T(4,)T(4,)=d4112/28/202230经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用T(1,2,3,4)T(2,3,4)T(3,

32、2,4)T(4,2,3)T(3,4)T(4,3)T(2,4)T(4,2)T(2,3)T(3,2)T(4,)T(3,)T(4,)T(2,)T(3,)T(4,)12/28/202231经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用T(1,2,3,4,5)T(2,3,4,5)T(3,2,4,5)T(3,4,5)T(4,5)T(5,4)T(2,4,5)T(5,4)T(4,5)12/28/202232经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服

33、务的费用T(1,2,3,4)T(2,3,4)T(3,2,4)T(4,2,3)T(3,4)T(4,3)T(2,4)T(4,2)T(2,3)T(3,2)T(4,)T(3,)T(4,)T(2,)T(3,)T(4,)1(n-1)C(n-2,n-2)(n-1)C(n-2,n-3)第第k层层(n-1)C(n-2,n-k-1)n-1一共一共 层层12/28/202233经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第第k层层(n-1)C(n-2,n-k-1)；一共；一共n-1层层1+(n-1)C(n-2,n-k-1)k1n-

34、1k1=1+(n-1)C(n-2,)n-1=1+(n-1)C(n-2,)k0n-2k-1k2n=1+C(n,1)+C(n,2)+C(n,n)=C(n,k)k0n=1+(n-1)2n-2空间复杂性空间复杂性O(n2n)12/28/202234经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用矩阵链乘法n问题描述问题描述n加括号的方案数加括号的方案数 n动态规划法动态规划法 12/28/202235经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服

35、务的费用矩阵链乘法:问题描述给定给定n个矩阵个矩阵A1,A2,An，Ai的维数为的维数为pi-1pi(1in),要求计算连乘积要求计算连乘积A1A2 An由于矩阵乘法满足结合率，所以可以由于矩阵乘法满足结合率，所以可以有许多不同的计算次序，这种计算次有许多不同的计算次序，这种计算次序可以用加括号的方式来确定。序可以用加括号的方式来确定。比如：A1,A2,A3,A4 (A(A1 1(A A2 2(A A3 3(A(A4 4)(A)(A1 1(A A2 2 A A3 3)A)A4 4)(A (A1 1 A A2 2)()(A A3 3 A A4 4)(A)(A1 1(A A2 2 A A3 3)A

36、 A4 4)(A (A1 1 A A2 2)A A3 3)A)A4 4)12/28/202236经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用不同的计算次序有不同的计算量不同的计算次序有不同的计算量注：注：1.设设Apq,Aqr两矩阵相乘，普通乘法的次数两矩阵相乘，普通乘法的次数为为pqr2.加括号对乘法次数的影响加括号对乘法次数的影响 如：如：A10100B1005C550 (AB)C):101005+10550=7500次次 (A(BC):100550+1010050=75000次次12/28/202237

37、经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用穷举法：穷举法：将将n个矩阵从第个矩阵从第k和第和第k+1处隔开，对二个子序处隔开，对二个子序列再分别加括号，则可以得到下面递归式：列再分别加括号，则可以得到下面递归式：因此，穷举法不是一个有效算法12/28/202238经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用计算m14过程如下：自顶向下递归求解最优解的值如A3:4被计算了2次，保存下来可以节省许多时间12/28/202239

38、经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用matrixChain(int p,int m,int s)int n=p.length-1;for(int i=1;i=n;i+)mii=0;for(int r=2;r=n;r+)for(int i=1;i=n-r+1;i+)int j=i+r-1;mij=mi+1j+pi-1*pi*pj;sij=i;for(int k=i+1;k j;k+)int t=mik+mk+1j+pi-1*pk*pj;if(t mij)mij=t;sij=k;12/28/202240经

39、营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用矩阵链乘法:动态规划算法 n自底向上记忆化方式求解自底向上记忆化方式求解mij -计算方向：计算方向：j m11,m12,m13,m1n m22,m23,m2n i mn-1n-1,mn-1n mnn 12/28/202241经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用矩阵链乘法:动态规划算法（续）n计算示例：计算示例：行行 x 列列A130 x35A235x15A315x5A4 5

40、x10A510 x20A620 x256555443333i33322333111654321sj6543i21 6 54321mj00000015125500035001000537525007501050071254375262511875937578751575012/28/202242经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用矩阵链乘法:动态规划算法（续）n计算示例：计算示例：行行 x 列列A130 x35A235x15A315x5A4 5x10A510 x20A620 x256555443333i

41、33322333111654321sjResult(A1(A2A3)(A4A5)A6)traceback(int i,int j)if(i=j)return;traceback(i,sij);traceback(sij+1,j);print(“A”,i,”*A”,sij);print(“and A”,sij+1,”*A”,j);12/28/202243经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用1.矩阵链乘问题满足最优性原理 记Ai:j为AiAi+1Aj链乘的一个最优括号方案，设Ai:j的最优次序中含有二个子

42、链Ai:k和Ak+1:n，则Ai:k和Ak+1:n也是最优的。（反证可得）2.矩阵链乘的子问题空间：Ai:j,1ijn A1:1,A1:2,A1,:3,A1:n A2:2,A2:3,A2:n An-1:n-1,An-1,n An,n 12/28/202244经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用l递归求解最优解的值 记mij为计算Ai:j的最少乘法数，则原问题的最优值为 m1n(AiAi+1Ak)pi-1pk(Ak+1Ak+2Aj)pkpj12/28/202245经营者提供商品或者服务有欺诈行为的，应当

43、按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用依据递归式自底向上计算。在计算过程中，保存已经解决的子问题答案。A1,A2,A3,A4,A5,A6m25 =min m22+m35+p1p2p5 m23+m45+p1p3p5 m24+m55+p1p4p512/28/202246经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用A1=(aij)35 40 A2=(aij)40 20 A3=(aij)20 10 A4=(aij)10 15m13 =min m12 =m23 =40

44、 20 108000m34 =20 10 15300035 40 2028000m11+m23+35 4010,m12+m33+35 2010 m24m14m11m12m13m14m22m23m24m33m34m44 j=1 2 3 4i=1 2 3 412/28/202247经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用最长公共子序列若给定序列若给定序列X=x1,x2,xm，则另一序列则另一序列Z=z1,z2,zk，是，是X的子序列是指存在一个严的子序列是指存在一个严格递增下标序列格递增下标序列i1,i2,i

45、k使得对于所有使得对于所有j=1,2,k有：有：zj=xij。例如，序列例如，序列Z=B，C，D，B是序列是序列X=A，B，C，B，D，A，B的子序列，的子序列，相应的递增下标序列为相应的递增下标序列为2，3，5，7。给定给定2个序列个序列X和和Y，当另一序列当另一序列Z既是既是X的子序列的子序列又是又是Y的子序列时，称的子序列时，称Z是序列是序列X和和Y的的公共子序列。给定给定2 2个序列个序列X=xX=x1 1,x,x2 2,x xm m 和和Y=yY=y1 1,y,y2 2,y yn n，找出找出X X和和Y Y的最长公共子序列。的最长公共子序列。12/28/202248经营者提供商品或

46、者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用最长公共子序列的结构设序列设序列X=x1,x2,xm和和Y=y1,y2,yn的最长公共子序列的最长公共子序列为为Z=z1,z2,zk，则，则(1)若若xm=yn，则，则zk=xm=yn，且，且zk-1是是xm-1和和yn-1的最长公共子序的最长公共子序列。列。(2)若若xmyn且且zkxm，则，则Z是是xm-1和和Y的最长公共子序列。的最长公共子序列。(3)若若xmyn且且zkyn，则，则Z是是X和和yn-1的最长公共子序列。的最长公共子序列。由此可见，2个序列的最长公共子序列包含

47、了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结最优子结构性质构性质。12/28/202249经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用子问题的递归结构由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用cij记录序列和的最长公共子序列的长度。其中，Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其他情况下，由最优子结构性质可建立递归关系如下：12/28/202250经营者提供商品或者服务有欺诈行

48、为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用Algorithm lcsLength(x,y,b)1:mx.length-1;2:ny.length-1;3:ci0=0;c0i=0;4:for(int i=1;i=m;i+)5:for(int j=1;j=cij-1)10:cij=ci-1j;11:bij=2;12:else 13:cij=cij-1;14:bij=3;15:16:return cmn;17:12/28/202251经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的

49、价款或接受服务的费用0-1背包问题:问题描述及举例 n问题描述问题描述n举例：举例：w=(w1,w2,w3)=(2,3,4),v=(v1,v2,v3)=(1,2,5),n=3,c=6,求求Knap(1,3,6)取取x=(1,0,1)时，时，12/28/202252经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n0-1背包问题满足最优性原理背包问题满足最优性原理n证明：设证明：设(y1,y2,yn)是是Knap(1,n,c)的一个最优解，则的一个最优解，则n(y2,yn)是是Knap(2,n,c-w1y1)子问题

50、的一个最优解。子问题的一个最优解。n若不然，设若不然，设(z2,zn)是是Knap(2,n,c-w1y1)的最优解，因此的最优解，因此有有说明(y1,z2,zn)是Knap(1,n,c)的一个更优解，矛盾。12/28/202253经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用0-1背包问题:递归关系 n考虑子问题：考虑子问题：Knap(i,n,j)jc(假设假设c,wi取整数取整数)设其最优值为设其最优值为m(i,j),即即m(i,j)是背是背包容量为包容量为j,可选物品为可选物品为i,i+1,n的的0-1背包