noip动态规划教学PPT.ppt

动态程序设计,动态规划,与递归程序相类，将对问题求解分解为对子问题求解；不同之处在于把子问题的解存起来，用空间换时间。 例：fibonacci数 f(0)=0; f(1)=1; f(n)=f(n-1)+f(n-2); 递归: f(n-1)和f(n-2)分别求到底一次 动态规划：用数组将前n-1个数存起来，每次只用一个加法 fn = fn-1+fn-2 即可。,例 最短路径问题。下图中给出一个地图，地图中每个顶点代表一个城市，两个城市之间的连线表示道路，连线上的数值代表道路的长度。现在，想从城市a到城市e，怎样走路程最短，最短路程的长度是多少？ 现在，我们想从城市a到达城市e。怎样走才能使得路径最短，最短路径的长度是多少？,设：disx为城市x到城市e的最短路径长度（x表示任意一个城市）;mapi,j表示i，j两个城市间的距离，若mapi,j=0，则两个城市不通。 我们可以使用回溯来计算disx:,var s:未访问的城市聚合； function search(who):integer; 求城市who与城市e的最短距离 var i,j,min:integer; begin if who=e then search:=0 else begin min:=maxint; for i取遍所有城市 do if (mapwho,i0) and (i in s) then begin s:=s-i; 城市i已访问 j:=mapwho,i+search(i); 计算城市e至城市who的路径长度 s:=s+i; 恢复城市i未访问状态 if jmin then min:=j; 若城市e至城市who的路径长度为目前最短，则记下 end; search:=min; 返回城市e至城市的最短路径长度 end; begin s:=所有城市； disa:=search(a); 计算城市a城市e的最短路径长度 writeln(dista); end.,这个程序的效率如何呢？我们可以看到，每次除了已经访问过的城市外，其他城市都要，所以时间复杂度为w(n!)，这是一个“指数级”的算法。那么还有没有效率更高的解题方法呢？ 首先，我们来观察上述算法。在求b1到e的最短路径的时候，先求出从c2到e的最短路径；而在求b2到e的最短路径的时候，又求了一遍从c2到e的最短路径。也就是说，从c2到e的最短路径求了两遍。两样可以发现，在求从c1、c2到e的最短路径的过程中，从d1到e的最短路径也被求了两遍。而在整个过程中，从d1到e的最短路径被求了四遍，这是多么大的一个浪费啊！如果在求解的过程中，同时将求得的最短路径的距离“记录在案”，以便将来随时调用，则可以避免这种重复计算。至此，一个新的思路产生了，即由后往前依次推出每个dis值，直到推出disa为止。,阶段的划分具有如下性质： 阶段i的取值只与阶段i+1有关，阶段i+1的取值只对阶段i的取值产生影响； 每个阶段的顺序是确定的，不可以调换任两个阶段的顺序。,我们从阶段4的城市e出发，按照阶段的顺序倒推至阶段0的城市a。在求解的各个阶段，利用了k阶段与k+1阶段之间的如下关系 diskx= dis4e=0 k=4，3，0，其中diskx指k阶段的城市x。,我们从阶段4的城市e出发，按照阶段的顺序倒推至阶段0的城市a。在求解的各个阶段，利用了k阶段与k+1阶段之间的如下关系 diskx= dis4e=0 k=4，3，0，其中diskx指k阶段的城市x。,我们从阶段4的城市e出发，按照阶段的顺序倒推至阶段0的城市a。在求解的各个阶段，利用了k阶段与k+1阶段之间的如下关系 diskx= dis4e=0 k=4，3，0，其中diskx指k阶段的城市x。,2,3,我们从阶段4的城市e出发，按照阶段的顺序倒推至阶段0的城市a。在求解的各个阶段，利用了k阶段与k+1阶段之间的如下关系 diskx= dis4e=0 k=4，3，0，其中diskx指k阶段的城市x。,我们从阶段4的城市e出发，按照阶段的顺序倒推至阶段0的城市a。在求解的各个阶段，利用了k阶段与k+1阶段之间的如下关系 diskx= dis4e=0 k=4，3，0，其中diskx指k阶段的城市x。,由此得出程序 : dise0； for k3 downto 0 do for x取遍k阶段的所有城市do begin disx； for y取遍k+1阶段的所有城市do if disy+mapx,ydisx then disxdisy+mapx,y； end；for 输出disa；,由常识知，最短路有一个重要特性：最短路上的任一（后部）子路也是最短的。即 若 a-b3-c1-d1-e 是 a-e 最短， 则 b3-c1-d1-e 是 b3-e 最短路， c1-d1-e 也是c1-e 最短路. 利用最短路的这一特性，构造寻找 a-e 最短路的方法，即为： 从最后一段开始，即 d-e 段开始，用由后向前逐步逆推的方法，求出各点到 e 的最短路线，最后求出从 a 点到 e 点的最短路逆序法。,（动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。）,基本概念,一、阶段和状态 1、阶段k：将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便按次序去求每阶段的解。设阶段变量为k。阶段是问题的属性。多阶段决策问题中通常存在着若干个阶段。在一般情况下，阶段是和时间有关的，但是在很多问题中，阶段和时间并无直接关系。从阶段的定义中，可以看出阶段的两个特点，一是“相互联系”，二是“次序”。阶段之间相互联系的方式是通过状态和状态转移体现的。,2、状态sk： 各阶段开始时的客观条件叫做状态。 描述各阶段状态的变量称为状态变量，常用sk表示第k阶段的状态变量，状态变量sk的取值集合称为状态集合。用sk表示。例如s2=c1,c2,c3,c4。 状态是阶段的属性。每个条件通常包含若干个状态，用以描述问题发展到这个阶段时所处在的一种客观情况。s1=b1,b2。 每个阶段的状态都是由以前阶段的状态以某种方式“变化”而来，这种“变化”称为状态转移。 应用动态程序设计方法的一个重要条件。那就是将各阶段按照一定的次序排列好之后，对于阶段i的状态只能由阶段i+1的状态通过状态转移方程得来，与其它状态没有关系，尤其是与未发生的状态没有关系。换句话说，每个状态都是“过去历史的一个完整总结”。这就是无后效性。,二、决策和策略 1、决策uk(sk)：当阶段的状态取定以后，就可以做出不同的决定，从而确定下一阶段的状态，这种决定称为决策。表示决策的变量称为决策变量，常用uk(sk)表示第k阶段当状态为sk时的决策变量。在实际问题中，决策变量的取值往往限制在一定范围内，我们称此范围为允许决策集合。常用dk(sk)表示第k阶段从状态sk出发的允许决策集合。显然有uk(sk) dk(sk) 决策是问题解的属性。决策的目的就是“确定下一阶段的状态”。从阶段1的b1状态出发有三条路，也就是三个决策，分别导向阶段2的c1,c2,c3三个状态，即d1(b1)=c1,c2,c3。 动态程序设计方法中本阶段的状态往往是对上一阶段某状态进行相应决策的结果，由第k段的状态sk和决策uk确定第k+1段的状态sk+1的过程叫状态转移。 状态转移规律的形式化表示sk+1=tk(sk，uk)称为状态转移方程。决策的目的是转移状态，状态转移的途径是决策。,2、策略pl，n：各段决策确定后，整个问题的决策序列就构成一个策略，用p1，n=u1(s1)，u2(s2)， un(sn)表示。对每个实际问题，可供选择的策略有一定范围，称为允许策略集合，记作p1，n，使整个问题达到最有效果的策略就是最优策略。 运用动态程序设计方法的一个前提。即这个过程的最优策略应具有这样的性质：无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略。这就是最优化原理。简言之，就是最优策略的子策略也是最优策略。,最优化原理与无后效性,该问题的解必须符合最优化原理是前提。 这是因为是否符合最优化原理是一个问题的本质特征。对于不满足最优化原理的一个多阶段决策问题，整体上的最优策略p1,n同任何一个阶段k上的决策uk或任何一组阶段k1,，k2上的子策略pk1,k2都不存在任何关系。如果要对这样的问题进行动态程序设计的话，我们从一开始所作的划分阶段等如努力进都将是徒劳的。 问题的求解过程必须具备无后效性的特点是条件。 因为动态程序设计方法是按次序去求每阶段的解，如果一个问题有后效性，那么这样的次序便是不合理的。但是，我们可以通过重新划分阶段或选定状态以及增加状态变量个数等手段，来使得问题满足无后效性这个条件。说到底，还是要确定一个“序”。,最优指标函数和状态转移方程 用于衡量所选定策略优劣的数量指标称为指标函数，指标函数记fk(sk)，它表示从第k段状态sk采用策略p*k,n到过程终止时的最佳效益值。 最优指标函数其实就是我们真正关心的问题的解。在上例中，f1(b1)就表示从b1点到终点e的最短路径长度。我们求解的最终目标就是f0(a)。 最优指标函数的求法一般是一个从目标状态出发的递推公式，称为状态转移议程：,其中sk是第k段的某个状态，uk是从sk出发的允许决策集合dk(sk)中的一个决策，tk(sk,uk)是定义在数值x和决策uk上的一个函数，而函数opt表示最优化，根据具体问题分别表示为max或min。例中最短路径问题的状态转移方程就是,（边界条件）,1、确定问题的研究对象，即状态。选定的状态必须满足如下两点： 状态必须完全描述出事物的性质，两个不同事物的状态是不同的； 必须存在状态与状态之间的“转移方程”，以便我们可以由初始状态逐渐转化为目标状态。 由于状态是描述事物性质的量，所以我们应该以上述要求为标准，具体情况具体分析。 2、划分阶段，确定阶段之间的状态转移方程； 3、考察此问题可否用动态程序设计方法解决，即问题是否具备最优子结构和无后效性的特征 4、如果发现问题目前不能用动态程序设计方法解决，则调整阶段的划分和状态的定义，使其具备最优子结构和无后效性的特征。,使用动态程序设计方法解题的步骤,程序设计的一般格式 ； for kn-1 downto 1 do 枚举阶段 for s取遍所有状态 do for u取遍所有决策 do ； 这里是一种从目标状态往回推的逆序求法，适用于目标状态确定的问题。而很多试题是确定了初始状态的。当然，对于初始状态确定的问题，我们也可以采用从初始状态出发往前推的顺序求法。事实上，这种方法对我们来说要更为直观、更易设计一些，从而更多地出现在我们的解题过程中。 由于动态程序设计方法的模式性比较强，因此应该把主要精力放在状态定义、阶段划分和状态转移方程的设计上。一旦这些问题解决了，事情成功了一大半。,动态程序设计方法之所以效率高，是因为它把已经做过的工作结果存储起来，每次需要的时候，直接读入即可，不做已经做过的工作。当然，对于同一个问题，由于各人看问题的角度不同，对阶段、状态和状态转移方式的理解可能不一样，因此有些状态转移方程仍存在冗余运算。是否充分利用信息是提高时间效率的关键。此外，充分利用信息并不一定要以牺牲空间为代价，只要方法得当，同样可以优化算法的空间复杂度。,动态规划的实质是分治思想和解决冗余，因此它与分治和贪心类似，它们都是将问题的实例分解为更小的、相似的子问题，但是动态规划又有自己的特点。 贪心法的当前选择可能要依赖于已经作出的选择，但不依赖于还未做出的选择和子问题，因此它的特征是由顶向下，一步一步地做出贪心的选择，但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解。相比而言，动态规划则可以处理不具有贪心实质的问题。,在用分治法解决问题时，由于子问题的数目往往是问题规模的指数函数，因此对时间的消耗太大。动态规划的思想在于，如果各个子问题不是独立的，不同的子问题的个数只是多项式数数量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是：用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。,其实动态规划的思想是对贪心算法和分治法的一种折衷，它所解决的问题往往不具有贪心算法的实质，但是各个子问题又不是完全零散的，这时候我们用一定的空间来换取时间，就可以提高解题的效率。 动态规划是对最优化问题的一种新的算法设计方法。由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题有不同特色的表示方式。,数字三角形问题,图3示出了一个数字三角形宝塔。数字三角形中的数字为不超过100的整数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走 假设三角形行数100，编程求解从最顶层走到最底层的一条路径，使得沿着该路径所经过的数字的总和最大，输出最大值。 输人数据：由文件输入数据，第一行是三角形的行数n，以后的n行分别是从最顶层到最底层的每一层中的数字。,数字三角形问题,采用动态规划中的顺推解法。按三角形的行划分阶段，若行数为 n，则可把问题看做一个n-1个阶段的决策问题。从始点出发，依顺向求出第n-1阶段、第n-2阶段第1阶段中各决策点至底层的最佳路径。 设： fi,j为从第i阶段中第j个状态的点uk至三角形顶点有一条最佳路径，该路径所经过的数字的总和最大； 由于每一次决策有两个选择，或沿左斜线向下，或沿右斜线向下，因此设： ifi+1,jfi+1,j+1 then fi,j:=fi+1,j+ai,j else fi,j:=fi+1,j+1+ai,j;,状态转移方程：fi,j:=max(fi+1,j+1, fi+1,j)+ai,j;,program triple; const fin=d:input.txt; fon=d:output.txt; maxn=100; var f,a:array1maxn,1maxn of integer; n:integer; procedure init; procedure main; procedure print; begin init; main; print; end.,procedure init; var i,j:integer; begin assign(input,fin);reset(input); readln(n); for i:=1 to n do begin for j:=1 to i do read(ai,j); readln; end; close(input); end; procedure print; var i,ans:integer; begin assign(output,fon); rewrite(output); writeln(f1,1); close(output); end;,procedure main; var i,j:integer; begin for i:=1 to n do fn,i:=an,i; for i:=n-1 downto 1 do for j:=1 to i do if fi+1,jfi+1,j+1 then fi,j:=fi+1,j+ai,j else fi,j:=fi+1,j+1+ai,j; end;,program triple; const fin=d:input.txt; fon=d:output.txt; maxn=100; var f,a:array1maxn,1maxn of integer; n:integer; procedure init; var i,j:integer; begin assign(input,fin);reset(input); readln(n); for i:=1 to n do begin for j:=1 to i do read(ai,j); readln; end; close(input); end; procedure main; var i,j:integer; begin for i:=1 to n do fn,i:=an,i; for i:=n-1 downto 1 do for j:=1 to i do if fi+1,jfi+1,j+1 then fi,j:=fi+1,j+ai,j else fi,j:=fi+1,j+1+ai,j; end; procedure print; var i,ans:integer; begin assign(output,fon); rewrite(output); writeln(f1,1); close(output); end; begin init; main; print; end.,例2,给定数列a1,a2,an，求最长递减子序列。 输入数据 n和n个整数（nai； 边界条件：s0=0； answer=maxsi, 1=i=n。,a: 76 8 9 6 20 19 18 69 3,s: 1 2 2 3 2 3 4 2 5,算法分析,ai=数列的第i个数； si=以ai结尾的最长递减子序列长度；,a: 76 8 9 6 20 19 18 69 3,s: 1 2 2 3 2 3 4 2 5,状态转移方程：si=maxsk+1 0ai； 边界条件：s0=0； answer=maxsi, 1=i=n。,a: 76 8 9 6 20 19 18 69 3,s: 1 2 2 3 2 3 4 2 5,for i:=1 to n do read(ai); a0:=maxint; fillchar(s,sizeof(s),0); answer:=0; for i:=1 to n do begin for k:=0 to i-1 do if (akai) and (sk+1si) then si:=sk+1; if (sianswer) then answer:=si; end; writeln(answer);,si=maxsk+1 0ai； 边界条件：s0=0； answer=maxsi, 1=i=n。,program ex6_2_1; var n,i,k,answr:integer; a:array01000 of integer; s:array01000 of integer; answer:integer; begin read(n); for i:=1 to n do read(ai); a0:=maxint; s0:=0; answer:=0; for i:=1 to n do begin si:=0; for k:=0 to i-1 do if (akai) and (sk+1si) then si:=sk+1; if (sianswer) then answer:=si; end; writeln(answer); end.,program ex6_2_2; var n,i,k,answer:integer; a:array11000 of integer; s,last:array01000 of integer; size:integer; q:array11000 of integer; begin read(n); for i:=1 to n do read(ai); s0:=0; answer:=0; for i:=1 to n do begin si:=0; for k:=0 to i-1 do if (k=0) or (akai) and (sk+1si) then begin si:=sk+1; lasti:=k; end; end;,for i:=1 to n do if (sianswer) then begin answer:=si; k:=i; end; size:=0