当前位置:首页 >> IT/计算机 >>

动态规划理论(精华)


动态规划理论
一.动态规划的逆向思维法
动态规划是一种思维方法,没有统一的、具体的模式。动态规划可以从多方面 去考察,不同的方面对动 态规划有不同的表述。我们不打算强加一种统一的表述,而是从多个角度对动 态规划的思维方法进行讨 论,希望大家在思维具体问题时,也能够从多个角度展开,这样收获会更大。 逆向思维法是指从问题目标状态出发倒推回初始状态或边界状态的思维方 法。如果原问题可以分解成 几个本质相同、规模较小的问题,很自然就会联想到从逆向思维的角度寻求问 题的解决。 你也许会想,这种将大问题分解成小问题的思维不就是分治法吗?动态规划 是不是分而治之呢?其实, 虽然我们在运用动态规划的逆向思维法和分治法分析问题时,都使用了这种将 问题实例归纳为更小的、 相似的子问题,并通过求解子问题产生一个全局最优值的思路,但动态规划不 是分治法:关键在于分解 出来的各个子问题的性质不同。 分治法要求各个子问题是独立的(即不包含公共的子问题),因此一旦递归地 求出各个子问题的解后, 便可自下而上地将子问题的解合并成原问题的解。如果各子问题是不独立的, 那么分治法就要做许多不 必要的工作,重复地解公共的子问题。 动态规划与分治法的不同之处在于动态规划允许这些子问题不独立(即各子 问题可包含公共的子问题) ,它对每个子问题只解一次,并将结果保存起来,避免每次碰到时都要重复计 算。这就是动态规划高效

的一个原因。 动态规划的逆向思维法的要点可归纳为以下三个步骤: (1)分析最优值的结构,刻画其结构特征; (2)递归地定义最优值;0 (3)按自底向上或自顶向下记忆化的方式计算最优值。 【例题 1】背包问题描述: 有一个负重能力为 m 的背包和 n 种物品,第 i 种物品的价值为 v,重量为 w。在不超过背包负重能力的前 提下选择若干个物品装入背包,使这些的物品的价值之和最大。每种物品可以 不选,也可以选择多个。 假设每种物品都有足够的数量。 分析: 从算法的角度看,解决背包问题一种最简单的方法是枚举所有可能的物品的 组合方案并计算这个组合 方案的价值之和,从中找出价值之和最大的方案。显然,这种靠穷举所有可能 方案的方法不是一种有效 的算法。 但是这个问题可以使用动态规划加以解决。下面我们用动态规划的逆向思维 法来分析这个问题。 (1)背包问题最优值的结构 动态规划的逆向思维法的第一步是刻画一个最优值的结构,如果我们能分析 出一个问题的最优值包含 其子问题的最优值,问题的这种性质称为最优子结构。一个问题的最优子结构 性质是该问题可以使用动 态规划的显著特征。 对一个负重能力为 m 的背包,如果我们选择装入一个第 i 种物品,那么原 背包问题就转化为负重能力 为 m-w 的子背包问题。原背包问题的最优值包含这个子背包问题的最优值。若 我们用背包的负重能力来 划分状态,令状态变量 s[k]表示负重能力为 k 的背包,那么 s[m]的值只取决于 s[k](k≤m)的值。因此背包

问题具有最优子结构。 (2)递归地定义最优值 动态规划的逆向思维法的第二步是根据各个子问题的最优值来递归地定义原 问题的最优值。对背包问 题而言,有状态转移方程: /max{s[k-w]+v}(其中 1≤i≤n,且 k-w≥0) s[k]= 若 k>0 且存在 1≤i≤n 使 k-w≥0, \ 0 否则。 有了计算各个子问题的最优值的递归式,我们就可以直接编写对应的程序。 下述的函数 knapsack 是输 入背包的负重能力 k,返回对应的子背包问题的最优值 s[k]: function knapsack(k:integer):integer; begin knapsack:=0; for i:=1 to n do if k-w>=0 then begin t:=knapsack(k-w)+v; if knapsack < t then knapsack:=t; end; end; 上述递归算法在求解过程中反复出现了一个子问题,且对每次重复出现的子 问题都要重新解一次,这 需要多花费不少时间。下面先考虑一个具体的背包问题。例如,当 m=3,n=2,v[1]=1,w[1]=1,v[2]=2,w[2]=2, 图 1 示出了由调用 knapsack(3)所产生的递归树,每一个结点上标有参数 k 的值,请注意某些数出现了 多次。 3 /\ 2 /\ 1 / 0 0 1 \ 0

图1 例如,knapsack(1)被引用了两次:在计算 knapsack(3)和 knapsack(2)中分 别被引用;而 knapsack(0) 更是被引用了三次。如果 knapsack(1)和 knapsack(0)每次都要被重新计算,则 增加的运行时间相当可观 。 下面,我们来看看动态规划是如何解决这个问题的。 (3)按自顶向下记忆化或自底向上的方式求最优解 一般地,如果一个解最优化问题的递归算法经常反复地解重复的子问题,而 不是总在产生新的子问题 时,我们说该最优化问题包含重迭子问题。这类问题不宜用分治法求解,因为 分治法递归的每一步要求 产生相异的子问题。在这种情况下,采用动态规划是很合适的,因为该方法对 每一个子问题只解一次, 然后把解存放在一个表中,以便在解同样的子问题时查阅,充分利用了重迭子 问题。一般来说,解决重 迭子问题的方式有两种。 ①自顶向下的记忆化方式 该方式的程序流程基本按照原问题的递归定义,不同的是,它专门设置了一 张表,以记忆在求解过程 中得出的所有子问题的解。一个记忆的递归算法为每个子问题的解在表中记录 一个表项。初始时每个表 项都包含一个特殊值,以示该表项的解有待填入。例如背包问题中: s=-1;(0≤i≤m) 当在递归算法的执行中第一次遇到一个子问题时(即 s=-1),计算其解并填入表 中,以后每遇到该子问题 ,只要查看表中先前填入的值即可。 下面,我们按照自上而下的记忆化方式,写出求背包问题的递归算法。 函数 memorized_knapsack 输入背包的负重能力 k,返回背包问题的解 s[k]。s 表应设为全局变量,使得

函数执行后,传出所有子问题的解 s(0≤i≤m)。 function memorized_knapsack(k:integer):integer; begin if s[k]=-1 then begin s[k]:=0; for i:=1 to n do if k-w>=0 then begin t:=memorized_knapsack(k-W)+V; if s[k] < t then s[k]:=t; end; end; memorized_knapsack:=s[k]; end; 我们在主程序通过调用 memorized_knapsack(m)即可获得背包问题的解。 显然这种自顶向下记忆化的算法效率比重复解重迭子问题的 knapsack 算法 要强一些。此外,在程序中 加入判别哪些子问题需要求解的语句,只解那些肯定要解的子问题,从而节省 了时间。 ②自底向上的方式 假设我们要解决在分析函数 knapsack 当中提出的那个具体的背包问题。观 察一下在调用 memorized_knapsack(4)的过程中,s[k]被计算出来的顺序。我们发现,首先是 s[0]被计算出来,然后是 s[1],s[2],最后 s[3]被计算出来,这与调用的次序正好相反。 动态规划的执行方式是自底向上,所有的子问题计算一次,充分利用重迭子 问题。因此,我们很自然 就想到与这种自底向上的执行方式相应的采用自底向上的方式递推所有子问题 的最优值。 我们知道,计算负重能力为 k 的背包问题的解仅依赖于计算负重能力小于 k 的背包问题的解,因此填 s

表的方式与解决负重能力递增的背包问题相对应: 最初设定负重能力为 0 的背包问题的解 s[0]=0。然后依次考虑负重能力为 1,2,…,m 的背包问题的解 。每填入一个 s[k](0≤k≤m)时,充分利用所有重迭子问题的解:s[kw](0≤i≤n,k-w≥0) 下面是按照自底向上方式计算背包问题的算法流程。过程 knapsack_order 输入背包的负重能力 k,s 表 设为全局变量。过程执行后所有子问题的解通过 s 表传给主程序。 procedure knapsack_order(k:integer); begin for i:=1 to k do s:=0; for j:=1 to k do for i:=1 to n do if j-w>=0 then begin t:=s[j-w]+v; if s[j] < t then s[j]:=t; end; end; 我们在主程序调用 knapsack_order(m),过程执行后 s[m]即为背包问题的 解。 最后,我们分析一下背包问题的动态规划解法的复杂度。所需的存储开销主 要在 s 表上,其空间复杂 度是 O(m)。而整个 s 表用两重循环求出,循环内语句的执行只需常数时间,因 此,时间复杂度是 O(m,n)。 自顶向下的记忆化是动态规划的一种变形。动态规划的执行方式是自底向 上,因此自底向上的计算方 式是与动态规划的执行方式相一致的。它无需递归代价,且维护记忆表的开销 也要小些,因此其效率通 常好于自顶向下的记忆法。 但是,在动态规划的执行过程中,并不是所有的子问题都要用到它。对某个 具体问题而言,可能有大 部分子问题的最优值是不必计算的。自底向上的计算方式无法判断那些子问题 是需要求解的,所以它将

一视同仁地处理所有的子问题,这就可能会把大量的时间都花在计算不必解决 的子问题上;而自顶向下 的记忆法可以判断那些子问题是需要求解的,只解那些肯定要解的子问题,在 这个意义上,自顶向下的 算法效率又好于自底向上。所以到底那种方式效率更高,我们要具体问题具体 分析。 最后,给出求解背包问题的程序如下: {//背包问题程序} program knapsack; const maxn=100; maxm=1000; var m,n:integer; S:array[0..maxm] of integer; v,w:array[1..maxn] of integer; {//输入数据} procedure read_data; var i:integer; begin read(m,n); for i:=1 to n do read(v,w); end; {//采用自底向上的方式求解背包问题} procedure knapsack_order; var i,j,t:integer; begin for i:=1 to m do s:=0; for j:=1 to m do for i:=1 to n do if j-w>=0 then begin t:=s[j-w]+v; if s[j] < t then s[j]:=t; end; end; {//主程序}

begin read_data; knapsack_order; writeln(s[m]); end.

二.动态规划的正向思维法
正向思维法是指从初始状态或边界状态出发,利用某种规则不断到达新的状 态,直到问题目标状态的方 法。动态规划的正向思维法,正是从已知最优值的初始状态或边界状态开始, 按照一定的次序遍历整个 状态空间,递推出每个状态所对应问题的最优值。 提出动态规划的正向思维法的根本原因,是为了摆脱逆向思维法当中那种将 大问题转化为子问题的思 维框框,提供一种新的思维方式。在正向思维法中,我们不再区分原问题和子 问题,将动态规划的过程 看成是从状态到状态的转移。我们将所有的状态构造出一个状态空间,并在状 态空间中设想一个状态网 络,若对两个状态 i,j,存在决策变量 di 使 t(i,di)=j,则向状态网络添加有 向边。给定己知最优值的初 始状态或边界状态,我们可以沿着有向边推广到未知最优值的新状态,利用状 态转移方程得到新状态的 状态变量的最优值。我们可以用这种方式遍历整个状态空间,得到每个状态的 状态变量的最优值。 因为正向思维法中不再区分原问题、子问题、子子问题,所以我们不再按照 问题被递归调用求解的相 反次序的方法确定状态最优值的计算次序。从上面我们知道可以按照状态的拓 扑序列来计算每个状态的 最优值,于是我们用一个新的名词"阶段"来描述在状态空间遍历的过程中,各 个状态最优值的计算次序

。我们将每个状态和一个阶段挂钩,前一个阶段的状态先计算,后一个阶段的 状态后计算。有的时候我 们甚至将一组状态和一个阶段挂钩,前一个阶段的那组状态先计算,后一个阶 段的那组状态后计算,而 在同一个阶段内,那些状态的计算次序可以是任意的。 动态规划的正向思维法的要点可归纳为以下三个步骤: (1)构造状态网络; (2)根据状态转移关系和状态转移方程建立最优值的递推计算式: (3)按阶段的先后次序计算每个状态的最优值。 在下一节"最短路问题"当中,我们将结合最短路问题来示范动态规划的正向 思维法。 动态规划的正向思维法带给我们什么启示呢?动态规划需要按阶段遍历整个 状态空间,因此动态规划 的效率取决于状态空间的大小和计算每个状态最优值的开销:如果状态空间的 大小是多项式的,那么应 用动态规划的算法就是多项式时间的;如果状态空间的大小是指数的,那么应 用动态规划的算法也是指 数时间的。因此,找一个好的状态划分对动态规划的效率是至关重要的。 将这个结论应用到逆向思维上,我们得出如下结果:一个问题的最优子结构 常常暗示了动态规划的状 态空间。典型的情况是,某一个特定问题可有几类"自然"的子问题,不同的子 问题往往意味着不同的最 优子结构,从而我们得到不同的状态划分方案。但是由这些不同的状态得到的 算法的效率可能差异极大 。例如,某个问题的输入是一个有序序列,有两类"自然"的子问题,一类子问 题的输入是原问题输入序 列的所有子序列,另一类子问题的输入是原问题输入序列的任意元素构成的新 序列。显然若我们采用后 者的最优子结构来建立状态,它的状态空间必然远远大于基于前者的状态空 间。那末基于后者的状态空

间的动态规划则要解许多不必要的问题,使得算法的效率骤然下降。 从动态规划的正向思维法的分析可以看出,我们从已知最优值的初始状态和 边界状态出发,利用最优 化原理,一步一步向未知的目标状态推进,直到目标状态的最优值解决。这种" 从己知推广到未知"的思 维,正是动态规划正向思维法的精髓。大家在运用动态规划的正向思维法时如 果能掌握这一点,那么就 能达到应用自如的境界。 在应用动态规划求解的问题的过程中,希望读者能够注意从题目的分析中领 会:应用动态规划解题是 富于技巧和创造性的,没有固定的模式可套;题目出现的形式多种多样,而且 大部分表面上与动态规划 看不出直接的联系。只有在充分把握其思想精髓的前提下大胆联想,才能达到 得心应手,灵活运用的境 界。

三.动态规划设计方法的一般模式
动态规划所处理的问题是一个多阶段决策问题,一般由初始状态开始,通过对 中间阶段决策的选择,达 到结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程的一条 活动路线(通常是求最优的 活动路线)。如图所示。动态规划的设计都有着一定的模式,一般要经历以下几 个步骤。 ┌───┐ ┌───┐ ┌───┐ 初始状态→│决策1│→│决策2│→…→│决策n│→结束状态 └───┘ └───┘ └───┘ 图 1 动态规划决策过程示意图 (1)划分阶段:,按照问题的时间或空间特征,把问题分为若干个阶段。在 划分阶段时,注意划分后

的阶段一定要是有序的或者是可排序的,否则问题就无法求解。 (2)确定状态和状态变量:将问题发展到各个阶段时所处于的各种客观情况 用不同的状态表示出来。 当然,状态的选择要满足无后效性。 (3)确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系, 状态转移就是根据上一阶 段的状态和决策来导出本阶段的状态。所以如果确定了决策,状态转移方程也 就可写出。但事实上常常 是反过来做,根据相邻两段各状态之间的关系来确定决策。 (4)寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终 止条件或边界条件。 (5)程序设计实现:动态规划的主要难点在于理论上的设计,一旦设计完 成,实现部分就会非常简单 。 根据上述动态规划设计的步骤,可得到大体解题框架如图 2 所示。 图 2 动态规划设计的一般模式 上述提供了动态规划方法的一般模式,对于简单的动态规划问题,可以按部 就班地进行动态规划的设 计。 下面,给出一个利用动态规划方法求解的典型例子。 【例题 6】数字三角形问题。图 3 示出了一个数字三角形宝塔。数字三角形 中的数字为不超过 100 的整 数。现规定从最顶层走到最底层,每一步可沿左斜线向下或右斜线向下走。 任务一:假设三角形行数≤10,键盘输入一个确定的整数值 M,编程确定是否 存在一条路径,使得沿着 该路径所经过的数字的总和恰为 M,若存在则给出所有路径,若不存在,则输 出"NO Answer!"字样。 任务二:假设三角形行数≤100,编程求解从最顶层走到最底层的一条路 径,使得沿着该路径所经过

的数字的总和最大,输出最大值。 输人数据:由文件输入数据,任务一中文件第一行是三角形的行数 N 和整数 值 M。以后的 N 行分别是从 最顶层到最底层的每一层中的数字。任务二中文件数据格式同任务一,只是第 一行中没有整数值 M。在例 子中任务二的文件数据表示如下: 输入:5 7 输出: 3 8 7 输出路径和最大值 8 1 0 3 8 或"No Answer!"字样。 2 7 7 4 8 1 0 4 5 2 6 5 2 7 4 4 图 3 数字三角形 4 5 2 6 5 【分析】对于这一问题,很容易想到用枚举的方法去解决,即列举出所有路径 并记录每一条路径所经过 的数字总和。然后判断数字总和是否等于给定的整数值 M 或寻找出最大的数字 总和,这一想法很直观,而 且对于任务一,由于数字三角形的行数不大(<=10),因此其枚举量不是很大, 应该能够实现。但对于任 务二,如果用枚举的方法,当三角形的行数等于 100 时,其枚举量之大是可想 而知的,显然,枚举法对于 任务二的求解并不适用。其实,只要对对任务二稍加分析,就可以得出一个结 论: 如果得到一条由顶至底的某处的一条最佳路径,那么对于该路径上的每一个 中间点来说,由顶至该中 间点的路径所经过的数字和也为最大。因此该问题是一个典型的多阶段决策最 优化的问题。算法设计与 分析如下: 对于任务一,合理地确认枚举的方法,可以优化问题的解法。由于从塔顶到 底层每次都只有两种走法

,即左或右。设"0"表示左, "1"表示右,对于层数为 N 的数字塔,从顶到底的 一种走法可用一个 N-1 位 的二进制数表示。如例中二进制数字串 1011,其对应的路径应该是:8-1-46。这样就可以用一个 N-l 位 的二进制数来模拟走法和确定解的范围。穷举出从 0 到 2n-1 个十进制数所对应 的 N-1 位二进制串对应的路 径中的数字总和,判定其是否等于 M 而求得问题的解。 对于任务二,采用动态规划中的顺推解法。按三角形的行划分阶段,若行数 为 n,则可把问题看做一 个 n-1 个阶段的决策问题。从始点出发,依顺向求出第一阶段、第二阶段…… 第 n-1 阶段中各决策点至始 点的最佳路径,最终求出始点到终点的最佳路径。 设:fk(Uk)为从第 k 阶段中的点 Uk 至三角形顶点有一条最佳路径,该路径 所经过的数字的总和最大, fk(Uk)表示为这个数字和; 由于每一次决策有两个选择,或沿左斜线向下,或沿右斜线向下,因此设: Uk1 为 k-1 阶段中某点 Uk 沿左斜线向下的点; Uk2 为 k-1 阶段中某点 Uk 沿右斜线向下的点; dk(Uk1)为 k 阶段中 Uk1 的数字;dk(Uk2)为 k 阶段中 Uk2 的数字。 因而可写出顺推关系式(状态转移方程)为: fk(Uk)=max{fk-1(Uk)+dk(Uk1),fk-1(Uk)+dk(Uk2)}(k=1,2,3,…,n) f0(U0)=0 经过一次顺推,便可分别求出由顶至底 N 个数的 N 条路径,在这 N 条路径所 经过的 N 个数字和中,最大值 即为正确答案。

四.动态规划方法实现的灵活性与技巧性
上述例子给出了一般情况下的动态规划思维过程。一些较为简单的问题可以"按 部就班"来操作,但大多 数的"动态规划"问题,特别是作为信息学竞赛中的"动态规划"问题,考察的知 识是多方面的,应用的技

巧是灵活多变的。下面给出上述例 5 变形的例子。 【例题 7】花店橱窗布置问题('99IOI 试题)。假设以最美观的方式布置花店 的橱窗,有 F 束花,每束花 的品种都不一样,同时,至少有同样数量的花瓶,被按顺序摆成一行,花瓶的 位置是固定的,并从左到 右,从 1 到 V 顺序编号,V 是花瓶的数目,编号为 1 的花瓶在最左边,编号为 V 的花瓶在最右边,花束可以移 动,并且每束花用 1 到 F 的整数惟一标识,标识花束的整数决定了花束在花瓶 中列的顺序即如果 I < J,则 花束 I 必须放在花束 J 左边的花瓶中。例如,假设杜鹃花的标识数为 1,秋海 棠的标识数为 2,康乃馨的标 识数为 3,所有的花束在放人花瓶时必须保持其标识数的顺序,即:杜鹃花必 须放在秋海棠左边的花瓶中 ,秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目,则 多余的花瓶必须空,即每 个花瓶中只能放一束花。 每一个花瓶的形状和颜色也不相同,因此,当各个花瓶中放人不同的花束时 会产生不同的美学效果, 并以美学值(一个整数)来表示,空置花瓶的美学值为 0。在上述例子中,花瓶 与花束的不同搭配所具有的 美学值,可以用如下表格表示: ┌───┬───┬───┬───┬───┬───┐ │ │花瓶 1 │花瓶 2 │花瓶 3 │花瓶 4 │花瓶 5 │ ├───┼───┼───┼───┼───┼───┤ │杜鹃花│ 7 │ 23 │ -5 │ -24 │ 16 │ ├───┼───┼───┼───┼───┼───┤ │秋海棠│ 5 │ 21 │ -4 │ 10 │ 23 │ ├───┼───┼───┼───┼───┼───┤ │康乃馨│ -21 │ 5 │ -4 │ -20 │ 20 │ └───┴───┴───┴───┴───┴───┘

根据表格,杜鹃花放在花瓶 2 中,会显得非常好看,但若放在花瓶 4 中则显 得很难看。 为取得最佳美学效果,必须在保持花束顺序的前提下,使花的摆放取得最大 的美学值,如果具有最大 美学值的摆放方式不止一种,则输出任何一种方案即可。题中数据满足下面条 件:1≤F≤100,F≤V≤ 100,-50≤AIJ≤50,其中 AII 是花束 I 摆放在花瓶 J 中的美学值。输入整数 F,V 和矩阵(AIJ),输出最大 美学值和每束花摆放在各个花瓶中的花瓶编号。 [分析]问题实际就是给定 F 束花和 V 个花瓶,以及各束花放到不同花瓶中的 美学值,要求你找出一种摆 放的方案,使得在满足编号小的花放进编号小的花瓶中的条件下,美学值达到 最大。 (1)将问题进行转化,找出问题的原型。首先,看一下上述题目的样例数据 表格。 将摆放方案的要求用表格表现出来,则摆放方案需要满足:每行选且只选一 个数(花瓶);摆放方案的 相邻两行中,下面一行的花瓶编号要大于上面一行的花瓶编号两个条件。这时 可将问题转化为:给定一 个数字表格,要求编程计算从顶行至底行的一条路径,使得这条路径所经过的 数字总和最大(要求每行选 且仅选一个数字)。同时,路径中相邻两行的数字,必须保证下一行数字的列数 大于上一行数字的惺 ? br> 看到经过转化后的问题,发现问题与例题 6 的数学三角形问题十分相 似,数字三角形问题的题意 是: 给定一个数字三角形,要求编程计算从顶至底的一条路径,使得路径所经过 的数字总和最大(要求每 行选且仅选一个数字)。同时,路径中相邻两行的数字,必须保证下一行数字的 列数与上一行数字的列数

相等或者等于上一行数字的列数加 1。 上例中已经知道:数字三角形中的经过数字之和最大的最佳路径,路径的每 个中间点到最底层的路径 必然也是最优的,可以用动态规划方法求解,对于"花店橱窗布置"问题经过转 化后,也可采取同样的方 法得出本题同样符合最优性原理。因此,可以对此题采用动态规划的方法。 (2)对问题原型动态规划方法的修改。"数字三角形"问题的动态规划方法 为:已知它是用行数来划分 阶段。假设用 a[i,j]表示三角形第 i 行的第 j 个数字,用 p [i,j]表示从最 底层到 a[i,j]这个数字的最佳 路径(路径经过的数字总和最大)的数字和,易得问题的动态转移方程为: p[n+1,j]=0 (1≤i≤n+1) p[i,j]=max{p[i+1,j],p[i+1,j+1]}+a[i,j] (1≤i≤i≤n,其中 n 为总行数) 分析两题的不同之处,就在于对路径的要求上。如果用 path 表示路径中第 i 行的数字编号,那么两题 对路径的要求就是:"数字三角形"要求 path≤path[i+1]≤path+1,而本题则 要求 path[i+1)>path。 在明确两题的不同之后,就可以对动态规划方程进行修改了。假设用 b[i, j]表示美学值表格中第 i 行 的第 j 个数字,用 q[i,j]表示从表格最底层到 b[i,j]这个数字的最佳路径 (路径经过的数字总和最大)的 数字和,修改后的动态规划转移方程为: q[i,V+1]=-∞(1≤i≤F+1) q[F,j]=b[F,j](1≤j≤V) q[i,j]=max{q[i+1,k](j<K≤V+1)}+A[I,J](1≤I≤F,1≤J≤V) 这样,得出的 max{q[1,k]} (1≤j≤V)就是最大的美学值,算法的时间复 杂度为 O(FV2)。 (3)对算法时间效率的改进。先来看一下这样两个状态的求解方法: q[i,j]=max{q[i+1,k] (j < k≤V+1)}+b[i,j] (1≤i≤F,1≤j≤V) q[i,j+1)=max{q[i+1,k] (j+1 < k≤V+1)}+a[i,j+1) (1≤i≤F, 1≤j+1≤V)

上面两个状态中求 max{q[i+1,k]}的过程进行了大量重复的比较。此时对 状态的表示稍作修改,用数 组 t[i,j]=max{q[i,k](j≤k≤V+1)}(1≤i≤F, 1≤j≤V)表示新的状态。经 过修改后,因为 q[i,j]=t [i+1,j+1]+a[i,j],而 t[i,j]=max{t[i,j+1],q[i,j}(1≤i≤F, 1≤j≤V),所以得出新的状态转移 方程: t[i,V+1]=-∞ (1≤i≤F 十 1) t[F,j]=max{t[F,j+1],b[F,j]} (1≤j≤V) t[i,j]=max{t[i,j+1],t[i+1,j+1]+a[i,j]} (1≤i≤F,1≤j≤V) 这样,得出的最大美学值为 t[1,1],新算法的时间复杂度为 O(F*V),而空 间复杂度也为 O(F*V),完全 可以满足 1≤F≤V≤100 的要求。下面给出这一问题的源程序。 {$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S+,T-,V+, X+} {$M16384,0,655360} program ex;{花店橱窗布置问题} const st1='flower.inp'; {输入文件名} st2='flower.out'; {输出文件名} var f,v:integer; {f 为花束的数量;v 为花瓶的数量} b:array[1..100,1..100] of shortint; {b[i,j]为第 i 束花放进第 j 个花瓶的美学值} t:array[1..101,1..101] of integer; {t[i,¨为将第 i 到第 f 束花放进第 j 到第 v 个花瓶所可能得到的最大美学值} procedure readp; {从文件中读入不同花束对应不同花瓶的美学值} var f1:text; i,j:integer; begin assign(f1,st1);reset(f1); readln (f1, f, v); for i:=1 to f do for j:=1 to v do read (f1, b [i, j]); close (f1); end; procedure main; {用动态规划对问题求解}

var i, j: integer; begin for i:=1 to f+1 do t[i, v+1]:=-9999; for j:=v downto 1 do if t[f, j+l] > b[f, j] then t[f,j]:=t[f, j+1] else t[f,j]:=b[f,j]; {设定动态规划的初始条件,其中-9999 表示负无穷} for i:=f-1 downto 1 do for j:= v downto 1 do begin t[i, j]:=t[i, j+1]; if t[i+1, j+1] + b[i, j] > t[i, j] then t[i, j]:=t[i+1, j+1] +b[i, j]; end; end; procedure print; {将最佳美学效果和对应方案输出到文件} var f1: text; i,j,p: integer; {为当前需确定位置的花束编号,p 为第 i 束花应插入的花瓶编号的最小值} begin assign (f1, st2); rewrite (f1); writeln (f1, t [1, 1]); p:=1; for i:=1 to f do begin {用循环依次确定各束花应插入的花瓶} j:=p; while t[i, j] =t[i, p] do inc (j); write (f1, j-1,' '); p:=j; end; writeln (f1); close (f1); end; begin readp; main; print; end. 由此可看出,对于看似复杂的问题,通过转化就可变成简单的经典的动态规 划问题。在问题原型的基

础上,通过分析新问题与原问题的不同之处,修改状态转移方程,改变问题状 态的描述和表示方式,就 会降低问题规划和实现的难度,提高算法的效率。由此可见,动态规划问题中 具体的规划方法将直接决 定解决问题的难易程度和算法的时间与空间效率,而注意在具体的规划过程中 的灵活性和技巧性将是动 态规划方法提出的更高要求。

五.应用举例.
【例题 1】最短路径问题 现有一张地图,各结点代表城市,两结点间连线代表道路,线上数字表示城市 间的距离。如图 1 所示,试 找出从结点 A 到结点 E 的最短距离。 图 1 我们可以用深度优先搜索法来解决此问题,该问题的递归式为 其中是与 v 相邻的节点的集合,w(v,u)表示从 v 到 u 的边的长度。 具体算法如下: function MinDistance(v):integer; begin if v=E then return 0 else begin min:=maxint; for 所有没有访问过的节点 i do if v 和 i 相邻 then begin 标记 i 访问过了; t:=v 到 i 的距离+MinDistance(i); 标记 i 未访问过; if t<min then min=t; end; end; end;

开始时标记所有的顶点未访问过,MinDistance(A)就是从 A 到 E 的最短距离。 这个程序的效率如何呢?我们可以看到,每次除了已经访问过的城市外,其他 城市都要访问,所以时间 复杂度为 O(n!),这是一个"指数级"的算法,那么,还有没有更好的算法呢? 首先,我们来观察一下这个算法。在求从 B1 到 E 的最短距离的时候,先求出从 C2 到 E 的最短距离;而在求 从 B2 到 E 的最短距离的时候,又求了一遍从 C2 到 E 的最短距离。也就是说, 从 C2 到 E 的最短距离我们求了两 遍。同样可以发现,在求从 C1、C2 到 E 的最短距离的过程中,从 D1 到 E 的最 短距离也被求了两遍。而在整 个程序中,从 D1 到 E 的最短距离被求了四遍。如果在求解的过程中,同时将求 得的最短距离"记录在案", 随时调用,就可以避免这种情况。于是,可以改进该算法,将每次求出的从 v 到 E 的最短距离记录下来, 在算法中递归地求 MinDistance(v)时先检查以前是否已经求过了 MinDistance(v),如果求过了则不用重 新求一遍,只要查找以前的记录就可以了。这样,由于所有的点有 n 个,因此 不同的状态数目有 n 个,该 算法的数量级为 O(n)。 更进一步,可以将这种递归改为递推,这样可以减少递归调用的开销。 请看图 1,可以发现,A 只和 Bi 相邻,Bi 只和 Ci 相邻,...,依此类推。这 样,我们可以将原问题的解决过 程划分为 4 个阶段,设 S1={A},S2={B1,B2},S3={C1,C2,C3,C4},S4={D1,D2,D3},Fk(u)表示从 Sk 中的 点u到 E 的最短距离,则 并且有边界条件 显然可以递推地求出 F1(A),也就是从 A 到 E 的最短距离。这种算法的复杂度 为 O(n),因为所有的状态总数

(节点总数)为 n,对每个状态都只要遍历一次,而且程序很简洁。 具体算法如下: procedure DynamicProgramming; begin F5[E]:=0; for i:=4 downto 1 do for each u ∈Sk do begin Fk:=无穷大; for each v∈Sk+1∩δ (u) do if Fk>w(u,v)+Fk+1[v] then Fk:=w(u,v)+Fk+1[v]; end; 输出 F1[A]; end 【例题 2】生产计划问题 工厂生产某种产品,每单位(千件)的成本为 1(千元),每次开工的固定成本为 3(千元),工厂每季度的最 大生产能力为 6(千件)。经调查,市场对该产品的需求量第一、二、三、四季 度分别为 2,3,2,4(千件 )。如果工厂在第一、二季度将全年的需求都生产出来,自然可以降低成本(少 付固定成本费),但是对于 第三、四季度才能上市的产品需付存储费,每季每千件的存储费为 0.5(千 元)。还规定年初和年末这种产 品均无库存。试制订一个生产计划,即安排每个季度的产量,使一年的总费用 (生产成本和存储费)最少 。 这是一个明显的多阶段问题,我们按照计划时间自然划分阶段,状态定义为每 阶段开始时的存储量 xk, 决策为每个阶段的产量 uk,记每个阶段的需求量(已知)为 dk,则状态转移方 程为: 设每个阶段开工固定成本费用为 a,生产单位数量产品的成本为 b,每阶段单位 数量产品的存储费用为c

,阶段指标为阶段的生产成本费用和存储费用之和,即: 指标函数 Vkn 为 vk 之和,最优值函数 fk(xk)为从第 k 阶段的状态 xk 出发到过 程终结的最小费用,满足 其中允许决策集合 Uk 由每阶段的最大生产能力决定,设过程终结时允许存储量 为 x0n+1,则终端条件为: 【例题 3】Bitonic 旅行路线问题 欧几里德货郎担问题是对平面给定的 n 个点确定一条连结各点的、闭合的游历 路线问题。图 1(a)给出了七 个点问题的解。Bitonic 旅行路线问题是欧几里德货郎担问题的简化,这种旅 行路线先从最左边开始,严 格地由左至右到最右边的点,然后再严格地由右至左到出发点,求路程最短的 路径长度。图 1(b)给出 了七个点问题的解。 图1 请设计一种多项式时间的算法,解决 Bitonic 旅行路线问题。 首先将 n 个点按 X 坐标递增的顺序排列成一个序列 L=<点 1,点 2,…,点 n>。 显然 L[n]为最右点,L[1]为最 左点。由于点 1 往返经过二次(出发一次,返回一次),因此点 1 拆成两个点: L[0]=L[1]=点 1。 设: " Wi,j -- 边<i,j>的距离; " Wi..j -- j-i 条连续边<i,i+l>,<i+l,i+2>,…,<j-2,j-1>,<j-1,j>的距离 和。由点 i 至点 j 的连续边组 成的路径称为连续路径; " d --从点 i 出发由左至右直到 n 点后再由右至左到达点 i-1 的最短距离。d 的递归式如下: 我们专门设置了一张记忆表 k(1≤i≤n),记下使得 d 最小的 J 值。显然递归式 的边界 d[n]=Wn,n-1 ,k[n]

=n 。 由 d 的递归式和记忆表 k 的定义可以看出,在由点 i-1 至点 i 的最短路上,点 i 至 k 的子路径上的点序号是遂 一递增的,为由左至右方向上的连续子路径。按照递归定义,若 k≠N 且 k[k+1]≠N,则点 k[k+1]+1 至点 k[k[k+1]+1]也是由左至右方向上的连续子路径;否则 k[k+1]至 k+1 为由右至 左方向上的连续子路径,该 子路径上的点序号是遂一递减的。 显然要使 d 最小,必须分别使 d[i+1]…d[n-1],d[n]最小,d 包含了 d[i+1]…d[n]最小的子问题,因此该问 题具有最优子结构和重叠子问题性质,满足动态规划法适用的条件。为了提高 算法效率,我们从 d[n]出 发,运用动态规划方法依次求 d[n-1],d[n-2],…,d[1],充分利用重叠子问 题。最后求得的 d[1]便是最短 游历路线的距离;从点 1 出发,顺着记忆表 k 的指示可以递归递输出这条游历 路线。 【例题 4】皇宫看守 SGOI2001 第二次竞赛试题第 4 题,中国教育曙光网举办 问题描述 太平王世子事件后,陆小凤成了皇上特聘的御前一品侍卫。 皇宫以午门为起点,直到后宫嫔妃们的寝宫,呈一棵树的形状;某些宫殿间可 以互相望见。大内保卫森 严,三步一岗,五步一哨,每个宫殿都要有人全天候看守,在不同的宫殿安排 看守所需的费用不同。 可是陆小凤手上的经费不足,无论如何也没法在每个宫殿都安置留守侍卫。 编程任务: 帮助陆小凤布置侍卫,在看守全部宫殿的前提下,使得花费的经费最少。 数据输入: 输入数据由文件名为 INPUT.TXT 的文本文件提供。输入文件中数据表示一棵 树,描述如下: 第 1 行 n,表示树中结点的数目。 第 2 行至第 n+1 行,每行描述每个宫殿结点信息,依次为:该宫殿结点标号 i (0<i<=n),在该宫殿安置侍

卫所需的经费 k,该边的儿子数 m,接下来 m 个数,分别是这个节点的 m 个儿子 的标号 r1,r2,...,rm。 对于一个 n(0 < n <= 1500)个结点的树,结点标号在 1 到 n 之间,且标号不 重复。 数据输出: 输出到 OUTPUT.TXT 文件中。输出文件仅包含一个数,为所求的最少的经费。 如左图的输入数据示例 输出数据示例 在下面我们用根结点的标号来表示一棵树,树 T 就是根结点标号为 T 的树。 " 设 f(T,0)表示对于一棵树 T,不在 T 的树根上布置守卫的情况下,监控 T 的 全部节点所需的最少的费用; " 设 f(T,1)表示对于一棵树 T,不在 T 的树根上布置守卫的情况下,监控除了 T 的根结点以外的其他全部节 点所需的最少的费用,当然也可以监控住 T 的根结点,不过不是强行要求的; " 设 f(T,2)表示对于一棵树 T,在 T 的树根上布置守卫的情况下,监控 T 的全 部节点所需的最少的费用; 假设 T 的儿子节点为 T1,T2,…,Tn;则我们可以得到递归公式: (1) (2) (3) 下面说明上面的三个公式的含义。 如果 T 的根不布置守卫,并且要求监控 T 的所有结点,则必须保证 T 的子结点 中有一个结点 Tk 的根上布置了 一个守卫,这样在 Tk 的根上的守卫可以同时看守 T 的根。至于 T 的其他子结点 (i=1,2,..n,i≠k),可以在 树根上布置守卫,也可以不布置,但是必须监控住自己所有的结点(因为 T 的 根上没有守卫),因此选择 最优的方案 min{f(Ti,0),f(Ti,2)}。这样就得到了(1)式; 如果 T 的根不布置守卫,并且要求监控除了 T 的根结点以外的其他全部节点, 则必须保证 T 的所有的子结点 Ti 都被监控,而不用管 Ti 的根上是否有守卫。于是每个子节点 Ti 取最优的方 案 min{f(Ti,0),f(Ti,2)}。 这样就得到了(2)式;请注意,有可能 f(T,0)=f(T,1),因为 f(T,1)只是要求 监控除了 T 的根结点以外的

其他全部节点,也就是可以选择不监控 T 的根,而不是不允许监控 T 的根。当 存在一个 1<=k<=n,f(Tk,0) >=f(Tk,2)的时候,(2)和(1)等价,这时候 f(T,1)=f(T,0); 如果规定 T 的根布置了守卫,则 T 的所有的子结点上可以布置也可以不布置守 卫,而且 T 的所有的子结点 Ti 的根原来可以被监控也可以不被监控,这是因为如果原来 Ti 的根没有被监控, 则可以被 T 的根上布置的那 个守卫监控。因此 Ti 选择最优的方案 min{f(Ti,0),f(Ti,1),f(Ti,2)}。这样 就得到了(3)式, 这里 ω (T)表示在根结点 T 上布置守卫的代价。实际上,在(3)中的 min 只要对 f(Ti,1)和 f(Ti,2)取 min 就可以了 ,因为根据(2)可以知道 f(Ti,1)<=f(Ti,0)。 如果 T 是整棵树的树根的话,只要求出 f(T,0),f(T,2)取较小者就是结果。 对于 T 没有儿子的情况(结点 T 为叶子),我们给出上面递归公式的边界条 件: (4) (5) (6) 注意,这里我们做了一点特殊规定,因为根据前面对 f(T,0) f(T,1) f(T,2)的 定义可以知道,在 T 是叶子 的情况下不在 T 的树根上布置守卫的情况下而要监控 T 的全部节点使不可能 的,f(T,0)实际上是不存在的 ,但是为了使上面的公式(1)-(3)能够适用于边界条件,我们规定了(4) 式对于 T 是叶子的情况成立 。这并不影响公式(1)-(3)的正确性。(5)说明在 T 是叶子的情况下,不 在 T 的树根上布置守卫的情 况下并监控除了 T 的根结点以外的其他全部节点,最节约的办法是不布置任何 的守卫,这样代价最少为 0 ;(6)说明在 T 是叶子的情况下,在 T 的树根上布置守卫的情况下并监控 T 的 全部节点的办法就是在节点 T

上布置一个守卫,代价为。 下面说说如何编程实现对于这个算法。对于这个问题,虽然可以自底向上的计 算,但是不如自顶向下的 计算方便。我们采用备忘录法,用一个 n*3 的数组记录所有的 f 函数。因为 n<=1500;n*3 不过才 4500,显然 不会有内存不足的问题。之所以采用自顶向下的备忘录方法,是因为输入的数 据是一棵树,从树的根找 到树的子结点肯定比从子节点找到父结点方便。不过也可以自底向上,这时可 以用一个数组 parent 存储 所有的节点的父结点(也就是树的父结点树组描述法),parent 就是结点 i 的 父结点。这样每次要扫描一 遍整个数组,太麻烦了一点。所以我们干脆选择最自然的自顶向下的计算方 式。 源程序 guard.c 在 Turbo C 2.0 下面调试通过,并且通过了所有的测试数据


赞助商链接
相关文章:
动态规划习题
§7.1 动态规划的基本理论 1.1 多阶段决策过程的数学描述 有这样一类活动过程, 其整个过程可分为若干相互联系的阶段, 每一阶段都要作出相应 的决策,以使整个...
动态规划
年和 1964 年出版了两部关于动态 规划的著作,并于 1964 年同尼母霍思尔(Nemhauser) 、威尔德(Wild)一道创建了处理分 枝、 循环性多阶段决策系统的一般性理论...
动态规划的基本思想
动态规划的基本思想前文主要介绍了动态规划的一些理论依据, 我们将前文所说的具有明显 的阶段划分和状态转移方程的动态规划称为标准动态规划, 这种标准动 态规划是...
城市规划:从终极蓝图到动态规划 ——动态规划实践与理论
城市规划:从终极蓝图到动态规划主持人:王富海孙施文——动态规划实践与理论 URBAN PLANNING FROM ULTIMATE BLUEPRINT TO DYNAMIC PLANNING—— PRACTICE AND THEORY OF...
动态规划算法原理及应用
动态规划算法原理及应用_信息与通信_工程科技_专业资料。算法分析设计的优秀样榜 动态规划算法刘兴田(浙江工业大学 计算机学院 软件工程 1205 班 201226630512)摘要: ...
动态规划原理
动态规划的原理 1. 1.动态规划的基本理论 .. 一.动态规划的术语在研究现实的...动态规划加速原理之四边... 6页 免费 动态规划理论(精华) 26页 免费 Bellman...
动态规划加速原理
动态规划加速原理_数学_自然科学_专业资料。动态规划加速原理赵明阳 【摘要】 本...动态规划(理论部分) 54页 免费 动态规划理论(精华) 26页 免费 Bellman最优...
动态规划算法原理与应用
动态规划算法原理 及其应用研究 系姓 别: x 名: x x x x x x x 指导教员: x 2012 年 5 月 20 日 摘要: 动态规划是解决最优化问题的基本方法,本文...
动态规划法学习报告
动态规划法学习报告 - 现代控制理论学习报告 动态规划法 1、概述: 动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程最优化的数学 方法。20 世纪 ...
动态规划原理
动态规划原理_理学_高等教育_教育专区。动态规划原理例题动态规划基本原理近年来,涉及 的各种竞赛题越来越多, 近年来,涉及动态规划的各种竞赛题越来越多,每一年的 ...
更多相关标签: