济南seo整站优化招商电话,房地产网站建设策划书,做外贸面料哪个网站可以接单,1688货源网下载文章目录 一、动态规划是什么#xff1f;二、动态规划原理三、0-1背包问题总结 一、动态规划是什么#xff1f;
动态规划是一种解决最优化问题的复杂算法#xff0c;其从形式上看与分治法类似#xff0c;两者都是通过将大问题逐步分解为小问题#xff0c;直到一个原子问题… 文章目录 一、动态规划是什么二、动态规划原理三、0-1背包问题总结 一、动态规划是什么
动态规划是一种解决最优化问题的复杂算法其从形式上看与分治法类似两者都是通过将大问题逐步分解为小问题直到一个原子问题直接求解。但它们又有本质的不同。具体表现在如下方面
子问题重叠性动态规划算法分解的子问题具有重叠性而使用分治法解决的子问题通常是独立的。中间结果的存储动态规划通过缓存中间结果来减少重复子问题带来的重复运算算法使用要求使用动态规划算法要求问题具有最优子结构与重叠子问题性质分治法无特殊要求算法复杂度分治法复杂度较高为O(2^ n而动态规划时间复杂度为多项式级别On^ 2
举例说明一下子问题重叠性质对于数组{1324}排序使用分治法子问题图如{1324}-》{13}{24}-》{1}{3}{2}{4}而动态规划的子问题图形式如下 其中每个顶点对应一个子问题而每条边是子问题的一种选择。
使用动态规划算法解决问题的步骤大致分为以下四步 其中1-3步是必选项这3步仅仅是求出一个最优解的值可以理解为给最优解问题的一个评估分数这个分值既可以表示正向价值也可以表示负向价值若表示正向价值则在求解子问题时取其所有选择中的max值否则取min值。
例如对于钢条切割问题来说这个值就是切割方案的最大经济价值而对于矩阵链乘法问题这个值是矩阵相乘的代价负向价值
第四步是可选项如果不仅仅需要求出最优解的值还需要给出具体方案那就需要在求解过程中在关键选择处记录下关键信息后续通过这些信息来反推方案。
动态规划有两种实现方式一种是自顶向下带备忘的递归实现一种是自底向上的循环实现
二、动态规划原理
接下来我会详细解释一下上述的四个步骤 首先第一步是刻画一个最优解的特征。
这一步骤的目的是为了判断问题是否具备使用动态规划算法的条件与性质。使用动态规划算法需要满足最优子结构与子问题重叠两个性质。 最优子结构如果一个问题的最优解包含其子问题的最优解我们就称此问题具有最优子结构 子问题重叠子问题空间必须足够小即问题的递归算法会反复地求解相同的子问题而不是一直生成新的子问题 发掘一个问题的最优子结构实际上遵循如下的通用模式 问题的最优解值是由选择本身所产生的收益正向收益取最大值反向收益表示代价取最小值子问题产生的收益两部分组成的对于钢条切割问题其选择与子问题产生的收益如下如下 而对于矩阵链乘法问题如下 框出的部分是选择本身所产生的收益剩余部分是子问题收益。
我们需要假设某个选择是此时问题规模的最优解并且假设子问题的最优解是已知的。
确定选择会产生哪些子问题做出一个选择本质上就是决定如何对问题进行分解。子问题形式的选择会影响问题的复杂程度我们需要决定如何刻画这个子问题可能需要从多个维度考虑
最后一步证明也是最关键的一步证明此结构的正确性。即如果子问题选择是问题的一个最优解那么子问题的解本身也是其自身的最优解。可能你会觉的奇怪这难道不应是理所当然的事情吗实则不然这个问题的本质实际上是在讨论一个问题的局部最优解是否能够推导出一个全局最优解。
那么哪些情况下会破坏最优子结构性质我大致罗列了以下几点
子问题之间存在干扰一个子问题的选择会直接或间接的影响到其他子问题的求解。当前解的选择影响到剩余子问题的可行解空间问题的解依赖历史决策状态目标函数的非线性组合子问题之间不是简单的叠加而是更复杂的运算约束条件动态的变化约束指状态转移方程中对自由度的约束即括号中的部分
关于子问题之间相互干扰这里举个例子。求解无权有向图的最长简单路径 导致此问题不满足最优子结构的根本原因在于其子问题之间是非独立的q-r的最长简单路径的求解会锁定r-t的最长简单路径的求解所需的资源顶点。无关性是指问题分解出的子问题之间是互相独立的不锁定对方的资源。
第二个需要满足的性质是子问题重叠。上面已经举过例子进行简单说明下面再给一个更直观的图 在矩阵链乘法问题中不带备忘的递归版本实现中图中的阴影部分是重复出现的子问题这些问题会被重复的计算。 接下来讲解第二个步骤。递归定义最优解的值也就是说在证明问题具备特征后推导其出状态转移方程。 例如在钢条切割问题中只涉及一个子问题而在矩阵链乘法中涉及两个子问题。这两个问题中每个问题的解都存在多种选择而在后续的背包问题中我们会看到仅有简单的两种选择的情况。
子问题的数量与选择的数量可以粗略估算算法总体复杂度。也可以通过子问题图来分析。图中每个顶点对应一个子问题每条边对应一种选择。
这个步骤还有一个需要注意的点是有时为了保证子问题具有一致的形式需要对子问题进行一般化。 也就是说我们必须保证分解出的所有子问题能够使用同一个状态转移方程求解。在矩阵链乘法问题中我们会发现将一个链分解后第二个链的形式会与第一个有所不同为此我们引入额外的自由度来表示方程使其更具有一般性这也是为什么其解是由Aij 表示而非A1j 。通过引入额外自由度我们改变了子问题的刻画形式而每个自由度最终都对应表格中的一个维度。通过改变子问题刻画形式有时还能改变问题求解的复杂度我们需要明确这种刻画所表示的含义。
状态转移方程还应该包括临界值它们对应着问题中的边界条件是问题求解过程中的特殊情况换句话说是指问题分解到原子问题时的情况此时问题的解是一目了然的。当递推公式不满足其约束时会跳转到这个状态 第三个步骤计算最优解的值也就是将推导设计出的状态转移方程进行代码实现。
通常有两种实现方式一种是带备忘的自上而下的实现一种是自下而上的实现。
不带备忘的递归实现会反复计算重复子问题。上面已经展示过这种情况这种情况下其性能与暴力求解无异。复杂度为O2^n。
而带备忘的自上而下递归与自下而上的实现两种方式复杂度差不太多大致都在On^2的量级。 不管使用哪种方式实现都需要维护一个对应子问题刻画形式所需维度的表用于存储中间结果因为动态规划的本质其实就是利用表项与表项之间的依赖关系来进行求解。而表项间的关系即是递推方程。当使用自顶向下法实现时这个方程用递归形式表示而当使用自底向上法实现时这个方程直接使用所依赖的表项来表示。
为此在进行自底向上的实现时我们需要仔细的分析问题的子问题空间确定其所依赖的表项从而确定表的填充顺序。以保证在求解每个问题时其所依赖的每个子问题以经被解决。
举个例子在矩阵链乘法问题中其表项的依赖关系如下图所示 第四个步骤用所求的值构造最优解。
这个步骤需要维护一个记录关键选择的表在每次做出关键选择时将所作的选择记录下来。最后通常会使用逆推的方式回溯出完整的解决方案。 三、0-1背包问题
接着运用上述所讲的思维方式来看看动态规划问题的具体求解过程。
我以经典的0-1背包问题举例说明。这个问题大致描述如下
给定背包容量m给定n件物品给定n件物品的价值数组v重量数组w求如何选择物品使得在不超出背包最大容量的情况下物品的总价值最大。
分析过程如下
问题总体太大我们无法得知结果尝试对其进行分解假设在rmset{i}为背包容量为m物品集合为set{i}时的最大价值
假设此时我们选择第k件物品会使得背包中物品价值最大此时rmset{i}rm-w[k],set{i}-k(k属于set{i}且w[k]m)
通过假设选择我们把问题拆分成两个子问题背包容量、物品集合都缩小了但是分析这个推导出的方程发现其中的维度set{i}是一个无序的维度这使得公式的实现变得复杂得出结论——直观的分析结果不可行。
转换思维方式对子问题刻画方式稍加修改使用rm,i表示背包容量为m前i件物品时的最大价值注意我对此子问题刻画的表述明确说明了前i件物品这与之前的定义有很大不同在这种定义下物品维度变的有序简化了算法实现
接着推导其公式因为背包容量与物品数量维度都是从小到大的增长我们假设在求解rmi时i-1之前的所有物品都已经考察过所以这种情况下我们只需要考察第i件物品即可。
对于第i件物品来说分两种情况
w[i]m 此时物品根本无法放入那么rm,i必然等于rm,i-1w[i]m此时又会产生两种选择 假设i是最优方案中的一员即放入i那么r(m,i)r(m-w[i],i-1)v[i];假设i不在最优方案中那么r(m,i)r(m,i-1)保持不变,这两种选择我们选择其中的max值;
再分析临界情况当背包容量为0或物品数量为0时最大价值显然是0即r(m,i)0 (m0||i0)。
简单证明一下公式正确性假设r(m,i)为最优解时子问题的解并非其最优解那么我们可以通过取其最优解再与选择进行组合得出一个更优解从而与假设矛盾从公式也可以看出其显然也满足重叠子问题性质。
公式有两个自由度所以需要一个二维数组来进行缓存中间结果
得出公式接下来就可以代码落地实现了首先展示自上而下带备忘的递归实现
/** 背包问题给定背包容量mi件物品价值v以及重量w求* 在不超过背包容量的情况下如何拿取物品价值最大。*/
#region 自上而下带备忘的递归实现
//1.自上而下的带备忘递归实现
public static (int,Listint) KnapsackUpdown(int m, int[] v, int[] w)
{int n v.Length;//创建dp数组var dp new int[n, m];//创建构造最优解的关键信息表记录关键选择var s new int[n,m];Listint solution new Listint();//赋初值表示尚未计算状态的特殊值for (int i 0; i n; i){for (int j 0; j m; j){dp[i, j] int.MinValue;}}var r KnapsackUpdown(m, n, v, w, dp, s);//关键信息以记录到s表反推构造最优解while (m 1 n 1){var select s[n - 1, m - 1];if (select ! 0){solution.Add(select);m - w[select-1];}n--;}return (r,solution);
}
public static int KnapsackUpdown(int m, int i, int[] v, int[] w, int[,] dp, int[,]s)
{//递归终止条件(递推公式中的临界值)if (m 0 || i 0){return 0;}//如果结果缓存中存在则直接返回if (dp[i - 1, m - 1] 0){return dp[i - 1, m - 1];}//其他情况使用推导出的递推公式计算if (m w[i - 1]){var val1 KnapsackUpdown(m - w[i - 1], i - 1, v, w, dp,s) v[i - 1];var val2 KnapsackUpdown(m, i - 1, v, w, dp, s);dp[i - 1, m - 1] Math.Max(val1, val2);if (val1val2){s[i - 1, m - 1] i;}}else{dp[i - 1, m - 1] KnapsackUpdown(m, i - 1, v, w, dp, s);}return dp[i - 1, m - 1];
}
#endregion然后是自下而上的实现 #region 自下而上实现//2.自下而上的实现public static (int, Listint) KnapsackDownUp(int m, int[] v, int[] w){int n v.Length;//创建dp表项数组var dp new int[n 1, m 1];//创建构造最优解的关键信息表记录关键选择var s new int[n, m];Listint solution new Listint();//初始化临界值m0或i0的情况因默认初始化便为0所以此步骤省略//填充表项填充顺序从左到右从上到下确保每个表项计算时其依赖的子问题已计算完成for (int i 1; i n; i)//i表示当前计算表项对应的前i件物品{for (int j 1; j m; j)//j表示表项对应的背包容量{if (w[i - 1] j){//背包容量大于第i件物品取放与不放两种情况较大值var val1 dp[i - 1, j];//不放入var val2 dp[i - 1, j - w[i - 1]] v[i - 1];//放入dp[i, j] Math.Max(val1, val2);if (val2 val1){s[i - 1, j - 1] i;}}else{//否则价值不变dp[i, j] dp[i - 1, j];}}}var val dp[n,m];//关键信息以记录到s表反推构造最优解while (m 1 n 1){var select s[n - 1, m - 1];if (select ! 0){solution.Add(select);m - w[select - 1];}n--;}return (val, solution);}#endregion最后再给出一种使用一维数组的进一步优化的实现
#region 一维数组实现
//2.自下而上的实现进一步优化使用一维数组
public static (int, Listint) KnapsackDownUp1D(int m, int[] v, int[] w)
{int n v.Length;//创建dp表项数组var dp new int[m1];//创建构造最优解的关键信息表记录关键选择var s new int[n, m];Listint solution new Listint();//初始化临界值m0或i0的情况因默认初始化便为0所以此步骤省略//填充表项填充顺序从左到右从上到下确保每个表项计算时其依赖的子问题已计算完成for (int i 1; i n; i)//i表示当前计算表项对应的前i件物品{for (int j m; j1; j--)//j表示表项对应的背包容量{if (w[i - 1] j){//背包容量大于第i件物品取放与不放两种情况较大值var val1 dp[j];//不放入var val2 dp[j - w[i - 1]] v[i - 1];//放入dp[j] Math.Max(val1, val2);if (val2 val1){s[i-1,j-1] i;}}else{//否则价值不变dp[j] dp[j];}}}var val dp[m];//关键信息以记录到s表反推构造最优解while (m 1 n 1){var select s[n - 1, m - 1];if (select ! 0){solution.Add(select);m - w[select - 1];}n--;}return (val, solution);
}
#endregion简单说明一下可以使用一维数组进行优化的原因分析公式可知r(m,i)的计算依赖于r(m,i-1)即在计算r(m,i)时i-2之前的信息实际已经没什么价值了也就是说这部分空间可以复用而之所以要逆序是因为r(m,i)的计算还依赖于r(mw[i],i-1)为防止结果还没计算出来依赖项就被覆盖掉需要优先计算这些表项
这也就是所谓的利用表的访问模式进一步降低时空代价。
总结
本文通过详细展示动态规划问题的分析过程力图给读者建立一个完善全面的动态规划知识体系帮助读者建立思维方式抓住动态规划思想本质起到拨云见日的效果。动态规划、贪心算法等等作为高级的设计技术是一系列复杂工业算法的思想基础它解决的是一类问题而非某种特定问题掌握其思维方式是程序员的重要成长。 文章转载自： http://www.morning.feites.com.gov.cn.feites.com http://www.morning.lmpfk.cn.gov.cn.lmpfk.cn http://www.morning.tqpr.cn.gov.cn.tqpr.cn http://www.morning.kdnrc.cn.gov.cn.kdnrc.cn http://www.morning.rfrx.cn.gov.cn.rfrx.cn http://www.morning.dqdss.cn.gov.cn.dqdss.cn http://www.morning.3dcb8231.cn.gov.cn.3dcb8231.cn http://www.morning.wzwpz.cn.gov.cn.wzwpz.cn http://www.morning.lswgs.cn.gov.cn.lswgs.cn http://www.morning.fksyq.cn.gov.cn.fksyq.cn http://www.morning.nzsx.cn.gov.cn.nzsx.cn http://www.morning.snnwx.cn.gov.cn.snnwx.cn http://www.morning.nrchx.cn.gov.cn.nrchx.cn http://www.morning.kwqwp.cn.gov.cn.kwqwp.cn http://www.morning.dppfh.cn.gov.cn.dppfh.cn http://www.morning.rpwm.cn.gov.cn.rpwm.cn http://www.morning.yunease.com.gov.cn.yunease.com http://www.morning.qrzqd.cn.gov.cn.qrzqd.cn http://www.morning.qnpyz.cn.gov.cn.qnpyz.cn http://www.morning.kjlia.com.gov.cn.kjlia.com http://www.morning.dmzfz.cn.gov.cn.dmzfz.cn http://www.morning.sskkf.cn.gov.cn.sskkf.cn http://www.morning.mxhcf.cn.gov.cn.mxhcf.cn http://www.morning.hrpbq.cn.gov.cn.hrpbq.cn http://www.morning.bpmfn.cn.gov.cn.bpmfn.cn http://www.morning.frfpx.cn.gov.cn.frfpx.cn http://www.morning.gqjqf.cn.gov.cn.gqjqf.cn http://www.morning.fwrr.cn.gov.cn.fwrr.cn http://www.morning.brsgw.cn.gov.cn.brsgw.cn http://www.morning.kbqws.cn.gov.cn.kbqws.cn http://www.morning.mlfmj.cn.gov.cn.mlfmj.cn http://www.morning.kgxyd.cn.gov.cn.kgxyd.cn http://www.morning.xxsrm.cn.gov.cn.xxsrm.cn http://www.morning.yrmpz.cn.gov.cn.yrmpz.cn http://www.morning.wpqwk.cn.gov.cn.wpqwk.cn http://www.morning.mwlxk.cn.gov.cn.mwlxk.cn http://www.morning.zcqbx.cn.gov.cn.zcqbx.cn http://www.morning.rxsgk.cn.gov.cn.rxsgk.cn http://www.morning.hfrbt.cn.gov.cn.hfrbt.cn http://www.morning.sgcdr.com.gov.cn.sgcdr.com http://www.morning.nlgnk.cn.gov.cn.nlgnk.cn http://www.morning.ckbmz.cn.gov.cn.ckbmz.cn http://www.morning.nxhjg.cn.gov.cn.nxhjg.cn http://www.morning.fynkt.cn.gov.cn.fynkt.cn http://www.morning.zqcdl.cn.gov.cn.zqcdl.cn http://www.morning.kfjnx.cn.gov.cn.kfjnx.cn http://www.morning.mszls.cn.gov.cn.mszls.cn http://www.morning.fhtmp.cn.gov.cn.fhtmp.cn http://www.morning.drfcj.cn.gov.cn.drfcj.cn http://www.morning.zpyh.cn.gov.cn.zpyh.cn http://www.morning.ttdbr.cn.gov.cn.ttdbr.cn http://www.morning.rldph.cn.gov.cn.rldph.cn http://www.morning.hymmq.cn.gov.cn.hymmq.cn http://www.morning.pyswr.cn.gov.cn.pyswr.cn http://www.morning.lwnb.cn.gov.cn.lwnb.cn http://www.morning.qzpqp.cn.gov.cn.qzpqp.cn http://www.morning.phjny.cn.gov.cn.phjny.cn http://www.morning.frtt.cn.gov.cn.frtt.cn http://www.morning.llxqj.cn.gov.cn.llxqj.cn http://www.morning.wcqkp.cn.gov.cn.wcqkp.cn http://www.morning.mxdiy.com.gov.cn.mxdiy.com http://www.morning.tftw.cn.gov.cn.tftw.cn http://www.morning.hhzdj.cn.gov.cn.hhzdj.cn http://www.morning.ysybx.cn.gov.cn.ysybx.cn http://www.morning.sfyqs.cn.gov.cn.sfyqs.cn http://www.morning.bwfsn.cn.gov.cn.bwfsn.cn http://www.morning.rnwt.cn.gov.cn.rnwt.cn http://www.morning.nclps.cn.gov.cn.nclps.cn http://www.morning.zpzys.cn.gov.cn.zpzys.cn http://www.morning.yrmpz.cn.gov.cn.yrmpz.cn http://www.morning.njftk.cn.gov.cn.njftk.cn http://www.morning.tmxfn.cn.gov.cn.tmxfn.cn http://www.morning.nbybb.cn.gov.cn.nbybb.cn http://www.morning.wdhzk.cn.gov.cn.wdhzk.cn http://www.morning.rythy.cn.gov.cn.rythy.cn http://www.morning.svrud.cn.gov.cn.svrud.cn http://www.morning.ytnn.cn.gov.cn.ytnn.cn http://www.morning.hqwtm.cn.gov.cn.hqwtm.cn http://www.morning.gllgf.cn.gov.cn.gllgf.cn http://www.morning.hcbky.cn.gov.cn.hcbky.cn
