7-动态规划.pptVIP

动态规划 动态规划是运筹学的一个分支,是求解决策过程最优化的数学方法.20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,把多阶段过程转化为一系列的阶段问题,逐个求解,创立了解决这类过程最优化问题的新方法—动态规划.他于1957年出版了Dynamic Programming.这是该领域的第一本著作. 动态规划是用来解决多阶段决策过程最优化的一种数学方法。其特点在于，它可以把一个n 维决策问题变换为几个一维最优化问题，从而一个一个地去解决。 需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。 例1、最短路问题 A-B 决策树法(枚举) 可以枚举出20条路径，其中最短的路径长度为16 表现为明显的阶段性 一条从A 到B 的最短路径中的任何一段都是最短的 动态规划的基本概念及递推公式 状态(每阶段初始的出发点) 最短路问题中，各个节点就是状态 生产库存问题中，库存量是状态 物资分配问题中，剩余的物资量是状态 控制变量(决策变量) 最短路问题中，走哪条路 生产库存问题中，各阶段的产品生产量 物资分配问题中，分配给每个地区的物资量 阶段的编号与递推的方向 一般采用反向递推，所以阶段的编号也是逆向的 当然也可以正向递推 动态规划的步骤 1、确定问题的阶段和编号 2、确定状态变量 用 Sk 表示第 k 阶段的状态变量及其值 3、确定决策变量 用 xk 表示第 k 阶段的决策变量，并以 xk*表示该阶段的最优决策 4、状态转移方程 sk-1= g(sk, xk) 反向编号 sk+1= g(sk, xk) 正向编号 5、直接效果 直接一步转移的效果 dk(sk, xk) 6、总效果函数 指某阶段某状态下到终端状态的总效果，它是一个递推公式 动态规划的步骤 hk 是一般表达形式，求当前阶段当前状态下的阶段最优总效果 (1) 如最短路问题，是累加形式，此时有 实例：求下图中从A到E的最短路径 可分成4个阶段：A到B、B到C、C到D、D到E ；逐次作出决策，构成从A到E 的一条路径；状态集S1={A}, S2={B1, B2, B3}, S3={C1,C2, C3}, S4={D1, D2}, S5={E},直接效果d 为两个相邻节点之间的长度；fk(sk)为从sk到E的最短路径长度,f1(A)是从A到E的最短距离，即最优策略的值。 数字三角形问题 1．问题描述 给定一个具有N层的数字三角形，从顶至底有多条路径，每一步可沿左斜线向下或沿右斜线向下，路径所经过的数字之和为路径得分，请求出最小路径得分。 算法设计 采用状态表示法二求解最大权值路径： 最大子矩阵:Zju 1074: To the Max 【问题描述】 在一次战争中一个英勇的士兵救了国王。战后，国王为了表示感谢决定赏赐给他一块封地。现在有一个正方形区域，由许多小正方形区域组成。每块土地都有每年可以产生的利润。如图： 输入输出 Input： 先输入一个正整数n表示正方形边长。后边有n2个整数表示块土地的效益。 Output： 输出收益最大的子块的收益额。 Sample Input 4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 Sample Output 15 一种枚举+贪心解法 请大家给出它的动态规划解法，这里给出另外一种枚举+贪心的解法 对一维数组的最大子串我们可以用O(n)的方法求解: 花束摆放问题 1．问题描述 现在有F束不同品种的花束，同时有至少同样数量的花瓶被按顺序摆成一行，其位置固定于架子上，并从1至V按从左到右顺序编号，V是花瓶的数目(F≤V)。花束可以移动，并且每束花用1至F的整数唯一标识。标识花束的整数决定了花束在花瓶中排列的顺序，如果ij，花束i必须放在花束j左边的花瓶中。每个花瓶只能放一束花。如果花瓶的数目大于花束的数目，则多余的花瓶空置。 每一个花瓶都具有各自的特点。因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以一美学值(一个整数)来表示，空置花瓶的美学值为零。为取得最佳美学效果，必须在保持花束顺序的前提下，使花束的摆放取得最大的美学值。请求出具有最大美学值的一种摆放方式。 2．解题思路 状态表示法一： 设A(i,j)表示第i种花束摆在第j个花瓶中获得的美学值。S(i,k)表示第i种花束摆在第k个花瓶中时(这里k≥i)，前i种花束能够获得的最大美学值(之和)。这样，原问题的最优值可以通过计算max{S(F,