五大算法思想（五）动态规划及常见例子 |
您所在的位置：网站首页 › 农业产品有哪些举个例子 › 五大算法思想（五）动态规划及常见例子 |
五大算法思想（五）动态规划及常见例子
|
文章目录
一、理论基础1.1 适用场景1.2 使用步骤1.3 常用方法-填表法1.4 经典例子
二、常见例子2.1 矩阵连乘2.2 走金字塔2.3 最长公共子序列2.4 最长递增子序列2.5 0-1背包2.6 完全背包
一、理论基础
动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推的方式去解决。动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子阶段，按顺序求解子阶段。与分治不同的是，在动态规划过程中，前一子问题的解，为后一子问题的求解提供了有用的信息，也就是说前后阶段的问题求解存在依赖关系。在求解任一子问题时，通过决策保留那些有可能达到最优的局部解。依次解决各子问题，最后一个子问题就是初始问题的解。 以上都是官方说法，在实际运用动态规划时，每个人都有不同的理解。此处以爬楼梯问题为例，来介绍一下一种解决动态规划问题的思路。爬楼梯问题的描述： 一个人爬楼梯，一次只能爬一阶或两阶，当总共有n阶楼梯时，有多少种爬法。 本文中解决动态规划问题的思路是，确定动态规划四要素： 1、问题的阶段 在该问题中，在楼梯的每层台阶上，都有着不同数量的往上爬完楼梯的可能性，也就是说每层台阶其实就意味着不同的阶段。找阶段的过程，其实就是拆分问题的过程。假如楼梯总共有10层，每次只能向上爬1层或2层楼梯。那么解决这个问题的最后一个阶段就是可以理解为从第10层楼梯往上爬（因为每次只能爬1或2层，所以这个阶段只能爬到8层或9层），再细说的话，也就是：从10层爬到9层或8层是解决该问题的第一阶段。 也许有人会问，为什么要这样划分阶段？首先，在动态规划中，大问题不能像分治那样，拆分成完全相同的子问题，各子阶段是有依赖关系的，所以需要确定一个解决问题的“起点”和“终点”。而在动态规划中，“从底向上”的方案常常使用，所以此处就是从最底部（10）开始，作为解决问题的“起点”。2、每个阶段的状态 在第一步中，已经对问题划分了阶段，在划分阶段后，要解决问题，还需要做的是定义阶段的状态。在该问题中，我们确定解决问题的第一个阶段是：在第10层楼梯时。在动态规划问题中，和子问题相关的各个变量的一组取值,称之为一个"状态",一个状态对应一个或多个子问题所谓的在某个状态的值,这个就是状态所对应的子问题的解,所有状态的集合称为"状态空间"。这个状态的解释比较官方，其实每个阶段的状态可以简单理解为：要用动态规划思想解决问题，需要在某个阶段定义的变量值，这个变量可以是一个变量值，也可以是一组变量值。 在动态规划中，实际运用到的常常是一维数组dp[ ]或二维数组dp[ ][ ]。在爬楼梯问题中，我们就可以定义dp[10]，该变量的含义是在第10层台阶时，往上爬总共有多少种可能性。3、找数组的边界值 边界值常常是动态规划方案“终点”的计算值，往往在“终点”或邻近“终点”时，才能直接计算一些变量的变化值。比如在爬楼梯问题中，从第10层楼梯，有多少种可能性，一下子是计算不出来的。但是当处在第1层或第2层楼梯时，就可以直接计算出往上爬楼梯的可能性，这就是在爬楼梯问题中的“边界值”。4、从前一个阶段转化到后一个阶段之间的递推关系 前面的三个步骤都可以说是铺垫，动态规划中最核心的就是这最后一步：找状态转移方程，其实也就是每个阶段的变量怎样变化的关系式（这一步在每个问题中，都可能有不同的关系式，需要视具体情况而定）。在爬楼梯问题中，我们定义的在第10层往上爬的变量为dp[10]，此时题中有个条件是：一次只能爬一阶或两阶，这个条件就决定了转移方程的写法。 因为每次只能只能爬1或2个台阶，所以，从第10层楼梯只能爬到第9层或第8层，并且在从第10层爬到第9层和从第10层爬到第8层，是不存在交叉关系的过程。处在第9层和第8层时的变量，很容易想到是dp[9]和dp[8]，所以在该问题中，从第10层往上爬的状态转移方程就是：dp[10]=dp[9]+dp[8]。在推广到后续阶段过程中，状态转移方程就是：dp[n]=dp[n-1]+dp[n-2]。 1.1 适用场景能用动态规划解决的问题具有的特征： 1>最优化原理 如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。这个特征较容易理解，常见就是在某个问题汇总存在最值。 2>无后效性 即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。这个特征可以理解为：可以存储不同阶段的变量值。这样的话，在后续阶段中，就不用重复求一些之前阶段的值。 3>有重叠子问题 即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势。该特征是说，解问题的不同阶段中，子问题是有重叠、依赖关系的。如果子问题不存在重叠、依赖关系，使用分治往往更好。 1.2 使用步骤在动态规划的步骤上，每个人也有每个人的理解。一种比较容易的步骤是： 1>划分阶段 按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。 2>确定状态 将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。 3>确定决策并写出状态转移方程 因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。 4>寻找边界条件 给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。 1.3 常用方法-填表法 在使用动态规划思想解决问题时，最常用的方法是填表法，该方法是以未知的量为基础，通过已知的量来刷新当前的未知量。此处借用一张网上的图来表示： 常见例子如下： 1>矩阵连乘 2>走金字塔 3>最长公共子序列 4>最长递增子序列 5>背包问题 接下来将对这些例子进行实现，来探究动态规划的具体使用方法。 二、常见例子 2.1 矩阵连乘 矩阵连乘也是常见的动态规划例子之一。该问题的形式如下：给出N个矩阵，矩阵是有序的，即相邻矩阵之间可以进行乘法运算，求这些矩阵最小的相乘次数。 矩阵乘法是满足结合律的，所以在矩阵连乘的过程中，可以有多种相乘顺序，这种相乘次序，可以用加括号来确定。如存在着下面三个维度的矩阵：A1(30 * 15)、A2(15 * 5)、A3(5 * 10)，这三个矩阵连乘时，有两种计算次序：（A1A2）A3和A1（A2A3）。 以矩阵（3 * 2）和B（2 * 4）为例，两个矩阵的相乘的计算量如下： 字符不相等的情况下，保持现有公共字符串长度即可，用代码表示： dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1];4>寻找边界条件 在使用填表法解决动态规划问题时，当把表填完，就代表解决问题的过程已经结束，也就是所谓的边界条件。 有了上面的4步，就可以写代码了，示例代码如下： public class MaxSequence { public static void main(String[] args) { String str1 = "abcd"; String str2 = "adcd"; int result = findMaxSequence(str1, str1.length(), str2, str2.length()); System.out.println("公共子序列长度是："+result); } public static int findMaxSequence(String str1, int str1length, String str2, int str2length) { int[][] dp = new int[str1length + 1][str2length + 1]; for (int i = 0; i 确定状态 该问题中状态的定义是：以该位置的元素结尾，最长公共子序列的长度是多少。 3>写状态转移方程 状态转移的实现方式，其实在上面已有介绍，就是当某个位置的元素大于之前位置的元素时，就取之前的最长公共子序列长度+1和默认公共子序列长度之中的较大值。示例代码如下： if(array[i] > array[j]){ currentLegnth = Math.max(currentLegnth, dp[j]+1); }当某位置的元素小于之前位置的所有元素时，以该位置元素结果的最终递增子序列长度就是默认值1。 4>寻找边界条件 该问题的起始条件是1，也就是以最初始位置元素为结尾的默认递增子序列长度是1，结束条件就是将元素比较完。 示例代码如下： public class LongestSequence { public static void main(String[] args) { int[] array ={2,3,1,5,4}; int result = getResult(array); System.out.println("最长递增子序列长度是："+result); } private static int getResult(int[] array){ int[] dp = new int[array.length]; dp[0] = 1; for(int i = 0; i = 0; j--){ if(array[i] > array[j]){ currentLegnth = Math.max(currentLegnth, dp[j]+1); } } dp[i] = currentLegnth; } int maxLength = 1; for(int i = 0; i 划分阶段 该问题中，显而易见，阶段是按能装入到几个物品来划分的。因为动态规划表dp的其中一个维度就是物品。 2>确定状态 在构建动态规划表时，涉及两个元素：物品和背包承重量，所以状态也肯定使用这两者来表示，即dp[i][j]。关键的是这个dp[i][j]要表示怎样的值才合适？这时需要回到问题本身，看最后求的解是什么，就能定义这个状态表示的含义了，那就是当能装入第i个物品，背包承重为j时，所能装入物品的最大价值。这是动态规划问题的难点之一，状态的定义有时并不直观。 3>写状态转移方程 有了状态，就要写状态转移方程了。此时，有两种情况，1是背包的承重不足以装下当前的物品，那么此时背包能装入的最大重量是前一个物品装入的价值，用代码表示为： dp[i][j] = dp[i - 1][j];当背包能装入一个物品时，就需要考虑：是否要装入该物品？如果装入该物品后，不能达到最大装入价值，此物品肯定也是不需要装入的，反之则需要装入。用代码表示为： dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);4>寻找边界条件 此问题的起始变量为0，即一个物品也不装入时，背包中的物品价值为0。结束条件即物品遍历完毕。 示例代码如下： public class ZeroOnePackage { public static void main(String[] args) { /*商品的重量2、3、4、5*/ int[] weight = { 0 , 2 , 3 , 4 , 5 }; /*商品的价值3、4、5、6*/ int[] value = { 0 , 3 , 4 , 5 , 6 }; /*背包限重*/ int bagVeight = 8; int result = getMaxValue(weight,value,bagVeight); System.out.println("背包能装入的最大重量是："+result); } private static int getMaxValue(int[] weight,int[] value,int bagVeight){ int[][] dp = new int[weight.length][bagVeight+1]; for (int i = 1; i |
由上图可知，填表法的计算过程就是：借用初始变量和状态转移方程将动态规划表逐渐填完，再找出最值。
回到矩阵A1、A2、A3的矩阵连乘问题。当进行（A1A2）A3运算时，乘法计算次数为30 * 15 * 5+30 * 5 * 10=3750,；进行A1（A2A3）运算时，乘法计算次数为15 * 5 * 10+30 * 15 * 10=5250。由此可见，不同的运算顺序，会影响到乘法的计算次数。 对于矩阵连乘AiAi+1Ai+2……Aj的最优解问题，假设在第k位置上找到最优解，则完整的矩阵连乘问题就变成了两个子矩阵连乘问题，即（AiAi+1……Ak）和（Ak+1……Aj）。 此时用m[i][j]表示矩阵连乘的最优值，那么两个子矩阵连乘问题对应的最优值变成m[i][k],m[k+1][j]。阵连乘最优值递归式如下： 
此式子中的Pi-1 * Pk * Pj 代表的意思是划分后的两个矩阵的相乘后的乘法次数。 矩阵相乘示例代码如下：【本文地址】