文档介绍：动态规划最优化原理-10-14大榕树作为整个过程的最优策略具有这样的性质:即无论过去的状态和决策如何,对以前的决策所形成的状态而言,余下的诸决策必须构成最优策略。(无论过程的初始状态/初始决策是什么,其余决策活动必须相对于初始决策所产生的状态构成一个最优决策序列,才可能使整个决策活动构成最优决策序列。)简单地说,一个整体过程的最优策略的子策略一定是最优策略。利用这个原理,可以把多阶段决策问题的求解过程看成是一个连续的逆推过程。由后向前逐步推算。在求解时,各种状态前面的状态和决策,对后面的子问题,只不过相当于其初始条件而己,不影晌后面过程的最优策略。原理的证明可用反证法。在此把它略去。动态规划的求解方法-10-14大榕树是先把问题分成多个子问题(一般地每个子问题是互相关联和影响的),再依次研究逐个问题的决策。决策就是某个阶段的状态确定后,从该状态演变到下一阶段状态的选择。当全体子问题都解决时,整体问题也随之解决。用枚举的方法从所有可能的决策序列中去选取最优决策序列可能是较费时的笨拙的方法,但利用最优性原理去找出递推关系,再找最优决策序列就可能使得枚举数量大大下降,这就是动态规划方法设计算法的主要思路。动态规划的状态表示(一)-8-6大榕树一、引言问题求解技术,包括两个方面的内容:表示和搜索。在这两个方面的内容中,搜索是重点,表示是基础。不同的状态表示对搜索的效率会产生极大的影响。一个粗糙的状态表示可能使得搜索时要对状态变换进行更多的操作,而采取简洁的表示,搜索时进行的操作可能就显得方便、高效,甚至由于状态表示准确描述了问题的本质,给人以启示,从而找到更好的搜索技术。动态规划是求解问题的一个重要技术,它的状态表示在整个算法中有着举足轻重的作用,对整个算法的影响也远比其他搜索技术中的状态表示更为深刻。本文以实例对动态规划的状态表示进行一些讨论。二、动态规划对状态表示的要求在动态规划程序设计中,我们主要利用了问题的两个性质:最优子结构和子问题重叠。最优子结构指问题的最优解包含了子问题的最优解,它是动态规划方法可行的理论基础。而一个问题具有子问题重叠性质是指用递归算法自顶向下解这个问题时,并不总是产生新的子问题,有些子问题被重复求解多次。因为最优子结构性质,动态规划求问题最优解时,可以转化为求子问题的最优解,而对解决过的问题,动态规划则记录它的结果,当再次遇上已解决的问题,就可以直接利用结果。子问题重叠性质保证了这样做是有意义的。但一般的搜索技术,对于某个子问题不管是否已经解决过,只要遇上,就会再次对这个子问题进行求解。很明显,动态规划与一般搜索技术最大不同的地方就是记录了已求解过的问题的结果。这里包含了两个方面的内容:子问题的记录和子问题结果的记录。其中,子问题的记录是最重要,也是最为复杂的,它就是通常我们所说的状态表示。通常我们用一个数、一组数或一个向量来实现状态表示。但无论采取什么方法,从动态规划的原理来看,状态表示要满足两个要求:正确、合理描述子问题和描述的子问题满足最优子结构性质;从算法实现角度来看,状态表示必须能够用基本数据结构实现并且能满足空间要求。下面通过两个问题来阐述动态规划对状态表示的要求。问题一:存在一个数字三角形,从顶到底有多条路径,每一步可沿左斜线向下或沿右斜线向下。路径所经过的数字之和称为路径得分,要求求出最小路径得分。例:11232332332338123812最小路径得分=6状态表示1-1最自然的作法是用一元组(X)描述问题,D(X)表示从顶到达第X层的得分。但是一元组(X)描述的子问题不能满足最优子结构性质,因为D(X)的最优解可能不包含子问题D(X-I)的最优解。这样,动态规划方法是无法在状态表示1-1上应用的。状态表示1-2用二元组D(X,Y)描述问题,D(X,Y)表示到达第X层第Y个位置时的得分,那么D(X,Y)的最优解包含了子问题D(X-1,Y)或D(X-1,Y-1)的最优解,状态转移方程为D(X,Y)=Max{D(X-1,Y),D(X-1,Y-1)}+A[X,Y]D(1,1)=A[1,1]这样,最小路径得分可以通过比较底层的分数求得。一般情况下,我们找到的状态表示应能刻划子问题的特征,困难的是如何找到描述的子问题能满足最优子结构性质的状态表示,而这一点恰恰是决定该问题能否应用动态规划方法的重要因素。状态表示1-1描述的问题是正确的,但它不能满足最优子结构性质,使得无法用它来建立动态规划数学模型。状态分析的过程实际上是分析问题最优子结构的过程,不同的状态表示正是从不同的角度去试图刻划问题的最优子结构。只有状态表示描述的子问题能满足最优子结构性质,我们才能在此基础上正确的建立起动态规划数学模型。问题二:在茫茫大海中,有一座荒芜人烟的小岛,它有着肥沃的土地,终年四季如春。在许多年的沉寂后,移民者终于