● （5）第三次计算结点为B1，B2，B3，而决 策输出结点可能为C1，C2，C3。仿前计算可 得Bl，B2，B3的决策路径为如下情况。 ● Bl:B1C1费用 12+8=20， 路径:B1+C1+D1+E B2:B2C1费用 6+8=14， 路径:B2+C1+D1+E B3:B2C2费用 12+7=19，路径:B3+C2+D2+E ● 此时也无法定下第一，二，三阶段的城市哪 三个将在整体的最优决策路径上。 ● （6）第四次计算结点为A，决策输出结点可 能为B1，B2，B3。同理可得决策路径为 ● A：AB2，费用5+14=19，路径 A+B2+C1+D1+E。 ● 此时才正式确定每个子问题的结点中，哪一 个结点将在最优费用的路径上。19将是最短 路径的结果 ● 显然这种计算方法，符合最优原理。 ● 子问题的决策中，只对同一城市（结点）比 较优劣。而同一阶段的城市（结点）的优劣 要由下一个阶段去决定。
数塔
● 如下图所示的数塔，从顶部出发，在每一结点可以选择向左下走或是 向右下走，一直走到底层，要求找出一条路径，使路径上的数的和最 大。数塔层数用n表示，1<=n<=100。 ● 【分析】对于这一问题，很容易想到用枚举的方法（深度搜索法）去 解决，即列举出所有路径并记录每一条路径所经过的数字总和。然后 寻找最大的数字总和，这一想法很直观，很容易编程实现。 ● 但是当行数很大时，当三角形的行数等于100时，其枚举量之大是可 想而知的，用枚举法肯定超时，甚至根本不能得到计算结果，必须用 动态规划法来解。
动态规划适合解决什么样的问题
● 准确地说，动态规划不是万能的，它只适于解决一定条件的最优策略 问题。 ● (1)状态必须满足最优化原理； (2)状态必须满足无后效性 ● 1、动态规划的最优化原理是指无论过去的状态和决策如何，对前面 的决策所形成的当前状态而言，余下的诸决策必须构成最优策略。 ● 可以通俗地理解为子问题的局部最优将导致整个问题的全局最优在上 例最短路径问题中，A到E的最优路径上的任一点到终点E的路径也必 然是该点到终点E的一条最优路径，满足最优化原理。 ● 动态规划的无后效性原则指某阶段的状态一旦确定，则此后过程的演 变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”， 当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的 状态去影响过程未来的演变。具体地说，如果一个问题被划分各个阶 段之后，阶段 I 中的状态只能由阶段 I+1 中的状态通过状态转移方程 得来，与其他状态没有关系，特别是与未发生的状态没有关系，这就 是无后效性。
怎样用动态规划法解题
● program datasjx; const maxn=100; var n,i,j:integer; a:array[1..maxn,1..maxn] of integer; f:array[1..maxn,1..maxn] of integer; maxsum:integer; begin readln(n); for i:=1 to n do for j:=1 to i do read(a[i,j]); fillchar(f,sizeof(f),0); f[1,1]:=a[1,1]; for i:=2 to n do begin f[i,1]:=a[i,1]+f[i-1,1]; for j:=2 to i do if f[i-1,j-1]>f[i-1,j] then f[i,j]:=a[i,j]+f[i-1,j-1] else f[i,j]:=a[i,j]+f[i-1,j]; end; maxsum:=0;
怎样用动态规划法解题
● 1.逆推法: ● 按三角形的行划分阶段，若行数为 n，则可把问 题看做一个n-1个阶段的决策问题。先求出第n-1 阶段(第n-1行上各点)到第n行的的最大和，再依 次求出第n-2阶段、第n-3阶段……第1阶段(起始 点)各决策点至第n行的最佳路径。 ● 设：f[i,j]为从第i阶段中的点j至第n行的最大的数字 和； 则: f[n,j]=a[n,j] 1<=j<=n ● f[i,j]=max{a[i,j]+f[i+1,j],a[i,j]+f[i+1,j+1]} 1<=j<=i. ● f[1,1]即为所求。
动态规划---复习篇
Dynamic Programming
多阶段决策过程的最优化问题
● 1、问题的提出 ● 首先，例举一个典型的且很直观的多阶段决策问题: [例] 下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由A>E。求A->E的最省费用。
● 如图从A到E共分为4个阶段，即第一阶段从A 到B，第二阶段从B到C，第三阶段从C到D，第 四阶段从D到E。 ● 除起点A和终点E外，其它各点既是上一阶段的 终点又是下一阶段的起点。 ● 例如从A到B的第一阶段中，A为起点，终点有 B1，B2，B3三个，因而这时走的路线有三个 选择，一是走到B1，一是走到B2，一是走到 B3。若选择B2的决策，B2就是第一阶段在我 们决策之下的结果，它既是第一阶段路线的终 点，又是第二阶段路线的始点。在第二阶段， 再从B2点出发，对于B2点就有一个可供选择的 终点集合(C1，C2，C3)；若选择由B2走至C2 为第二阶段的决策，则C2就是第二阶段的终点， 同时又是第三阶段的始点。同理递推下去，可 看到各个阶段的决策不同，线路就不同。 ● 很明显，当某阶段的起点给定时，它直接影响 着后面各阶段的行进路线和整个路线的长短， 而后面各阶段的路线的发展不受这点以前各阶 段的影响。（无后效性） ● 故此问题的要求是：在各个阶段选取一个恰当 的决策，使由这些决策组成的一个决策序列所 决定的一条路线，其总路程最短。
● 动态规划的最优化概念是在一定条件下，找到一 种途径，在对各阶段的效益经过按问题具体性质 所确定的运算以后，使得全过程的总效益达到最 优。 ● 应用动态规划要注意阶段的划分是关键，必须依 据题意分析，寻求合理的划分阶段(子问题)方法。 ● 而每个子问题是一个比原问题简单得多的优化问 题。而且每个子问题的求解中，均利用它的一个 后部子问题的最优化结果，直到最后一个子问题 所得最优解，它就是原问题的最优解。
● （1）由目标状态E向前推，可以分成四个 阶段，即四个子问题。如上图所示。 ● （2）策略：每个阶段到E的最省费用为本 阶段的决策路径。 ● （3）D1，D2是第一次计算的结点。他们 到E都只有一种费用，在D1框上面标5，D2 框上面标2。目前无法定下，那一个点将在 全程最优策略的路径上。第二阶段计算中， 5，2都应分别参加计算。 ● （4）C1，C2，C3是第二次计算结点，他 们到D1，D2各有两种费用。此时应计算 C1，C2，C3分别到E的最少费用。 ● C1的决策路径是 min{（C1D1）， （C1D2）}。计算结果是C1+D1+E，在C1 框上面标为8。(程序中用数组保存记录） 同理C2的决策路径计算结果是C2+D2+E， 在C2框上面标为7。 同理C3的决策路径计算结果是C3+D2+E， 在C3框上面标为12。 此时也无法定下第一，二阶段的城市那二 个将在整体的最优决策路径上。
● 在此例的多阶段决策问题中，各个阶段 采取的决策，一般来说是与时间有关的， 决策依赖于当前状态，又随即引起状态 的转移，一个决策序列就是在变化的状 态中产生出来的，故有“动态”的含义， 称这种解决多阶段决策最优化问题的方 法为动态规划方法。 ● 与穷举法相比，动态规划的方法有两个 明显的优点: (1)大大减少了计算量 (2)丰富了计算结果 ● 从此例的求解结果中，我们不仅得到由 A点出发到终点E的最短路线及最短距 离，而且还得到了从所有各中间点到终 点的最短路线及最短距离，这对许多实 际问题来讲是很有用的。
怎样用动态规划法解题
program datasjx; const maxn=100; var n,i,j:integer; a:array[1..maxn,1..maxn] of integer; f:array[1..maxn,1..maxn] of integer; begin readln(n); for i:=1 to n do for j:=1 to i do read(a[i,j]); for i:=1 to n do f[n,i]:=a[n,i]; for i:=n-1 downto 1 do for j:=1 to i do if f[i+1,j]>f[i+1,j+1] then f[i,j]:=a[i,j]+f[i+1,j] else f[i,j]:=a[i,j]+f[i+1,j+1]; writeln(f[1,1]); end.
● ●● ●Fra bibliotek用动态规划法解 题的一般模式
● 动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通 过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列， 同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。动 态规划的设计都有着一定的模式，一般要经历以下几个步骤。 ● (1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划 分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题 就无法求解。 ● (2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况 用不同的状态表示出来。当然，状态的选择要满足无后效性。 ● (3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系， 状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果 确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据 相邻两段各状态之间的关系来确定决策。 ● (4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终 止条件或边界条件。 ● (5)程序设计实现：动态规划的主要难点在于理论上的设计，一旦设计完成， 实现部分就会非常简单。