1背包问题的动态编程方法. ppt

动态编程； 1.概述； 1.1多段图的最短路径问题； 2;令G为有向加权图，则G与G的顶点j之间的最短路径问题满足最优性原则. 证明: 让i〜ip〜iq〜j是最短路径，但是子路径ip〜iq〜j不是最优路径. 假设最佳路径为ip〜iq'〜j，则我们重构路径: i〜ip〜iq'〜j显然，路径长度小于i〜ip〜iq〜j，这与i〜ip〜iq〜矛盾. j是从顶点i到顶点j的最短路径. 因此，原始问题满足最优性原则. 对于多段图的边缘（u，v），使用cuv表示边缘的权重，并将从源点s到终点t的最短路径记录为d（s，t），然后从源点0到终点9；最短路径d（0，9）由以下公式确定: d（0，9）= min {c01 + d（1，9），c02 + d（2，9），c03 + d（3，9） ）}是决策的最后阶段，它取决于d（1，9），d（2，9）和d（3，9）的计算结果，并且d（1，9）= min {c14 + d（4，9），c15 + d（5，9）} d（2，9）= min {c24 + d（4，9），c25 + d（5，9），c26 + d（6， 9）} d（3，9）=最小值{c35 + d（5，9），c36 + d（6，9）}此阶段的决定取决于d（4，9），d（5，9）和d（6，9）: d（4，9）=最小值{7 + d（7，9），8 + d（8，9）} d（5，9）=最小值{c57 + d（7， 9），c58 + d（8，9）} d（6，9）= min {c67 + d（7，9），c68 + d（8，9）}此阶段的决定取决于d（7， 9）和d（8，9），以及d（7，9）和d（8，9）可以直接获得（该决定生成的状态转换在括号中给出）: d（7，9）= c79 ＝ 7（7→9）d（8，9）= c89 ＝ 3（8→9）然后向前推导，有: d（6，9）= min {c67 + d（7，9），c68 + d（8，9）} =最小值{6 + 7，5 + 3} = 8（6→8）d（5， 9）=最小值{c57 + d（7，9），c58 + d（8，9）} =最小值{8 + 7，6 + 3} = 9（5→8）d（4，9）=最小值{ 7 + d（7，9），c 48 + d（8，9）} =最小值{5 + 7，6 + 3} = 9（4→8）; d（3，9）=最小{c35 + d（5，9），c36 + d（6，9）} =最小{4 + 9，7 + 8} = 13（3→5）d（2，9 ）=最小{c24 + d（4，9），c25 + d（5，9），c26 + d（6，9）} =最小{6 + 9，7 + 9，8 + 8} = 15（2 →4）d（1，9）=最小{c14 + d（4，9），c15 + d（5，9）} =最小{9 + 9，8 + 9} = 17（1→5）d（ 0，9）=最小{c01 + d（1，9），c02 + d（2，9），c03 + d（3，9）} =最小{4 + 17，2 + 15，3 + 13} = 16（0→3）的最短路径是0→3→5→8→9，长度是16.

;在以上示例的多阶段决策问题中，每个阶段做出的决策通常与时间相关. 该决定取决于当前状态，然后导致状态转换. 决策序列处于变化状态. 它源自“动态”含义，这种解决多阶段决策优化问题的方法称为动态规划方法. 动态编程是运筹学的一个分支. 与其说动态编程是一种算法，不如说是一种更合适的思维方式. 因为没有用于动态编程的固定框架，所以即使将其应用于同一问题，也可以建立各种形式的求解算法. 隐式图上的许多算法（例如Dijkstra的用于查找单个源的最短路径的算法和广度优先搜索算法）都充满了动态规划的思想. 因此，动态编程不会先提供诸如深度或宽度之类的模式集，而是可以在需要时使用它. 它必须专门分析和处理特定问题，需要丰富的想象力来构建模型，并且需要创造性的思维. 解决. 确切地说，动态编程并不是万能的. 它仅适用于在特定条件下解决最佳策略问题. 也许您会很失望地听到这个结论: 实际上，这个结论并没有减少动态编程的光彩，因为上述范围内有太多问题，而且似乎有很多问题不在此范围内. 变成了这样的问题. 上述“满足一定条件”主要是指以下两点: （1）状态必须满足优化原则； （2）国家不得满足任何后遗症.

此功能是什么意思？它表明动态编程适合解决与当前决策和过去状态无关的问题. 该状态出现在策略的任何位置，其状态相同，并且所有人都可以执行相同的决策. 这是没有后效的意思. 最佳策略作为整个过程具有以下属性: 不管过去的状态和决策如何，对于以前的决策形成的当前状态，其余决策必须构成最优策略. 可以理解的是，子问题的局部优化将导致整个问题的全局优化，即问题具有最优子结构的性质，也就是说，问题的最优解仅取决于子问题. 最优解和非最优解对问题的解决没有影响. 在示例1中，最短路径问题，即从A到E的最佳路径上的任意点到端点E的路径，也必须是从该点到端点E的最佳路径，满足优化原理. 让我们讨论另一个问题. 示例问题残留数最少的路径. [分析]在此问题中，如果仍然按照示例1中的方法进行解决，则会发生错误. 根据示例1的思想，可以由B的最优值确定A的最优值，并且B的最优值为（1 + 3）mod 4 = 0，因此A的最优值应为2实际上，路径C1-C3-C5的最优值为（2 +1 + 1）mod 4 = 0，因此B的最优路径不是A的最优路径的子路径，即说A的最优值不是由B的最优值决定的，也就是说，它不满足优化原理，问题不具有最优子结构的性质.

可以看出，并不是所有的“决策问题”都可以通过“动态规划”解决，使用“动态规划”来解决问题必须满足优化原则. 所谓不产生后效应的原则是指这样的性质: 一旦确定了某个阶段的状态，此后过程的演变将不再受先前状态和决策的影响. 换句话说，“未来与过去无关”. 当前状态是先前历史的完整摘要. 先前的历史只能通过当前状态影响流程的未来发展. 具体而言，如果将问题分为多个阶段，则只能通过状态转换方程从阶段I + 1的状态中获得阶段I的状态，并且与其他状态（尤其是未发生的状态）没有关系，这不是后劲. ; 1.6动态规划方法的设计思想;解决原始问题；首先，划分阶段: 根据问题的时间或空间特征，将问题划分为几个阶段. 第二，选择状态: 问题发展到各个阶段的客观条件以不同的状态表示. 3.确定决策并写出状态转移方程式: 状态转移是根据前一阶段的状态和决策来得出该阶段的状态. 4.编写编程方程式（包括边界条件）: 动态编程的基本方程式是编程方程式的一般形式表达式. 动态规划方法可以解决的问题不仅可以分解为几个重叠的子问题，而且可以满足最优性原则（也称为最优子结构性质）. 这种类型的问题具有以下特征: 该解决方案还包含子问题的最佳解决方案.

在分析问题是否满足最优性原则时，通常假定从问题的最优解导出的子问题的解不是最优的，然后尝试在此假设下解释最优问题可以更好的解决方案会导致矛盾. 动态规划方法使用问题的最优性原理，以自下而上的方式从子问题的最优解逐步构建整个问题的最优解. 使用动态规划的设计算法通常分为三个阶段: （1）分割: 将原始问题分解为几个重叠的子问题； （2）分析: 分析问题是否满足最优性原则，找出动态规划函数的递推公式； （3）解决: 使用递归公式从下至上进行计算，以实现动态编程过程. ; 2.组合问题中的动态规划方法； 2.1 0/1背包问题;在0/1背包问题中，项目i要么装入背包，要么不装入背包，令xi表示项目i装入背包. 在这种情况下，当xi = 0时，表示项目i不装在背包中，当xi = 1时，表示物品i已装在背包中. 根据问题的要求，有以下约束条件和目标函数: 首先，证明0/1背包问题满足最优性原则. 令（x1，x2，…，xn）为给定的0/1背包问题的最优解，然后（x2，…，xn）为以下子问题的最优解: 可以看到0/1背包问题作为决策序列（x1，x2，…，xn），对任何变量xi的决策都是决定xi = 1或xi = 0.

在对xi-1做出决定后，已确定（x1，…，xi-1）. 在对xi做出决策时，问题在于以下两种状态之一: 背包的容量不足以装载物品i，则xi = 0的背包不会增加价值； b. 可以用项目i装载背包容量，然后xi = 1，背包值增加vi. 在这两种情况下，背包的最大价值应为决定xi后的背包的价值. 令V（i，j）表示前i（1≤i≤n）个项目中可装载到容量为j（1≤j≤C）的背包中的项目的最大值，然后进行以下动态编程可以得到以下函数: V（i，0）= V（0，j）= 0（公式3）;等式3表示: 将前i个物品装进容量为0的背包中，将0个物品装进容量为j的背包中，获得的值全部为0.等式4的第一个公式表明，如果重量第i个物品的``i''大于背包的容量，则通过加载第一个i项目获得的最大值与通​​过加载第i-1个项目获得的最大值相同，即，第i个物品无法放入背包;第二个公式表明，如果第i个物品的重量小于背包的容量，则将出现以下两种情况: （1）如果将第i个物品装入背包，则背包的值物品的数量等于装在容量为j-wi的背包中的第一个i-1物品的价值加上第i物品vi的价值； （2）如果没有将i物品装入背包，则该物品的价值等于将前i-1件物品装入容量为j的背包中获得的价值.

显然，将两者中的较大者作为将前i个物品装入容量为j的背包的最佳解决方案. 在第一阶段，仅加载第一件物品来确定背包在每种情况下可获得的最大值. 在第二阶段，仅加载前两个项目来确定背包在每种情况下均可获得的最大值；直到第n个阶段. 最后，V（n，C）是将n个物品装入容量为C的背包中时获得的最大值. 要确定装入背包中的特定物品背包问题 动态规划法，请从V（n，C）的值向前推. 如果V（n，C）> V（n-1，C），则表示第n个物品已装入背包. 将n-1件物品包装到一个可容纳C-wn的背包中；否则，将第n个项目不包装在背包中，将前n-1个项目包装在容量为C的背包中. 依此类推，直到确定是否将第一个项目放入背包中. 由此获得以下功能: 例如，有5个物品的权重为{2，2，6，5，5，4}，值为{6，3，5，4，6}，还有一个背包容量为10. 寻找背包中装载的物品并获得最大值. ;;令n个项目的权重存储在数组w [n]中，值存储在数组v [n]中，背包容量为C，数组V [n + 1] [C +1]存储迭代结果，其中V [i] [j]表示将前i个物品装入容量为j的背包时获得的最大值. 数组x [n]存储装入背包的物品. 通过动态编程解决0/1背包问题的算法如下: 算法1-0 / 1背包问题int KnapSack（int n，int w []，int v []）{for（i = 0; i < = n; i ++）//初始化列0 V [i] [0] = 0; for（j = 0; j <= C; j ++）//初始化行0 V [0] [j] = 0; for（i = 1; i <= n; i ++）//计算第i行，如果（j 0; i-）{if（V [i] [j]> V [i-1] [j]）{x [i] = 1; j = jw [i]; } else x [i] = 0;}返回V [n] [C]; //返回背包获得的最大值}； 2.2最长的公共子序列问题；令序列X = {x1，x2，…，xm} Y = {y1，y2，…，yn}的最长公共子序列为Z = {z1，z2，…，zk}，令Xk为的子序列. 序列X列中前k个连续字符的子序列，Yk是序列Y中前k个连续字符的子序列，Zk是序列Z中前k个连续字符的子序列，显然，以下公式成立: （1）如果xm = yn，则zk = xm = yn，并且Zk-1是Xm-1和Yn-1的最长公共子序列； （2）如果xm≠yn和zk≠xm，则Z是Xm-1和Y的最长公共子序列； （3）如果xm≠yn和zk≠yn，则Z是X和Yn-1的最长公共子序列.

可以看出，两个序列的最长公共子序列包含两个序列的前缀序列的最长公共子序列. 因此，最长的公共子序列问题满足最优性原则. 为了找到序列X的最长公共子序列X = {x1，x2，…，xm}并且Y = {y1，y2，…，yn}，可以计算如下: 当xm = yn时，找出最长的公共子序列Xm-1和Yn-1的子序列;然后在尾部加上xm以获得X和Y的最长公共子序列；当xm≠yn时，必须解决两个子问题: 查找Xm-1和Y的最长公共子序列以及Xm和Yn-1的最长公共子序列，这两个公共子序列中的较长的是X和Y的最长公共子序列. 使用L [i] [j]表示子序列Xi和Yj的最长公共子序列的长度，可以获得以下动态编程函数: L [0] [0] = L [i] [0] = L [0] [j] = 0（1≤i≤m，1≤j≤n）（等式6）（等式7）；为了获得序列Xm和Yn的最长公共子序列，假设一个二维表S [m +1] [n +1]，其中S [i] [j]表示计算L时的搜索状态[i] [j]，并具有: ; （a）长度矩阵L（b）状态矩阵S图4求解最长公共子序列的； 3，图问题的动态规划方法； 3.1 TSP问题；假设从顶点i开始，让d（i，V'）表示从顶点i到V'的每个顶点一次并且只有一次，最后返回到起点i的最短路径长度. 首先，V'= V- {i}，然后，TSP问题的动态编程函数为: d（i，V'）= min {cik + d（k，V－ {k}）}（k ∈V'）（等式8）d（k，{}）= cki（k≠i）（等式9）;从城市0开始，再经过城市1、2和3，到达城市0的最短路径长度是: d（0，{1，2，3}）= min {c01 + d（1，{2，3} ），c02 + d（2，{1，3}），c03 + d（3，{1，2}）}这是决策的最后阶段，它必须基于d（1，{2，3} ），d（2，{1，3}）和d（3，{1，2}）和: d（1，{2，3}）=最小{c12 + d（2，{3}），c13 + d（3，{2}）} d（2，{1，3}）=最小{c21 + d（1，{3}），c23 + d（3，{1}）} d（3，{1，2}）=最小值{c31 + d（1，{2}），c32 + d（2， {1}）}此阶段的决定取决于以下计算结果: d（1，{2}）= c12 + d（2，{}）d（2，{3}）= c23 + d（3， {}）d（3，{2}）= c32 + d（2，{}）d（1，{3}）= c13 + d（3，{}）d（2，{1}）= c21 + d（1，{}）d（3，{1}）= c31 + d（1，{}），可以直接获得以下公式（括号中是由该决定引起的状态转换）: d（1， {}）= c10 = 5（1→0）d（2，{}）= c20 = 6（2→0）d（3，{}）= c30 = 3（3→0）;向前推导，有: d（1，{2}）= c12 + d（2，{}）= 2 + 6 = 8（1→2）d（1，{3}）= c13 + d（3， {}）= 3 + 3 = 6（1→3）d（2，{3}）= c23 + d（3，{}）= 2 + 3 = 5（2→3）d（2背包问题 动态规划法，{1} ）= c21 + d（1，{}）= 4 + 5 = 9（2→1）d（3，{1}）= c31 + d（1，{}）= 7 + 5 = 12（3→1 ）d（3，{2}）= c32 + d（2，{}）= 5 + 6 = 11（3→2）然后推导，有: d（1，{2，3}）= min {c12 + d（2，{3}），c13 + d（3，{2}）} =最小{2 + 5，3 + 11} = 7（1→2）d（2，{1，3}）= min {c21 + d（1，{3}），c23 + d（3，{1}）} = min {4 + 6，2 + 12} = 10（2→1）; d（3，{1，2}）=最小{c31 + d（1，{2}），c32 + d（2，{1}）} =最小{7 + 8，5 + 9} = 14（3 →2）最后: d（0，{1，2，3}）=最小{c01 + d（1，{2，3}），c02 + d（2，{1，3}），c03 + d（ 3，{1，2}）} =最小值{3 + 7，6 + 10，7 + 14} = 10（0→1），从顶点0开始的TSP问题的最短路径长度是10，并且该路径是0→1→2→3→0.

;假设n个顶点的编号从0到n-1，请考虑以从顶点0求解TSP问题的形式填充. 首先，按1的顺序生成1到n-1个元素的子集，2，...，n-1并存储在数组V [2n-1]中，例如，当n = 4时，V [1] = {1}，V [2] = {2}，V [ 3] = {3}，V [4] = {1，2}，V [5] = {1，3}，V [6] = {2，3}，V [7] = {1,2,3 3}. 让数组d [n] [2n-1]存储迭代结果，其中d [i] [j]表示从顶点i到子集V [j]中的顶点的最短路径一次且仅一次，最后返回起点0长度. 首先，根据等式9初始化数组d的第0列，然后根据等式8逐列计算，在表格中填写表格的过程如图3所示. 5 .；让顶点之间的成本存储在数组c [n] [n]中. 解决TSP问题的动态规划方法的算法如下: 实践; 4.找到问题中的动态规划方法；令{r1，r2，…，rn}是n个记录的集合，它们的搜索概率分别为{p1，p2，…，pn}. 最佳二进制搜索树（Optimal Binary Search Trees）是由这n个记录组成的二进制搜索树. 平均比较数最小的二叉搜索树最小，其中pi是记录ri的搜索概率，ci是在二叉搜索树中找到ri的比较数.

例如，集合{A，B，C，D}的搜索概率为{0.1、0.2、0.4、0.3}. 图6.11显示了三个二进制搜索树. 搜索成功后，二进制搜索树的平均比较时间（a）为0.1×1 + 0.2×2 + 0.4×3 + 0.3×4 = 2.9，二进制搜索树的平均比较时间为（b ）为0.1×2 + 0.2×1 + 0.4×2 + 0.3×3 = 2.1，最佳二叉树为（c），平均比较数为0.1×3 + 0.2×2 + 0.4×1 + 0.3 ×2 = 1.7. 一种; rk;因此，获得以下动态编程函数: C（i，i-1）= 0（1≤i≤n+1）（等式10）C（i，i）= pi（1≤i≤n）（公式11）C（i，j）= min {C（i，k-1）+ C（k + 1，j）+}（1≤i≤j≤n，i≤k≤j）（公式12）公式10被解释为空树，比较次数为0，等式11被解释为仅包含记录ri的二叉搜索树. 假设一个二维表C [n + 1] [n + 1]，其中C [i] [j]表示二分搜索树T（i，j）的平均比较数. 注意，在等式12中，当k = 1时，C [i] [j]要求C [i] [0]，而当k = n时，C [i] [j]要求C [n + 1] [j] ，因此，二维表C [n + 1] [n + 1]的行下标的范围是1到n + 1，列下标的范围是0到n.

为了在查找由{r1，r2，…，rn}组成的二叉搜索树的比较平均数的同时获得最佳二叉搜索树，设置一个二维表R [n +1] [n +1]，下标范围与二维表C相同，R [i] [j]表示二叉搜索树T（i，j）的根节点的序列号. 例如，集合{A，B，C，D}的搜索概率为{0.1、0.2、0.4、0.3}. 二维表C和R的初始状态如图8所示. 因此，由前两个记录形成的最佳二叉搜索树的根节点数为2，并且每个C（i，j）和R（i，j）对角线地计算. 图9显示了决赛桌. 适用条件；动态编程的本质是分而治之，解决冗余. 与分治法类似，将原始问题分解为几个子问题，先解决子问题，然后再从这些子问题的解中获得原始问题的解. 与分而治之的方法不同，分解后的子问题通常不是彼此独立的. 如果被分割和征服，则一些共同的部分（子问题或子子问题）将被重复计算多次. 如果可以保存已解决子问题的答案，请在需要时查找它们，从而避免重复计算并节省时间. 动态编程方法使用表格记录所有已解决子问题的答案. 这是动态编程方法的基本思想. 具体的动态编程算法虽然多种多样，但是它们具有相同的表单填充方法.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-178338-1.html