动态规划基础部分教学PPT.ppt

动态规划-基础部分,动态规划的重要性：,涉及动态规划的各种竞赛题越来越多，每一年的noi几乎都至少有一道题目需要用动态规划的方法来解决 。,什么是动态规划？,动态规划是解决多阶段决策问题的一 种方法。,多阶段决策问题,如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采取措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。,例 下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由a-e。求a-e的最省费用。,如图从a到e共分为4个阶段： 第一阶段从a到b 第二阶段从b到c 第三阶段从c到d 第四阶段从d到e。 除起点a和终点e外，其它各点既是上一阶段的终点又是下一阶段的起点。,概念 状态（state）：表示事物的性质，是描述“动态规划”中的“单元”的量。亦是每一阶段求解过程的出发点。 阶段（stage）：阶段是一些性质相近，可以同时处理的状态集合，或者说，阶段只是标识那些处理方法相同、处理顺序无关的状态。 决策（decision）：每个阶段做出的某种选择性的行动，是程序所需要完成的选择。 状态转移方程：用数学公式描述与阶段相关的状态间的演变规律。,上一阶段的状态,决策,下一阶段的状态,（1）d1，d2是第一次输入的结点。他们到e都只有一种费用，在d1框上面标5，d2框上面标2。目前无法定下，那一个点将在全程最优策略的路径上。第二阶段计算中，5，2都应分别参加计算。 （2）c1，c2，c3是第二次输入结点，他们到d1，d2各有两种费用。此时应计算c1，c2，c3分别到e的最少费用。 c1的决策路径是 min（c1d1），（c1d2）。计算结果是c1+d1+e，在c1框上面标为8。 同理c2的决策路径计算结果是c2+d2+e，在c2框上面标为7。 同理c3的决策路径计算结果是c3+d2+e，在c3框上面标为12。 此时也无法定下第一，二阶段的城市那二个将在整体的最优决策路径上。,实现过程：,实现过程：,（3）第三次输入结点为b1，b2，b3，而决策输出结点可能为c1，c2，c3。仿前计算可得bl，b2，b3的决策路径为如下情况。 bl:b1c1费用 12+8=20， 路径:b1+c1+d1+e b2:b2c1费用 6+8=14， 路径:b2+c1+d1+e b3:b2c2费用 12+7=19， 路径:b3+c2+d2+e 此时也无法定下第一，二，三阶段的城市那三个将在整体的最优决策路径上。,实现过程：,（4）第四次输入结点为a，决策输出结点可能为b1，b2，b3。同理可得决策路径为 a：ab2，费用5+14=19，路径 a+b2+c1+d1+e。,在上例的多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。,应用动态规划要注意阶段的划分是关键，必须依据题意分析，寻求合理的划分阶段(子问题)方法。而每个子问题是一个比原问题简单得多的优化问题。而且每个子问题的求解中，均利用它的一个后部子问题的最优化结果，直到最后一个子问题所得最优解，它就是原问题的最优解。,记忆化算法在求解的时候还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。这种方法综合了搜索和动态规划两方面的优点，因而还是很有实用价值的。,动态规划的适用条件 ：,必须满足以下两个条件 (1)状态必须满足最优化原理； 动态规划的最优化原理是无论过去的状态和决策如何，对前面的决策所形成的当前状态而言，余下的诸决策必须构成最优策略。可以通俗地理解为子问题的局部最优将导致整个问题的全局最优。在上例中例题1最短路径问题中，a到e的最优路径上的任一点到终点e的路径也必然是该点到终点e的一条最优路径，满足最优化原理。即：问题的最优解包含了其中一个子问题的最优解。,如图，已知一个有向图，求一条从最左边的点走到最右边点的方案（只能从左往右走），使得所经过的权值和除以4的余数最小。,mod 4余数最小问题,设所有点从左至右编号为14，min（i）表示前i个点的最优值，很容易得出一个方程： min(i)=min(min(i-1)+numi-1,1) mod 4, min(i-1)+numi-1,2) mod 4 通过这个方程可以求出一条路径为（2+3+1）mod 4=2 但最优值实际上是 （2+1+1）mod 4=0。 为什么会出错呢？,分析,(2).无后效性 动态规划的某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。具体地说，如果一个问题被划分各个阶段之后，阶段 i 中的状态只能由阶段 i+1 中的状态通过状态转移方程得来，与其他状态没有关系，特别是与未发生的状态。,动态规划的适用条件 ：,题目分析：请问“拔河比赛”可以用动态规划解题吗？ 拔河比赛（tug） 问题描述 一个学校举行拔河比赛，所有的人被分成了两组，每个人必须（且只能够）在其中的一组，要求两个组的人数相差不能超过1，且两个组内的所有人体重加起来尽可能地接近。 输入 输入数据的第1行是一个n，表示参加拔河比赛的总人数，n=100，接下来的n行表示第1到第n个人的体重，每个人的体重都是整数（1=weight=450）。 输出 输出数据应该包含两个整数：分别是两个组的所有人的体重和，用一个空格隔开。注意如果这两个数不相等，则请把小的放在前面输出。,动态规划问题的一般解题步骤, 初始状态决策决策决策结束状态 1、判断问题是否具有最优子结构性质，若不具备则 不能用动态规划。 2、把问题分成若干个子问题（分阶段）。分治？ 3、建立状态转移方程（递推公式）。 4、找出边界条件。（可以顺推可以逆推）递推？ 5、将已知边界值带入方程。 6、递推求解。,目的是得到一个最优解（方案）,动态规划的实质是分治思想和解决冗余 （记忆化算法），因此，动态规划是一种将问题分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优（最大或最小）解。若存在多个最优解的话，它只取其中的一个。,1、递推的边界条件一般很明显，而动态规划的边界条件比较隐蔽，容易被忽视； 2、递推的数学性一般较强，而动态规划的数学性相对较弱； 3、递推一般不划分阶段，而动态规划一般有较为明显的阶段； 4、动态规划往往是用来求一个最优值，而一般的递推往往是用来计数或是求一个值。,动态规划和一般递推的不同点？,动态规划和一般递推的相同点？,无后效性和有边界条件。,动态规划的正向思维法是指从初始状态或边界状态出发，利用某种规则不断到达新的状态，直到问题目标状态的方法,逆向思维法是指从问题目标状态出发倒推回初始状态或边界状态的思维方法。如果原问题可以分解成几个本质相同、规模较小的问题，很自然就会联想到从逆向思维的角度寻求问题的解决。,动态规划递推方法：,例题：数字三角形（ioi1994） 问题描述 如下所示为一个数字三角形： 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。 每一步可沿直线向下或右斜线向下走； 1三角形行数100； 三角形中的数字为整数0，1，99； 问题输入 输入文件tringle.in，其中第一行为一个自然数，表示数字三角形的行数n，接下来的n行表示一个数字三角形。 问题输出 输出文件tringle.out，仅有一行包含一个整数，表示要求的最大总和。,输入样例 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 输出样例 30,方法1：穷举？,方法2：贪心？,方法3： 动态规划？,状态转移方程： fi,j=maxfi-1,j,fi-1,j-1 +ai,j （2=i=n,1=j=i）,样例程序,算法分析：我们假设从顶至数字三角形的某一位置的所有路径中，所经过的数字的总和最大的那条路径，我们称之为该位置的最大路径。由于问题规定每一步只能沿直线向下或沿斜线向右下走，若要走到某一位置，则其前一位置必为其左上方或正上方两个位置之一，由此可知，当前位置的最优路径必与其左上方或正上方两个位置的最优路径有关，且来自于其中更优的一个。 阶段：每一行数据 状态：每一个位置路径和 决策：取最大路径 我们可以用一个二维数组a记录数字三角形中的数，ai,j表示数字三角形中第i行第j列的数，fi,j为 第i行第j列上点到起点的最大和。,随堂练习： 利用另外一种递推方法解决“数字三角形”问题,按三角形的行划分阶段，若行数为 n，则可把问题看做一个n-1个阶段的决策问题。先求出第n-1阶段(第n-1行上各点)到第n行的的最大和，再依次求出第n-2阶段、第n-3阶段第1阶段(起始点)各决策点至第n行的最佳路径。 设：fi,j为从第i阶段中的点j至第n行的最大的数字和； 则: fn,j=an,j 1=j=n fi,j=maxai,j+fi+1,j,ai,j+fi+1,j+1 1=j=i. f1,1即为所求。,逆推,动态规划算法和贪心算法区别： 1）在动态规划算法中，以自底向上的方式来利用最优子结构，也就是说，首先找到子问题的最优解，解决子问题，然后找到问题的一个最优解。 2）在贪心算法中，以自顶向下的方式使用最优子结构，也就是说，贪心算法会先做出选择，在当时看起来是最优的选择，然后再求解一个结果子问题，而不是先求解子问题的最优解，然后再做出选择。 两者的不同点： 1 贪心算法作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。 2 动态规划算法的全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有局部最优解；,对比样例：,7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 如果我不给出一个点只能走到下或者右下这个限制条件，我们可以从这一层的一个点走到下一层的任意一个点，求解方法？,为什么加上一个条件后，就变成了动态规划呢？,贪心可以保证一次最优，而动规可以保证整体最优。 贪心是局部的最优解，动规是整体的最优解。,输入：一行四个数据，分别表示b点坐标和马的坐标。 输出：一个数据，表示所有的路径条数。,程序,假设用fi