第4章动态规划概要.ppt

第4章 动态规划 一、动态规划的基本思想 动态规划算法通常用于求解具有某种最优性质的问题。 在这类问题中，可能会有许多可行解。 每一个解都对应于一个值，我们希望找到具有最优值的解。 基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。 如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。 我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。 这就是动态规划法的基本思路。 具体的动态规划算法多种多样，但它们具有相同的填表格式。 二、设计动态规划法的步骤 找出最优解的性质，并刻画其结构特征； 递归地定义最优值（写出动态规划方程）； 以自底向上的方式计算出最优值； 根据计算最优值时得到的信息，构造一个最优解。 步骤1～3是动态规划算法的基本步骤。 在只需要求出最优值的情形，步骤4可以省略； 若需要求出问题的一个最优解，则必须执行步骤4。 三、动态规划问题的特征 动态规划算法的有效性依赖于问题本身所具有的两个重要性质： 最优子结构： 当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。 重叠子问题： 在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。 * 4.1 最长公共子序列 若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。 例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。 给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。 例如，序列Z={B，C，B}是序列X={A，B，C，B，D，A，B}和Y={B，D，C，A，B，A}的公共子序列。 例如，序列Z={B，C，B，A}也是序列X={A，B，C，B，D，A，B}和Y={B，D，C，A，B，A}的公共子序列。 给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。 * 4.1.1 最长公共子序列的结构 例如，序列Z={B，C，B，A}是序列X={A，B，C，B，D，A，B}和Y={B，D，C，A，B，A}的最长公共子序列。 设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ，则 若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。 若xm≠yn且zk≠xm，则Z是xm-1和Y的最长公共子序列。 若xm≠yn且zk≠yn，则Z是X和yn-1的最长公共子序列。（为什么没有若xm≠yn且zk≠xm且zk≠yn，则Z是xm-1和Yn-1的最长公共子序列呢？） 2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。 最长公共子序列问题具有最优子结构性质。 4.1.2 子问题的递归结构 由最长公共子序列问题的最优子结构性质可知，要找出X和Y的最长公共子序列，可按以下方式递归地进行： 当xm＝yn时，找出Xm－1和Yn－1的最长公共子序列，然后在其尾部加上xm（＝yn）即可得X和Y的一个最长公共子序列。 当xm≠yn时，必须解两个子问题，即找出Xm－1和Y的一个最长公共子序列及X和Yn－1的一个最长公共子序列。这两个公共子序列中较长者为X和Y的一个最长公共子序列。 例如，序列X={A，B，C，B}和Y={B，D，C}的最长公共子序列。 (用树来描述...) * 用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。 Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。 当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时C[i][j]=0。 其它情况下，由最优子结构性质可建立递归关系如下： * 填表过程： 例如，序列X7={A，B，C，B，D，A，B}，Y6={B，D，C，A，B，A}。 * 0 1 2 3 4 5 6 yi B D C A B A 0 xi 1 A 2 B 3 C 4 B 5 D 6 A 7 B i j 数组c 4.1.3 计算最优值 计算最长公共子