第25讲-动态规划.pptVIP

动 态 规 划;回顾：;简单的背包问题(0-1背包) 设有ｎ种物品，每种物品有一个重量及一个价值。同时有一个背包，最大载重量为M，今从ｎ种物品中选取若干件，使其重量的和小于等于m，而价值的和为最大。N=100,M1000.输入数据：第一行两个数：物品总数Ｎ，背包载重量M；两个数用空格分隔；第二行N个数,为Ｎ种物品重量Wi(1000)；两个数用空格分隔；第三行N个数,为N种物品价值Vi(1000); 两个数用空格分隔；输出数据： 总价值；;;用f[i,j]表示在第１到第i件物品中装入重量为j的背包获得的最大价值．;主程序：; 动态规划（Dynamic Programming 简称DP）算法是信息学奥赛中重点考察的基本算法，几乎每年的试题中都有动态规划的题目。 ;最短路径问题 ;阶段1;定义f(i)为i点到E的最短距离，d(i,j)为节点i到节点j的距离。 ;动态规划的术语： 1、 阶段： 把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于按一定的次序去求解，过程不同，阶段数就可能不同．描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k表示。 阶段的划分一般根据时间和空间来划分的。 2、状态： 某一阶段的出发位置成为状态，通常一个阶段有多个状态。 状态通常可以用一个或一组数来描述，称为状态变量。 3、决策： 一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。描述决策的变量称决策变量 4、策略和最优策略  所有阶段的决策有序组合构成一个策略。 最优效果的策略叫最优策略。;fk[x]=min{fk+1[yi]+d [x,yi]};fk[x]=min{fk-1[yi]+d [yi,x]};结合题目看方程：顺推和倒推;一般形式： U：状态； X：策略;一般形式： U：状态； X：策略;动态规划问题的特征 : 1、最优子结构 如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。也称最优化原理。 最优子结构也可以理解为“整体最优则局部最优”。反之不一定成立。 2、重叠子问题 在解决整个问题时，要先解决其子问题，要解决这些子问题，又要先解决他们的子子问题 ……。而这些子子问题又不是相互独立的，有很多是重复的，这些重复的子子问题称为重叠子问题。 动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表中，以后再遇到这些相同问题时直接查表就可以，而不需要再重复计算，每次查表的时间为常数。 ;3、无后效性原则 “已经求得的状态值，不受未求的那些状态的影响”。 后面阶段的状态只受前面阶段的状态的影响。 对于任意两个状态，只能单向的进行转移。 某个状态一旦被求出，以后不再会发生变化（不受后面的影响）。 要求的状态在空间或时间上是有序的。;最优子结构、重叠子问题、无后效性;有后效性:D1;拓扑图（有向无环图） 无后效性;非拓扑图（可能有环） 有后效性 a?b?c ？ b?c?a？ ;动态规划的条件：无后效性、最优子问题; 1、找出最优解的性质，并刻画其结构特征； 2、递归地定义最优值（写出动态规划方程）； 3、以自底向上的方式计算出最优值； 记忆化有哪些信誉好的足球投注网站（树型）、递推 4、根据计算最优值时得到的信息，构造一个最优解。; 状态转移方程的构造是动态规划过程中最重要的一步,也是最难的一步.对于大多数的动态规划,寻找状态转移方程有一条十分高效的通道,就是寻找变化中的不变量（已经求得的值）. 定量处理的过程也就是决策实施的过程.;f[Un]=初始值； for k←n-1 downto 1 do {枚举阶段} for U取遍所有状态 do {枚举状态} for X取遍所有决策 do {枚举决策} f[Uk]=opt{f[Uk+1]+L[Uk,Xk]}；  //L[Uk,Xk]}：状态Uk通过策略Xk到达状态Uk+1的费用输出： f[U1]:目标 ;f[U1]=初始值； for k←2 to n do {枚举每一个阶段} for U取遍所有状态 do for X取遍所有决策 do f[Uk]=opt{f[Uk-1]+L[Uk-1,Xk-1]}}；