《动态规划法》PPT课件.ppt

《《动态规划法》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、#includeusingnamespacestd;intbinarysearch(inta[],constintx,intleft,intright,int&i,int&j){intmiddle;while(left<=right){middle=(left+right)/2;if(x==a[middle]){i=middle;j=middle;return1;}if(x>a[middle])left=middle+1;elseright=middle-1;}i=right;j=left;return0;}课后第一题voidmain(){inta

2、[6]={1,3,5,6,9,11};intx=4;inty=10;inti1,j1,i2,j2;binarysearch(a,x,0,5,i1,j1);binarysearch(a,y,0,5,i2,j2);for(intk=j1;k<=i2;k++)cout<

3、集必须满足某些事先给定的条件，这些条件称为约束条件，满足约束条件的解称为问题的可行解。满足约束条件的可行解可能不只一个，为了衡量这些可行解的优劣，事先给出一定的标准，这些标准通常以函数的形式给出，这些标准函数称为目标函数，使目标函数取得极值（极大或极小）的可行解称为最优解，这类问题就称为最优化问题。6.1.1最优化问题例：付款问题：超市的自动柜员机（POS机）要找给顾客数量最少的现金。假定POS机中有n张面值为pi(1≤i≤n)的货币，用集合P={p1,p2,…,pn}表示，如果POS机需支付的现金为A，那么，它必须从P中选取一个最小子集S，使得（式6.1）如果用向量

4、X=(x1,x2,…,xn)表示S中所选取的货币，则（式6.2）那么，POS机支付的现金必须满足（式6.3）并且（式6.4）在付款问题中，集合P是该问题的输入，满足式6.1的解称为可行解，式6.2是解的表现形式，因为向量X中有n个元素，每个元素的取值为0或1，所以，可以有2n个不同的向量，所有这些向量的全体构成该问题的解空间，式6.3是该问题的约束条件，式6.4是该问题的目标函数，使式6.4取得极小值的解称为该问题的最优解。6.1.2最优性原理对于一个具有n个输入的最优化问题，其求解过程往往可以划分为若干个阶段，每一阶段的决策仅依赖于前一阶段的状态，由决策所采取的动作

5、使状态发生转移，成为下一阶段决策的依据。从而，一个决策序列在不断变化的状态中产生。这个决策序列产生的过程称为多阶段决策过程。S0P1P2Pn多阶段决策过程S1S2Sn-1SnSn-1SnS1S0s1,1sn,knp1,1s1,k1p1,k1s1,r1………sn-1,kn-1pn,kn…pn-1,kn-1…动态规划的决策过程sn-1,1……sn-1,rn-1sn,1sn,rn……在每一阶段的决策中有一个赖以决策的策略或目标，这种策略或目标是由问题的性质和特点所确定，通常以函数的形式表示并具有递推关系，称为动态规划函数。多阶段决策过程满足最优性原理（OptimalPrin

6、ciple）：无论决策过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的当前状态，构成一个最优决策序列。如果一个问题满足最优性原理通常称此问题具有最优子结构性质。6.1.3动态规划法的设计思想动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。原问题的解原问题……填表子问题1子问题2子问题n动态规划法的求解过程

7、n=5时分治法计算斐波那契数的过程。F(5)F(4)F(3)F(3)F(2)F(2)F(1)F(2)F(1)F(1)F(0)F(1)F(0)F(1)F(0)例：计算斐波那契数：01234567890112358132134动态规划法求解斐波那契数F(9)的填表过程：注意到，计算F(n)是以计算它的两个重叠子问题F(n-1)和F(n-2)的形式来表达的，所以，可以设计一张表填入n+1个F(n)的值。用动态规划法求解的问题具有特征：能够分解为相互重叠的若干子问题；满足最优性原理（也称最优子结构性质）：该问题的最优解中也包含着其子问题的最优解。（用反证法）