算法设计动态规划稿概要.pptx

算法设计及其应用算法设计及其应用第六章:动态规划算法(国际大学生程序设计竞赛辅导教程）(国际大学生程序设计竞赛例题解（三）)动态规划概述l运筹学运筹学(Operations Research)是系统工程最是系统工程最重要的理论基础之一重要的理论基础之一,运筹学所研究的问题可运筹学所研究的问题可简单地归结为简单地归结为:“依照给定条件和目标依照给定条件和目标,从众多从众多方案中选择最佳方案方案中选择最佳方案.”而动态规划是运筹学的而动态规划是运筹学的重要分支之一重要分支之一,它是解决多阶段决策过程最优它是解决多阶段决策过程最优化的一种方法化的一种方法.动态规划概述l动态规划简单的来说就是：采用分治的策略把动态规划简单的来说就是：采用分治的策略把求最优解问题分解为求若干个子问题的最优解，求最优解问题分解为求若干个子问题的最优解，子问题也递归的分解为子问题的组合，通过递子问题也递归的分解为子问题的组合，通过递归递推等方法，把原问题最优解与局部子问题归递推等方法，把原问题最优解与局部子问题最优解联系起来，以求最后的解。这些局部子最优解联系起来，以求最后的解。这些局部子问题之间可能有重叠，就是某个子问题可能需问题之间可能有重叠，就是某个子问题可能需要求解多次，因此需要将子问题及其解记录下要求解多次，因此需要将子问题及其解记录下来，这样对每个子问题只需求解一次，从而提来，这样对每个子问题只需求解一次，从而提高了效率。高了效率。动态规划概述l一般来说，寻找最优解的算法都具有指一般来说，寻找最优解的算法都具有指数时间的复杂度，因此算法的优化显得数时间的复杂度，因此算法的优化显得十分重要；但是有一类特殊的最优化问十分重要；但是有一类特殊的最优化问题，我们通常可以找到具有多项式时间题，我们通常可以找到具有多项式时间的复杂度的算法，这种方法就是我们下的复杂度的算法，这种方法就是我们下面要介绍的动态规划。面要介绍的动态规划。动态规划的常用名词l(1)状态状态(state)对于一个问题，所有可能到达的情况（包括初始情况对于一个问题，所有可能到达的情况（包括初始情况和目标情况）都称为这个问题的一个状态。和目标情况）都称为这个问题的一个状态。l(2)状态变量状态变量(sk)对每个状态对每个状态k关联一个状态变量关联一个状态变量sk，它的值表示状态，它的值表示状态k所对应的问题的当前解值。所对应的问题的当前解值。l(3)决策决策(decision)决策是一种选择，对于每一个状态而言，你都可以选决策是一种选择，对于每一个状态而言，你都可以选择某一种路线或方法，从而到达下一个状态。择某一种路线或方法，从而到达下一个状态。动态规划的常用名词l(4)决策变量决策变量(dk)在状态在状态k下的决策变量下的决策变量dk的值表示对状态的值表示对状态k当当前所做出的决策。前所做出的决策。l(5)策略策略策略是一个决策的集合，在我们解决问题的时策略是一个决策的集合，在我们解决问题的时候，我们将一系列决策记录下来，就是一个策候，我们将一系列决策记录下来，就是一个策略，其中满足某些最优条件的策略称之为最优略，其中满足某些最优条件的策略称之为最优策略。策略。动态规划的常用名词l(6)状态转移函数状态转移函数(t)从一个状态到另一个状态，可以依据一定的规则来前从一个状态到另一个状态，可以依据一定的规则来前进。我们用一个函数进。我们用一个函数t来描述这样的规则，它将状态来描述这样的规则，它将状态i和决策变量和决策变量di映射到另一个状态映射到另一个状态j，记为，记为t(i,di)=j。l(7)状态转移方程状态转移方程(f)状态转移方程状态转移方程f描述了状态变量之间的数学关系。一般描述了状态变量之间的数学关系。一般来说，与最优化问题相应，状态转移方程表示来说，与最优化问题相应，状态转移方程表示si的值的值最优化的条件，或者说是状态最优化的条件，或者说是状态i所对应问题的最优解值所对应问题的最优解值的计算公式，用代数式表示就是：的计算公式，用代数式表示就是：lsi=f(sj,dj)|i=t(j,dj)，对决策变量，对决策变量dj所有可行的取值所有可行的取值)l1951年美国数学家年美国数学家R.Bellman等人，根据一等人，根据一类多阶段问题的特点，把多阶段决策问题变换类多阶段问题的特点，把多阶段决策问题变换为一系列互相联系的单阶段问题，然后逐个加为一系列互相联系的单阶段问题，然后逐个加以解决。一些静态模型，只要人为地引进以解决。一些静态模型，只要人为地引进“时时间间”因素，分成时段，就可以转化成多阶段的因素，分成时段，就可以转化成多阶段的动态模型，用动态规划方法去处理。动态模型，用动态规划方法去处理。最优化原理最优化原理l解决这类问题的解决这类问题的“最优化原理最优化原理”（Principle of optimality）：）：“一个过程的最优决策具一个过程的最优决策具有这样的性质：即无论其初始状态和初始决策有这样的性质：即无论其初始状态和初始决策如何，其今后诸策略对以第一个决策所形成的如何，其今后诸策略对以第一个决策所形成的状态作为初始状态的过程而言，必须构成最优状态作为初始状态的过程而言，必须构成最优策略策略”。l简言之，一个最优策略的子策略，对于它的初简言之，一个最优策略的子策略，对于它的初态和终态而言也必是最优的。态和终态而言也必是最优的。最优化原理l这个这个“最优化原理最优化原理”如果用数学化一点的语言来描述如果用数学化一点的语言来描述的话，就是：假设为了解决某一优化问题，需要依次的话，就是：假设为了解决某一优化问题，需要依次作出作出n个决策个决策D1，D2，Dn，如若这个决策序列是，如若这个决策序列是最优的，对于任何一个整数最优的，对于任何一个整数k，1kn，不论前面，不论前面k个个决策是怎样的，以后的最优决策只取决于由前面决策决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策所确定的当前状态，即以后的决策Dk+1，Dk+2，Dn也是最优的。也是最优的。l最优化原理是动态规划的基础。任何一个问题，如果最优化原理是动态规划的基础。任何一个问题，如果失去了这个最优化原理的支持，就不可能用动态规划失去了这个最优化原理的支持，就不可能用动态规划方法计算。方法计算。何为动态规划l动态规划是运筹学的一个分支。与其说动态规划是一动态规划是运筹学的一个分支。与其说动态规划是一种算法，不如说是一种思维方法来得更贴切。因为动种算法，不如说是一种思维方法来得更贴切。因为动态规划没有固定的框架，即便是应用到同一道题上，态规划没有固定的框架，即便是应用到同一道题上，也可以建立多种形式的求解算法。许多隐式图上的算也可以建立多种形式的求解算法。许多隐式图上的算法，例如求单源最短路径的法，例如求单源最短路径的Dijkstra算法、广度优先算法、广度优先搜索算法，都渗透着动态规划的思想。还有许多数学搜索算法，都渗透着动态规划的思想。还有许多数学问题，表面上看起来与动态规划风马牛不相及，但是问题，表面上看起来与动态规划风马牛不相及，但是其求解思想与动态规划是完全一致的。其求解思想与动态规划是完全一致的。动态规划适于解决何种问题l只适于解决一定条件的最优策略问题。只适于解决一定条件的最优策略问题。l所谓所谓“满足一定条件满足一定条件”主要指：主要指：l(1)状态必须满足最优化原理；状态必须满足最优化原理；l(2)状态必须满足无后效性。状态必须满足无后效性。l所谓的无后效性是指：所谓的无后效性是指：“过去的决策只能过去的决策只能通过当前状态影响未来的发展，当前的状态是通过当前状态影响未来的发展，当前的状态是对以往决策的总结对以往决策的总结”。动态规划适于解决何种问题l这个特征说明什么呢？它说明动态规划适这个特征说明什么呢？它说明动态规划适于解决当前决策和过去状态无关的问题。状态，于解决当前决策和过去状态无关的问题。状态，出现在策略的任何一个位置，它的地位都是相出现在策略的任何一个位置，它的地位都是相同的，都可以实施同样的决策。这就是无后效同的，都可以实施同样的决策。这就是无后效性的内涵。性的内涵。采用动态规划解题的优点l动动态态规规划划的的最最大大优优势势在在于于它它具具有有极极高的效率高的效率;l可获一系列解可获一系列解;l算法清晰简便，程序易编易调等。算法清晰简便，程序易编易调等。动态规划的逆向思维法l逆逆向向思思维维法法是是指指从从问问题题目目标标状状态态出出发发倒倒推推回回初初始始状状态态或或边边界界状状态态的的思思维维方方法法。如如果果原原问问题题可可以以分分解解成成几几个个本本质质相相同同、规规模模较较小小的的问问题题，很很自自然然就就会会联联想想到到从从逆逆向向思思维维的的角角度度寻寻求求问问题题的的解决。解决。l动动态态规规划划不不是是分分治治法法：关关键键在在于于分分解解出出来来的的各各个子问题的性质不同。个子问题的性质不同。动态规划的逆向思维法l分治法要求各个子问题是独立的（即不包含公共的子分治法要求各个子问题是独立的（即不包含公共的子子问题），因此一旦递归地求出各个子问题的解后，子问题），因此一旦递归地求出各个子问题的解后，便可自下而上地将子问题的解合并成原问题的解。便可自下而上地将子问题的解合并成原问题的解。l如果各子问题是不独立的，那么分治法就要做许多不如果各子问题是不独立的，那么分治法就要做许多不必要的工作，重复地解公共的子子问题。必要的工作，重复地解公共的子子问题。l动态规划与分治法的不同之处在于动态规划允许这些动态规划与分治法的不同之处在于动态规划允许这些子问题不独立（即各子问题可包含公共的子子问题），子问题不独立（即各子问题可包含公共的子子问题），它对每个子问题只解一次，并将结果保存起来，避免它对每个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。这就是动态规划高效的一每次碰到时都要重复计算。这就是动态规划高效的一个原因。个原因。动态规划的逆向思维法l动态规划的逆向思维法的要点可归纳为动态规划的逆向思维法的要点可归纳为以下三个步骤：以下三个步骤：l(1)分析最优值的结构，刻划其结构特征；分析最优值的结构，刻划其结构特征；l(2)递归地定义最优值；递归地定义最优值；l(3)按自底向上或自顶向下记忆化的方式按自底向上或自顶向下记忆化的方式计算最优值。计算最优值。递归编程递归编程 l动态规划算法经常使用递归编程来实现动态规划算法经常使用递归编程来实现,所以理解好所以理解好递归编程对掌握动态规划算法非常重要递归编程对掌握动态规划算法非常重要.我们先从一我们先从一个例子讲起个例子讲起.l例例6.1.1 一个楼梯有一个楼梯有20级级,每次走每次走1级或级或2级级,从底走到从底走到顶一共有多少种走法顶一共有多少种走法?l分析：假设从底走到第分析：假设从底走到第n级的走法有级的走法有f(n)种种,走到第走到第n级级有两个方法有两个方法,一个是从第一个是从第(n-1)级走级走1步步,另一个是从第另一个是从第(n-2)级走级走2步步,前者有前者有f(n-1)种方法种方法,后者有后者有f(n-2)种方种方法法,所以所以f(n)=f(n-1)+f(n-2),另外另外f(0)=1,f(1)=1.编写递编写递归程序如下归程序如下:递归编程递归编程l#includelint f(int n)l if(n=0|n=1)return 1;l else return f(n-1)+f(n-2);llvoid main()lcoutf(20)endl;l 递归编程递归编程l这个程序把计算这个程序把计算f(n)归结为归结为f(n-1)和和f(n-2)的计算的计算,对简对简单的情况单的情况,即即n为为0或或1的时候直接给出结果的时候直接给出结果.但要理解但要理解好这个程序还必须了解程序变量的类型好这个程序还必须了解程序变量的类型,简单的来分简单的来分,变量分为局部变量和全局变量变量分为局部变量和全局变量,局部变量在定义的时局部变量在定义的时候分配在内存候分配在内存,在离开作用域的时候被撤销在离开作用域的时候被撤销,而全局变而全局变量在程序的整个运行过程中都有效量在程序的整个运行过程中都有效.在递归程序中尤在递归程序中尤其要注意局部变量和全局变量的区别其要注意局部变量和全局变量的区别,前者在每次递前者在每次递归调用的时候都会在内存分配不停的内存单元归调用的时候都会在内存分配不停的内存单元,并赋并赋以不同的值以不同的值,在递归函数调用结束后撤销该内存单元在递归函数调用结束后撤销该内存单元,后者在递归调用过程中始终只有一个内存单元后者在递归调用过程中始终只有一个内存单元.例如例如,以上程序中的以上程序中的n就是一个局部变量就是一个局部变量,每次递归调用每次递归调用f(n)的时候的时候,都会在内存分配都会在内存分配n的新的内存单元的新的内存单元.递归编程递归编程l把程序程序6.1.1改写为:l#includelint f(int n)lint result;l if(n=0|n=1)result=1;l int temp1=f(n-1);lint temp2=f(n-2);lresult=temp1+temp2;lreturn result;l递归编程递归编程lvoid main()lcoutf(20)endl;l ln,result,temp1,temp2都是局部变量,每次递归调用的时候都会在内存分配新的内存单元,计算f(20)和计算f(19)有不同的内存单元,赋以不同的值,互不影响.递归编程递归编程l在递归程序中使用全局变量的一个例子：l#includelint n;lint result;l/计算给定的n值的函数值f(n),并把结果存放在result变量里,调用函数前后nl/值保持不变lvoid f()l if(n=0|n=1)l result=1;l return;l递归编程递归编程l int temp;ln-;l/计算f(n-1)lf();ltemp=result;ln-;l/计算f(n-2)lf();ltemp+=result;l/回复n值ln+=2;l/把结果存放到result变量递归编程递归编程l下面再给出若干个递归程序,以增加对递归编程的理解.l例例6.1.2 输入n,输出前n个自然数的所有排列,例如输入3,则输出l1 2 3l1 3 2l2 1 3l2 3 1l3 2 1l3 1 2 l其实现见程序6.1.4。递归编程递归编程l#includelvoid swap(int&x,int&y)l int temp=x;l x=y;l y=temp;llint n;lint data100;递归编程递归编程lvoid solve(int t)l if(t=n)l /输出一个排列l for(int i=1;i=n;i+)l coutdatai;l l coutn;l for(int i=1;i=n;i+)l datai=i;l l solve(1);l 递归编程递归编程lresult=temp;llvoid main()l n=20;lcoutresultendl;l 递归编程递归编程l例例6.1.3 计算两个自然数的最大公约数。其实现见程序6.1.5。l#includelint gcd(int x,int y)l return y=0?x:gcd(y,x%y);llvoid main()l int x,y;lcinxy;lcoutgcd(x,y)endl;l 递归编程递归编程l例例6.1.4 求若干个数的最大数.l最简单的方法就是通过循环比较找出最大值,但我们也可以用递归的方法来求出最大值。其实现见程序6.1.6。递归编程递归编程l#include lint data100;lint getMax(int left,int right)l if(left=right)l return dataleft;l l int t1=getMax(left,(left+right)/2);l int t2=getMax(left+right)/2+1,right);l return t1=t2?t1:t2;l递归编程递归编程lvoid main()l int n;l cinn;l for(int i=1;i datai;l l coutgetMax(1,n)1时，f(n)=f(n-1)+f(n-2)；l否则，f(0)=1,f(1)=1。l这些子问题是有重叠的，即求解某个问题的时候，某些子问题可能需求求解多次，例如，我们在求解f(5)的时候，其问题求解树为：动态规划基本原理动态规划基本原理l图图6.2.1 例6.1.1的求解树动态规划基本原理动态规划基本原理l很多子问题被重复的求解，例如f(2),被求解了3次。l当某个问题符合以上两点，我们就可以考虑用动态规划的方式来高效地求解，就是把子问题及其解记录下来，这样每个子问题只需求解一次，从而提高了效率。下面我们直接给出两个用动态规划方法求解例例6.1.1的程序：动态规划基本原理动态规划基本原理l#includel/用于保存f(n)的结果lint result100;l/求解f(n)lint f(int n)l /如果问题已经被求解，那么之间返回结果l if(resultn=0)return resultn;动态规划基本原理动态规划基本原理l/计算解并把结果保存到resultn里l int res;l if(n=0|n=1)res=1;l else res=f(n-1)+f(n-2);l resultn=res;l return res;l动态规划基本原理动态规划基本原理l#includel/用于保存f(n)的结果lint f100;lvoid main()l /先置初始解l f0=1;l f1=1;动态规划基本原理动态规划基本原理l/递推的求解各个子问题l for(int i=2;i=20;i+)l fi=fi-1+fi-2;l l /输出解l coutf20endl;动态规划基本原理动态规划基本原理l程序程序6.2.1采用递归的结构，每当遇到一个子问题，先判断该子问题是否已经被求解过，如果是，则直接返回已经记录下来的结果，否则才递归的求解下去，最后把结果保存起来，这样下次就不用再求解了。l程序程序6.2.2采用递推的结构，先求解小的子问题，然后求解大的子问题，在求解每个子问题的时候，它的子问题都是已经被求解过的，所以可以直接组合子问题的解。动态规划基本原理动态规划基本原理l这两个程序虽然采用不同的结构，但每个子问题都只求解了一次，而如果采用程序程序6.1.1,求解f(n)大约需要求解2n个子问题，所以采用动态规划的方法确实能大大的提高效率。l发现子问题的过程就是用分治的方法来分析问题的过程，这需求多做题目增加经验，但发现了子问题后，如何记录子问题，如何实现动态规划算法，却是有一些常用的方法，下面将分作介绍。作业作业l1342l1264l1233l1221l1222l1210l1120l1047