logo资料库

算法设计与分析论文（动态规划的特点及其应用）.doc

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：0.16M 资料格式：doc 举报 版权申诉
第1页 / 共12页
第2页 / 共12页
第3页 / 共12页
第4页 / 共12页
第5页 / 共12页
第6页 / 共12页
第7页 / 共12页
第8页 / 共12页
资料共12页，剩余部分请下载后查看
    【摘要】
    动态规划是信息学竞赛中的常见算法，本文的主要内容就是分析它的特点。
    文章的第一部分首先探究了动态规划的本质，因为动态规划的特点是由它的本质所决定的。第二部分从动态规划的
    文章在分析动态规划的特点的同时，还根据这些特点分析了我们在解题中应该怎样利用这些特点，怎样运用动态规
    【正文】
    【参考文献】
    动态规划的特点及其应用 【题目】 动态规划的特点及其应用 【摘要】 动态规划是信息学竞赛中的常见算法，本文的主要内容就是分析它的特点。 文章的第一部分首先探究了动态规划的本质，因为动态规划的特点是由它的本质所决 定的。第二部分从动态规划的设计和实现这两个角度分析了动态规划的多样性、模式性、技 巧性这三个特点。第三部分将动态规划和递推、搜索、网络流这三个相关算法作了比较，从 中探寻动态规划的一些更深层次的特点。 文章在分析动态规划的特点的同时，还根据这些特点分析了我们在解题中应该怎样利 用这些特点，怎样运用动态规划。这对我们的解题实践有一定的指导意义。 【正文】 动态规划是编程解题的一种重要的手段，在如今的信息学竞赛中被应用得越来越普遍。 最近几年的信息学竞赛，不分大小，几乎每次都要考察到这方面的内容。因此，如何更深入 地了解动态规划，从而更为有效地运用这个解题的有力武器，是一个值得深入研究的问题。 要掌握动态规划的应用技巧，就要了解它的各方面的特点。首要的，是要深入洞悉动态 规划的本质。 §1 动态规划的本质 动态规划是在本世纪 50 年代初，为了解决一类多阶段决策问题而诞生的。那么，什么 样的问题被称作多阶段决策问题呢？ §1.1 多阶段决策问题 说到多阶段决策问题，人们很容易举出下面这个例子。 多段图中的最短路径问题：在下图中找出从 A1 到 D1 的最短路径。 3 5 A1 7 8 B1 6 4 B2 5 C1 4 C2 7 6 C3 D1 仔细观察这个图不难发现，它有一个特点。我们将图中的点分为四类（图中的 A、B、 C、D），那么图中所有的边都处于相邻的两类点之间，并且都从前一类点指向后一类点。这 样，图中的边就被分成了三类（AB、BC、CD）。我们需要从每一类中选出一条边来， 6
    组成从 A1 到 D1 的一条路径，并且这条路径是所有这样的路径中的最短者。 从上面的这个例子中，我们可以大概地了解到什么是多阶段决策问题。更精确的定义如 下： 多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相 互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列[1]。要使整 个活动的总体效果达到最优的问题，称为多阶段决策问题。 从上述的定义中，我们可以明显地看出，这类问题有两个要素。一个是阶段，一个是决 策。 §1.2 阶段与状态 阶段：将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便按次序 去求每阶段的解。常用字母 k 表示阶段变量。[1] 阶段是问题的属性。多阶段决策问题中通常存在着若干个阶段，如上面的例子，就有 A、 B、C、D 这四个阶段。在一般情况下，阶段是和时间有关的；但是在很多问题（我的感觉， 特别是信息学问题）中，阶段和时间是无关的。从阶段的定义中，可以看出阶段的两个特点， 一是“相互联系”，二是“次序”。 阶段之间是怎样相互联系的？就是通过状态和状态转移。 状态：各阶段开始时的客观条件叫做状态。描述各阶段状态的变量称为状态变量，常用 sk 表示第 k 阶段的状态变量，状态变量 sk 的取值集合称为状态集合，用 Sk 表示。[1] 状态是阶段的属性。每个阶段通常包含若干个状态，用以描述问题发展到这个阶段时所 处在的一种客观情况。在上面的例子中，行人从出发点 A1 走过两个阶段之后，可能出现的 情况有三种，即处于 C1、C2 或 C3 点。那么第三个阶段就有三个状态 S3={C1,C2,C3}。 每个阶段的状态都是由以前阶段的状态以某种方式“变化”而来，这种“变化”称为状 态转移（暂不定义）。上例中 C3 点可以从 B1 点过来，也可以从 B2 点过来，从阶段 2 的 B1 或 B2 状态走到阶段 3 的 C3 状态就是状态转移。状态转移是导出状态的途径，也是联系各 阶段的途径。 说到这里，可以提出应用动态规划的一个重要条件。那就是将各阶段按照一定的次序排 列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的发展，而 只能通过当前的这个状态。换句话说，每个状态都是“过去历史的一个完整总结[1]”。这就 是无后效性。对这个性质，下文还将会有解释。 §1.3 决策和策略 上面的阶段与状态只是多阶段决策问题的一个方面的要素，下面是另一个方面的要素— —决策。 决策：当各段的状态取定以后，就可以做出不同的决定，从而确定下一阶段的状态，这 种决定称为决策。表示决策的变量，称为决策变量，常用 uk(sk)表示第 k 阶段当状态为 sk 时的决策变量。在实际问题中，决策变量的取值往往限制在一定范围内，我们称此范围为允 许决策集合。常用 Dk(sk)表示第 k 阶段从状态 sk 出发的允许决策集合。显然有 uk(sk) Dk(sk)。[1]
    决策是问题的解的属性。决策的目的就是“确定下一阶段的状态”，还是回到上例，从 阶段 2 的 B1 状态出发有三条路，也就是三个决策，分别导向阶段 3 的 C1、C2、C3 三个状 态，即 D2(B1)={C1,C2,C3}。 有了决策，我们可以定义状态转移：动态规划中本阶段的状态往往是上一阶段和上一阶 段的决策结果，由第 k 段的状态 sk 和本阶段的决策 uk 确定第 k+1 段的状态 sk+1 的过程叫 状态转移。状态转移规律的形式化表示 sk+1=Tk(sk,uk)称为状态转移方程。 这样看来，似乎决策和状态转移有着某种联系。我的理解，状态转移是决策的目的，决 策是状态转移的途径。 各段决策确定后，整个问题的决策序列就构成一个策略，用 p1,n={u1(s1),u2(s2),…, un(sn)}表示。对每个实际问题，可供选择的策略有一定范围，称为允许策略集合，记作 P1,n， 使整个问题达到最有效果的策略就是最优策略。[1] 说到这里，又可以提出运用动态规划的一个前提。即这个过程的最优策略应具有这样的 性质：无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策 应构成最优策略[1]。这就是最优化原理。简言之，就是“最优策略的子策略也是最优策略”。 §1.4 最优化原理与无后效性 这里，我把最优化原理定位在“运用动态规划的前提”。这是因为，是否符合最优化原 理是一个问题的本质特征。对于不满足最优化原理的一个多阶段决策问题，整体上的最优策 略 p1,n 同任何一个阶段 k 上的决策 uk 或任何一组阶段 k1…k2 上的子策略 pk1,k2 都不存在 任何关系。如果要对这样的问题动态规划的话，我们从一开始所作的划分阶段等努力都将是 徒劳的。 而我把无后效性定位在“应用动态规划的条件”，是因为动态规划是按次序去求每阶段 的解，如果一个问题有后效性，那么这样的次序便是不合理的。但是，我们可以通过重新划 分阶段，重新选定状态，或者增加状态变量的个数等手段，来是问题满足无后效性这个条件。 说到底，还是要确定一个“序”。 在信息学的多阶段决策问题中，绝大部分都是能够满足最优化原理的，但它们往往会在 后效性这一点上来设置障碍。所以在解题过程中，我们会特别关心“序”。对于有序的问题， 就会考虑到动态规划；对于无序的问题，也会想方设法来使其有序。 §1.5 最优指标函数和规划方程 最优指标函数：用于衡量所选定策略优劣的数量指标称为指标函数，最优指标函数记为 fk(sk)，它表示从第 k 段状态 sk 采用最优策略 p*k,n 到过程终止时的最佳效益值[1]。 最优指标函数其实就是我们真正关心的问题的解。在上面的例子中，f2(B1)就表示从 B1 点到终点 D1 点的最短路径长度。我们求解的最终目标就是 f1(A1)。 最优指标函数的求法一般是一个从目标状态出发的递推公式，称为规划方程： f k ( s k )  opt ( sDu  k k ) k  fg k 1   , usT k ( k  ,) u k k 其中 sk 是第 k 段的某个状态，uk 是从 sk 出发的允许决策集合 Dk(sk)中的一个决策， Tk(sk,uk)是由 sk 和 uk 所导出的第 k+1 段的某个状态 sk+1，g(x,uk)是定义在数值 x 和决策
    uk 上的一个函数，而函数 opt 表示最优化，根据具体问题分别表为 max 或 min。 f ( n n s ) 某个初始值 ，称为边界条件。 上例中的规划方程就是： f k ( s k )  从 s min 出发的某条边 k u k  f ( u k k 1  指向的点 s k 1  )  边 u k 的长度  边界条件为 Df 4 ( 1 ) 0 这里是一种从目标状态往回推的逆序求法，适用于目标状态确定的问题。在我们的信息 学问题中，也有很多有着确定的初始状态。当然，对于初始状态确定的问题，我们也可以采 用从初始状态出发往前推的顺序求法。事实上，这种方法对我们来说要更为直观、更易设计 一些，从而更多地出现在我们的解题过程中。 我们本节所讨论的这些理论虽然不是本文的主旨，但是却对下面要说的动态规划的特点 起着基础性的作用。 §2 动态规划的设计与实现 上面我们讨论了动态规划的一些理论，本节我们将通过几个例子中，动态规划的设计与 实现，来了解动态规划的一些特点。 §2.1 动态规划的多样性 花店橱窗布置问题（IOI99）试题见附录 本题虽然是本届 IOI 中较为简单的一题，但其中大有文章可作。说它简单，是因为它有 序，因此我们一眼便可看出这题应该用动态规划来解决。但是，如何动态规划呢？如何划分 阶段，又如何选择状态呢？ <方法 1>以花束的数目来划分阶段。在这里，阶段变量 k 表示的就是要布置的花束数目 （前 k 束花），状态变量 sk 表示第 k 束花所在的花瓶。而对于每一个状态 sk，决策就是第 k-1 束花应该放在哪个花瓶，用 uk 表示。最优指标函数 fk(sk)表示前 k 束花，其中第 k 束插 在第 sk 个花瓶中，所能取得的最大美学值。 状态转移方程为 s 1 k u k f k ( s k )   f max uk s  k k ( u k k 1  )  ,( skA ) k 规划方程为 （其中 A(i,j)是花束 i 插在花瓶 j 中的美学值） 边界条件 f 0 ( s 0 )  0(0  s 0  V ) （V 是花瓶总数，事实上这是一个虚拟的边界） <方法 2>以花瓶的数目来划分阶段。在这里阶段变量 k 表示的是要占用的花瓶数目（前 k 个花瓶），状态变量 sk 表示前 k 个花瓶中放了多少花。而对于任意一个状态 sk，决策就是 第 sk 束花是否放在第 k 个花瓶中，用变量 uk=1 或 0 来表示。最优指标函数 fk(sk)表示前 k
    个花瓶中插了 sk 束花，所能取得的最大美学值。 状态转移方程为 s 1 k s k  u k f k ( s k )   max 1,0 u  f ( s k  u k )  u k  ( sA k k 1  ), k 规划方程为 边界条件为 fk )0(  0(0  Vk ) 两种划分阶段的方法，引出了两种状态表示法，两种规划方式，但是却都成功地解决了 问题。只不过因为决策的选择有多有少，所以算法的时间复杂度也就不同。[2] 这个例子具有很大的普遍性。有很多的多阶段决策问题都有着不止一种的阶段划分方 法，因而往往就有不止一种的规划方法。有时各种方法所产生的效果是差不多的，但更多的 时候，就像我们的例子一样，两种方法会在某个方面有些区别。 所以，在用动态规划解题的时候，可以多想一想是否有其它的解法。对于不同的解法， 要注意比较，好的算法好在哪里，差一点的算法差在哪里。从各种不同算法的比较中，我们 可以更深刻地领会动态规划的构思技巧。 §2.2 动态规划的模式性 这个可能做过动态规划的人都有体会，从我们上面对动态规划的分析也可以看出来。动 态规划的设计都有着一定的模式，一般要经历以下几个步骤。 划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一 定要是有序的或者是可排序的，否则问题就无法求解。 选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当 然，状态的选择要满足无后效性。 确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有着 天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我 们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两 段的各状态之间的关系来确定决策。 写出规划方程（包括边界条件）：在第一部分中，我们已经给出了规划方程的通用形式 化表达式。一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。 动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。大体 上的框架如下： 对 f1(s1)初始化（边界条件） for k2 to n（这里以顺序求解为例） 对每一个 skSk fk(sk)一个极值（∞或－∞） 对每一个 uk(sk)Dk(sk) sk-1Tk(sk,uk)
    tg(fk-1(sk-1),uk) t 比 fk(sk) n y 更优 fk(sk)t 输出 fn(sn) 这个 N-S 图虽然不能代表全部，但足可以概括大多数。少数的一些特殊的动态规划， 其实现的原理也是类似，可以类比出来。我们到现在对动态规划的分析，主要是在理论上、 设计上，原因也就在此。 掌握了动态规划的模式性，我们在用动态规划解题时就可以把主要的精力放在理论上的 设计。一旦设计成熟，问题也就基本上解决了。而且在设计算法时也可以按部就班地来。 但是“物极必反”，太过拘泥于模式就会限制我们的思维，扼杀优良算法思想的产生。 我们在解题时，不妨发挥一下创造性，去突破动态规划的实现模式，这样往往会收到意想不 到的效果。[3] §2.3 动态规划的技巧性 上面我们所说的动态规划的模式性，主要指的是实现方面。而在设计方面，虽然它较为 严格的步骤性，但是它的设计思想却是没有一定的规律可循的。这就需要我们不断地在实践 当中去掌握动态规划的技巧，下面仅就一个例子谈一点我自己的体会。 街道问题：在下图中找出从左下角到右上角的最短路径，每步只能向右方或上方走。 7 2 8 3 4 3 5 6 8 7 7 6 6 4 3 5 4 4 3 3 6 5 9 3 8 5 5 2 3 4 7 这是一道简单而又典型的动态规划题，许多介绍动态规划的书与文章中都拿它来做例 子。通常，书上的解答是这样的： D1 C1 B1 A1 E1 D2 C2 B2 F1 G1 H1 E2 D3 C3 F2 E3 G2 F3 D4 E4 按照图中的虚线来划分阶段，即阶段变量 k 表示走过的步数，而状态变量 sk 表示当前
    处于这一阶段上的哪一点（各点所对应的阶段和状态已经用 ks 在地图上标明）。这时的模型 实际上已经转化成了一个特殊的多段图。用决策变量 uk=0 表示向右走，uk=1 表示向上走， 则状态转移方程如下： s  1 k u k    s k s k 1  u  k ( ( k k   row row ) ) （这里的 row 是地图竖直方向的行数） 我们看到，这个状态转移方程需要根据 k 的取值分两种情况讨论，显得非常麻烦。相应 的，把它代入规划方程而付诸实现时，算法也很繁。因而我们在实现时，一般是不会这么做 的，而代之以下面方法： D1 C1 B1 D2 D3 D4 D5 C2 B2 C3 B3 C4 B4 C5 B5 A1 A2 A3 A4 A5 将地图中的点规则地编号如上，得到的规划方程如下： f , ji  min f f     i ,1  j , ji 1    Distance Distance ,1( i  j ),(), ji ,( ji ),(),1 ji  （这里 Distance 表示相邻两点间的边长） 这样做确实要比上面的方法简单多了，但是它已经破坏了动态规划的本来面目，而不存 在明确的阶段特征了。如果说这种方法是以地图中的行（A、B、C、D）来划分阶段的话， 那么它的“状态转移”就不全是在两个阶段之间进行的了。 也许这没什么大不了的，因为实践比理论更有说服力。但是，如果我们把题目扩展一下： 在地图中找出从左下角到右上角的两条路径，两条路径中的任何一条边都不能重叠，并且要 求两条路径的总长度最短。这时，再用这种“简单”的方法就不太好办了。 如果非得套用这种方法的话，则最优指标函数就需要有四维的下标，并且难以处理两条 路径“不能重叠”的问题。 而我们回到原先“标准”的动态规划法，就会发现这个问题很好解决，只需要加一维状 态变量就成了。即用 sk=(ak,bk)分别表示两条路径走到阶段 k 时所处的位置，相应的，决策 变量也增加一维，用 uk=(xk,yk)分别表示两条路径的行走方向。状态转移时将两条路径分别 考虑： k  row ) k  row )  (     (   k a   b  k a   b  k k 1  1  1  1      k a b k a b k k x y k k 1  1  x  y  k k
    在写规划方程时，只要对两条路径走到同一个点的情况稍微处理一下，减少可选的决策 个数： f k ( s k )       u  k u k  min )0,1(),1,0( min )1,1(),0,1(),1,0(),0,0(   f k 1  f k 1  k (  , usT k  , usT k ( k k k )     ) 两条边长 两条边长   a k  b k a k  b k 从这个例子中可以总结出设计动态规划算法的一个技巧：状态转移一般是在相邻的两个 阶段之间（有时也可以在不相邻的两个阶段间），但是尽量不要在同一个阶段内进行。 动态规划是一种很灵活的解题方法，在动态规划算法的设计中，类似的技巧还有很多。 要掌握动态规划的技巧，有两条途径：一是要深刻理解动态规划的本质，这也是我们为什么 一开始就探讨它的本质的原因；二是要多实践，不但要多解题，还要学会从解题中探寻规律， 总结技巧。 §3 动态规划与一些算法的比较 动态规划作为诸多解题方法中的一种，必然和其他一些算法有着诸多联系。从这些联系 中，我们也可以看出动态规划的一些特点。 §3.1 动态规划与递推 ——动态规划是最优化算法 由于动态规划的“名气”如此之大，以至于很多人甚至一些资料书上都往往把一种与动 态规划十分相似的算法，当作是动态规划。这种算法就是递推。实际上，这两种算法还是很 容易区分的。 按解题的目标来分，信息学试题主要分四类：判定性问题、构造性问题、计数问题和最 优化问题。我们在竞赛中碰到的大多是最优化问题，而动态规划正是解决最优化问题的有力 武器，因此动态规划在竞赛中的地位日益提高。而递推法在处理判定性问题和计数问题方面 也是一把利器。下面分别就两个例子，谈一下递推法和动态规划在这两个方面的联系。 mod 4 最优路径问题：在下图中找出从第 1 点到第 4 点的一条路径，要求路径长度 mod 4 的余数最小。 1 3 1 0 1 2 2 2 0 2 3 3 4 这个图是一个多段图，而且是一个特殊的多段图。虽然这个图的形式比一般的多段图要 简单，但是这个最优路径问题却不能用动态规划来做。因为一条从第 1 点到第 4 点的最优路 径，在它走到第 2 点、第 3 点时，路径长度 mod 4 的余数不一定是最小，也就是说最优策略 的子策略不一定最优——这个问题不满足最优化原理。 但是我们可以把它转换成判定性问题，用递推法来解决。判断从第 1 点到第 k 点的长度 mod 4 为 sk 的路径是否存在，用 fk(sk)来表示，则递推公式如下：
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料