第七章_动态规划

动态规划的基本原理和基本应用动态规划（Dynamic Programming）是一种通过将一个问题分解为较小的子问题并存储子问题的解来解决复杂问题的方法。

动态规划的基本原理是通过记忆化或自底向上的迭代方式来求解问题，以减少不必要的重复计算。

它在计算机科学和数学中具有广泛的应用，尤其是在优化、组合数学和操作研究等领域。

1.确定最优子结构：将原问题分解为较小的子问题，并且子问题的最优解能够推导出原问题的最优解。

2.定义状态：确定存储子问题解的状态变量和状态方程。

3.确定边界条件：确定初始子问题的解，也称为边界状态。

4.递推计算：利用状态方程将子问题的解计算出来，并存储在状态变量中。

5.求解最优解：通过遍历状态变量找到最优解。

1.背包问题：背包问题是动态规划的经典应用之一、它有多种变体，其中最基本的是0/1背包问题，即在限定容量的背包中选择物品，使得所选物品的总价值最大。

可以使用动态规划的思想来解决背包问题，确定状态为背包容量和可选物品，递推计算每个状态下的最优解。

2. 最长递增子序列：最长递增子序列（Longest Increasing Subsequence）是一种常见的子序列问题。

给定一个序列，找到其中最长的递增子序列。

可以使用动态规划来解决这个问题，状态可以定义为以第i个元素为结尾的最长递增子序列的长度，并递推计算每个状态的解。

3.矩阵链乘法：矩阵链乘法是一种优化矩阵连乘计算的方法。

给定一系列矩阵，求解它们相乘的最小计算次数。

可以使用动态规划解决矩阵链乘法问题，状态可以定义为矩阵链的起始和结束位置，递推计算每个状态下最小计算次数。

4.最短路径问题：最短路径问题是在有向图或无向图中找到两个节点之间最短路径的问题。

可以使用动态规划解决最短路径问题，状态可以定义为起始节点到一些节点的最短距离，递推计算每个状态的最优解。

动态规划（生产和存储问题）一、动态规划法的发展及其研究内容动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。

20世纪50年代初美国数学家R.E.BELLMAN等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段问题转化为一系列的单阶段问题，逐个求解创立了解决这类过程优化问题的新方法——动态规划。

1957年出版的他的名著《Dynamic Proggramming》，这是该领域的第一本著作。

动态规划问世以来，在经济管理·生产调度·工程技术和最优控制等方面得到了广泛的应用。

例如最短路线·库存管理·资源分配·设备更新·组合·排序·装载等问题，采用动态规划法求解比用其他方法更为简便。

二、动态规划法基本概念一个多阶段决策过程最优化问题的动态规划模型通常包括以下几个要素：1．阶段阶段（stage）是对整个过程的自然划分。

通常根据时间顺序或是空间特征来划分阶段，对于与时间，空间无关的“静态”优化问题，可以根据其自然特征，人为的赋予“时段”概念，将静态问题动态化，以便按阶段的顺序解优化问题。

阶段变量一般用k=1.2….n.表示。

1.状态状态(state)是我们所研究的问题（也叫系统）在过个阶段的初始状态或客观条件。

它应能描述过程的特征并且具有无后效性，即当某阶段的状态给定时，这个阶段以后的过程的演变与该阶段以前各阶段的状态无关。

通常还要求状态是可以直接或者是间接可以观测的。

描述状态的变量称为状态变量（State Virable）用s 表示，状态变量的取值集合称为状态集合，用S表示。

变量允许取值的范围称为允许状态集合(set of admissble states).用x(k)表示第k阶段的状态变量，它可以是一个数或者是一个向量。

用X(k)表示第k阶段的允许状态集合。

n 个阶段的决策过程有n+1个状态变量，x(n+1)是x(n)的演变的结果。

动态规划的基本思想动态规划是一种常用于解决具有重叠子问题和最优子结构特征的问题的算法思想。

它将问题分解成一系列子问题，并通过解决子问题构建出整个问题的最优解。

动态规划的基本思想是将原始问题转化成一个或多个相似的子问题，然后通过解决这些子问题获得原始问题的解。

这种思想在很多实际问题中都能够得到应用。

动态规划的基本流程一般包括以下几个步骤：1. 将原始问题分解为子问题：首先需要将原问题划分为多个子问题，并且确保这些子问题之间有重叠的部分。

2. 定义状态：确定每个子问题需要求解的状态，也即问题需要达成的目标。

3. 确定状态转移方程：根据子问题之间的关系，确定子问题之间的状态转移方程，即如何将子问题的解转移到原问题的解。

4. 解决首个子问题：解决最基本的子问题，获得初始状态下的解。

5. 填充状态表格：根据状态转移方程，依次求解其他子问题，并且填充状态表格。

6. 求解原问题：通过填充状态表格，在保证状态转移方程的基础上求解原问题的最优解。

动态规划的关键在于将原问题转化为子问题，通过递归或者迭代的方式求解子问题，最终获得原问题的最优解。

在这个过程中，重叠子问题的求解是动态规划的特点之一。

由于问题的子问题存在重叠，所以在求解的过程中我们可以保存已经求解过的子问题的解，避免重复计算，从而提高效率。

动态规划还要求问题具有最优子结构特征，即问题的最优解可以通过子问题的最优解构建出来。

通过利用已解决的子问题的最优解，可以有效地解决原问题。

动态规划算法在实际应用中有着广泛的应用。

它可以用于解决很多经典的问题，如最长公共子序列、0-1背包问题、最大子数组和等。

动态规划算法可以有效地解决这些问题，使得它们的时间复杂度得到了有效的降低。

总结来说，动态规划的基本思想是将原始问题转化为子问题，并通过解决子问题构建整个问题的最优解。

动态规划算法通过保存已经解决的子问题的解来避免重复计算，从而提高算法的效率。

动态规划算法在实际应用中具有广泛的应用，是解决具有重叠子问题和最优子结构特征的问题的常用算法思想。

第七章动态规划｛最长公共子序列、矩阵链乘、点对最短路径｝仅供参考7.5用算法LCS来找出两个字符串A=”xzyzzyx”和B=”zxyyzxz”的最长公共子序列的长度。

给出一个最长公共子序列。

解：算法LCS填表过程如下：由回溯法以求得最长公共子序列（长度为4）有以下两个：1.（上行方向回溯）:xyyz，逆序zyyx为所求。

2.（左行方向回溯）:zzyx，逆序xyzz为所求。

7.11对于以下5个矩阵应用算法MATCHAINM1：2*3，M2：3*6，M3：6*4，M4：4*2，M5：2*7 （a）找出这5个矩阵相乘需要的最小数量算法的次数（即C[1,5]）。

（b）请给出一个括号化表达式，使在这种次序下达到乘法的次数最少。

解：矩阵链乘算法MATCHAIN。

建立矩阵C[n][n],其中Cij表示矩阵i到j的链乘的最小次数。

递归式如下：{}{)(,0,**],[]1,[min 1],[j i if j k i r r r j k C k i C j k i j i C =<=<++-+=目标为C[1,n]。

过程如下表：M1:2×3 M2:3×6 M3:6×4 M4:4×2 M5:2×7 首先，为了找出这五个矩阵相乘需要的最少数量乘法的次数的结合方法，使用动态规划方法，填写二维表C 。

r 为记录顺序规模的数组｛2，3，6，4，2，7｝. 动态规划的填表公式如下：C[i,j]=min{C[i,k-1]+C[k,j]+r i r k r j+1}，并且通过加括号指出当前规模的结合方式。

所以，这五个矩阵相乘需要的最少数量乘法的次数为：124 最佳乘法结合次序为如下表达式：(M1(M2(M3M4)))M57.15在如图7.7所示的含权有向图上执行所有点对最短路径算法。

解：记L[i,j]为初始状态点i 到点j的路径长；k j i d ,为矩阵k D 的第i 行j 列元素，表征从点i 到点j ，除了可能经过顶点1、顶点2或者同时经过他们以外，不经过任何其他顶点的最短路径，等等。

第七章 动态规划主要内容2动态规划的基本概念动态规划的逆推解法运筹学13动态规划的应用4动态规划的基本方程2动态规划的基本方程例1：如图所示线路网络，求A到G的最短路线。

AB 1B 2C 1C 2C 3C 4D 1D 2D 3E 1E 2E 3F 1F 2G538761366835338422123335526643最短路线的性质：如果由起点A经过P点和H点而到达终点G是一条最短路线，则由点P出发经过H点到达点G的这条子路线，必定是从点P 到点G的最短路线。

根据最短路线的性质，寻找最短路线的方法，就是从最后一段开始，由后向前逐步递推，求出各点到G 点的最短路线。

1234562动态规划的基本方程运筹学k=6第六阶段f6(F1)=4f6(F2)=3F1F2G43s6=｛F1,F2｝式12动态规划的基本方程k =5第五阶段f 5(E 1)=min ｛7,8｝=7s 5=｛E 1,E 2,E 3｝E 1E 2E 3F 1F 2G35526643()()()()()73543min ,,min 262151611515=⎭⎬⎫⎩⎨⎧++=⎭⎬⎫⎩⎨⎧++=F f F E d F f F E d E f ①:d 5(E 1,F 1)+f 6(F 1)=3+4=7②:d 5(E 1,F 2)+f 6(F 2)=5+3=8()115F E u =E 1→F 1→G2动态规划的基本方程k=5第五阶段s k=｛E1,E2,E3｝E1 E2 E3F1F2G 355 26 643()()()()()73543min,,min262151611515=⎭⎬⎫⎩⎨⎧++=⎭⎬⎫⎩⎨⎧++=FfFEdFfFEdEf()115FEu= ()()()()()53245min,,min262251612525=⎭⎬⎫⎩⎨⎧++=⎭⎬⎫⎩⎨⎧++=FfFEdFfFEdEf()225FEu= ()()()()()93646min,,min262351613535=⎭⎬⎫⎩⎨⎧++=⎭⎬⎫⎩⎨⎧++=FfFEdFfFEdEf()235FEu=2动态规划的基本方程k =4第四阶段s 4=｛D 1,D 2,D 3｝()()()()()75272min ,,min 252141511414=⎭⎬⎫⎩⎨⎧++=⎭⎬⎫⎩⎨⎧++=E f E D d E f E D d D f ()214E D u =D 1D 2D 3E 1E 2E 3F 1F 2G22123335526643()()()()()69251min ,,min 353242522424=⎭⎬⎫⎩⎨⎧++=⎭⎬⎫⎩⎨⎧++=E f E D d E f E D d D f ()224E D u =()()()()()89353min ,,min 353342523434=⎭⎬⎫⎩⎨⎧++=⎭⎬⎫⎩⎨⎧++=E f E D d E f E D d D f ()432u D E =2动态规划的基本方程k =3第三阶段s 3=｛C 1,C 2,C 3,C 4｝()()()()()136876min ,,min 242131411313=⎭⎬⎫⎩⎨⎧++=⎭⎬⎫⎩⎨⎧++=D f D C d D f D C d C f ()113D C u =C 1C 2C 3C 4D 1D 2D 3E 1E 2E 3F 1F 2G6835338422123335526643()()()()()106573min ,,min 242231412323=⎭⎬⎫⎩⎨⎧++=⎭⎬⎫⎩⎨⎧++=D f D C d D f D C d C f ()123D C u =()()()()()98363min ,,min 343332423333=⎭⎬⎫⎩⎨⎧++=⎭⎬⎫⎩⎨⎧++=D f D C d D f D C d C f ()233D C u =()()()()()128468min ,,min 343432424343=⎭⎬⎫⎩⎨⎧++=⎭⎬⎫⎩⎨⎧++=D f D C d D f D C d C f ()343D C u =2动态规划的基本方程k =2第二阶段s 2=｛B 1,B 2｝()()()()()()()1396103131min ,,,min 33312232121311212=⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧+++=⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧+++=C f C B d C f C B d C f C B d B f ()212C B u =B 1B 2C 1C 2C 3C 4D 1D 2D 3E 1E 2E 3F 1F 2G8761366835338422123335526643()()()()()()()1612697108min ,,,min 43422333222322222=⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧+++=⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧+++=C f C B d C f C B d C f C B d B f ()322C B u =2动态规划的基本方程k =1第一阶段s 1=｛A ｝()()()()()18163135min ,,min 2221121111=⎭⎬⎫⎩⎨⎧++=⎭⎬⎫⎩⎨⎧++=B f B A d B f B A d A f ()11B A u =AB 1B 2C 1C 2C 3C 4D 1D 2D 3E 1E 2E 3F 1F 2G5387613668353384221233355266432动态规划的基本方程()11B A u =()181=A f ()1312=B f ()212C B u =()1622=B f ()322C B u =()1313=C f ()113D C u =()1023=C f ()123D C u =()933=C f ()233D C u =()1243=C f ()343D C u =()714=D f ()214E D u =()624=D f ()224E D u =()834=D f ()234E D u =()715=E f ()115F E u =()525=E f ()225F E u =()935=E f ()235F E u =()416=F f ()G F u =16()326=F f ()G F u =26计算结果汇总A →B 1B 1→C 2C 2→D 1D 1→E 2E 2→F 2F 2→GA →B 1→C 2→D 1→E 2→F 2→G2动态规划的基本方程递推关系()()()()(){} ()⎪⎩⎪⎨⎧==+=+1,2,3,4,5,6,,min771ksfsufsusdsfkkkkkkkukkk边界条件递推关系一般形式()()()()(){}()⎪⎩⎪⎨⎧-==+=+++1,,1,,0,111nnksfsufsusvoptsfnnkkkkkkkukkk()()()()(){}()⎪⎩⎪⎨⎧-==⨯=+++1,,1,,1,,111nnksfsufsusvoptsfnnkkkkkkkukkk加法合成乘法合成2动态规划的基本方程动态规划的最优性原理：作为整个过程的最优策略，无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。