例550M背包问题(向后处理策略) ●●●●● ●●●● ●●0 设f(x)是KNAP(1X)的最优解。 ●●● ●●●● 则,fn(M)=KNAP(1,n,M) 向后递推关系式: f,(X)=maxi1 X),- X-Wi)+pi] 初始值: 0X≥0 f0(X)= 0X<0 2021/28
2021/2/8 例5.5 0/1背包问题（向后处理策略） 设fi (x)是KNAP(1,i,X)的最优解。 则，fn (M) = KNAP(1,n,M) 向后递推关系式： fi (X)=max{fi-1 (X),fi-1 (X-wi )+pi } 初始值： 0 X≥0 f0 (X) = -∞ X＜0
●●●●● 例5.6k段图问题(向后处理策略) ●●●● ●●0 ●●● 设 ●●●● k-1,jk-1 ∈Vk1,1kpk1Vk1|=pk1 Vk-1,jk-1 是由s到Vk-1,的最短路径,则s到t的最短路径是 k-1,k ∈V1,1pk}中最短的那条路径。 若s,v2V3,…,p…,vk1t是s到t的一条最短路径,v,是其中的一 个中间点,则s2V3…,和vpVk1t分别是由s到v和v到t的最 短路径(最优性原理) 从s到V中的结点j的最短路径将是: min(i v: v ∈v,1Sj≤p) J 2021/2/8
2021/2/8 例5.6 k段图问题（向后处理策略） 设 ∈Vk-1，1≤jk-1≤pk-1，|Vk-1 |=pk-1 ; 是由s到 的最短路径，则s到t的最短路径是 { t | ∈Vk-1 ,1≤jk-1≤pk-1 }中最短的那条路径。 若s,v2 ,v3 ,…,vi ,…,vk-1 ,t是s到t的一条最短路径，vi是其中的一 个中间点，则s,v2 ,v3 ,…,vi和 vi ,…,vk-1 ,t分别是由s到vi和vi到t的最 短路径（最优性原理） 从s到Vi中的结点j i的最短路径将是： min( { | ∈Vi ,1≤ji≤pi }) 1 1, − k− k j v −1, −1 k vk j 1 1, − k− k j v i i j v , i i j v , i i j v , 1 1, − − k k j v 1 1, − k− k j v 1 1, − k− k j v
●●● 动态规划的基本思想: p●● (1)动态规划方法的关键在于正确写出基本的递推关系 式和恰当的边界条件。要做到这一点,必须将问题的过程 分成几个相互联系的阶段,恰当选择状态变量,决策变量 和定义最优值函数,从而把一个大问题化成一簇同类型的 子问题,然后逐个求解。即从边界条件开始,逐段递推寻 优,在每一个子问题的求解中,均利用了它前面的子问题 的最优化结果,依次进行,最后一个子问题的最优解,就 是整个问题的最优解。 (2)在多阶段决策过程中,动态规划方法是既把当前 段和未来各段分开,又把当前的效益和未来效益综合起来 考虑的一种最优化方法。因此,每段决策的选取是从全局 来考虑的,与该段的最优选择答案一般是不同的。 (3)在求整个问题的最优策略时,由于初始状态是已知 的,而每段的决策都是该段状态的函数,故最优策略所经 的各段状态便可逐次变换得到,从而确定最优路线
2021/2/8 动态规划的基本思想： （1）动态规划方法的关键在于正确写出基本的递推关系 式和恰当的边界条件。要做到这一点，必须将问题的过程 分成几个相互联系的阶段，恰当选择状态变量，决策变量 和定义最优值函数，从而把一个大问题化成一簇同类型的 子问题，然后逐个求解。即从边界条件开始，逐段递推寻 优，在每一个子问题的求解中，均利用了它前面的子问题 的最优化结果，依次进行，最后一个子问题的最优解，就 是整个问题的最优解。 （2）在多阶段决策过程中，动态规划方法是既把当前一 段和未来各段分开，又把当前的效益和未来效益综合起来 考虑的一种最优化方法。因此，每段决策的选取是从全局 来考虑的，与该段的最优选择答案一般是不同的。 （3）在求整个问题的最优策略时，由于初始状态是已知 的，而每段的决策都是该段状态的函数，故最优策略所经 的各段状态便可逐次变换得到，从而确定最优路线
●●●●● ●●●● ●●0 关于动态规划求解策略的进一步说明 ●●● ●●●● >采用枚举法:若问题的决策序列由n次决策构成, 而每次决策有p种选择,则可能的决策序列将有 >利用动态规划策略的求解过程中保存了所有子问 题的最优解,而舍去了所有不能导致问题最优解 的次优决策序列 >动态规划:可能有多项式的计算复杂度。 2021/2/8
2021/2/8 关于动态规划求解策略的进一步说明 ➢ 采用枚举法：若问题的决策序列由n次决策构成， 而每次决策有p种选择，则可能的决策序列将有 pn个。 ➢ 利用动态规划策略的求解过程中保存了所有子问 题的最优解，而舍去了所有不能导致问题最优解 的次优决策序列 ➢ 动态规划：可能有多项式的计算复杂度
●●●● 与非线性规划相比,动态规划的优点: (1)易于确定全局最优解。动态规划方法是一种逐步改善法,它把 原问题化为一系列结构相似的最优化子问题,而每个子问题的变量 个数比原问题少的多,约束集合也要简单得多。 (2)能得到一簇解,有利于分析结果 (3)能利用经验,提高求解的效率。动态规划方法反映了过程逐段 演变的前后联系,较之非线性规划与实际过程联系得更紧密。 不足之处: (1)没有一个统一的标准模型可供应用。 (2)应用的局限性。要求状态变量满足“无后效性”条件,不少实 际问题在取其自然特征作为状态变量往往不能满足这条件。 (3)在数值求解中,存在“维数障碍”。在计算机中,每递推一段 必须把前一段的最优值函数在相应的状态集合上的全部值存入内存 中。当维数增大时,所需的内存量成指数倍增长。 2021/2/8
2021/2/8 与非线性规划相比，动态规划的优点： （1）易于确定全局最优解。动态规划方法是一种逐步改善法，它把 原问题化为一系列结构相似的最优化子问题，而每个子问题的变量 个数比原问题少的多，约束集合也要简单得多。 （2）能得到一簇解，有利于分析结果 （3）能利用经验，提高求解的效率。动态规划方法反映了过程逐段 演变的前后联系，较之非线性规划与实际过程联系得更紧密。 不足之处： （1）没有一个统一的标准模型可供应用。 （2）应用的局限性。要求状态变量满足“无后效性”条件，不少实 际问题在取其自然特征作为状态变量往往不能满足这条件。 （3）在数值求解中，存在“维数障碍”。在计算机中，每递推一段， 必须把前一段的最优值函数在相应的状态集合上的全部值存入内存 中。当维数增大时，所需的内存量成指数倍增长