张辰大牛的动规论文

《张辰大牛的动规论文》由会员分享，可在线阅读，更多相关《张辰大牛的动规论文（14页珍藏版）》请在金锄头文库上搜索。

1、张辰大牛的动规论文张辰大牛的动规论文张辰大牛的动规论文.txt12 思念是一首诗，让你在普通的日子里读出韵律来；思念是一阵雨，让你在枯燥的日子里湿润起来；思念是一片阳光，让你的阴郁的日子里明朗起来。最佳答案:动态规划的特点及其应用 安徽 张辰 【关键词】动态规划 阶段 【摘要】 动态规划是信息学竞赛中的常见算法，本文的主要内容就是分析它的特点。 文章的第一部分首先探究了动态规划的本质，因为动态规划的特点是由它的本质所决定的。第二部分从动态规划的设计和实现这两个角度分析了动态规划的多样性、模式性、技巧性这三个特点。第三部分将动态规划和递推、搜索、网络流这三个相关算法作了比较，从中探寻动态规划的一

2、些更深层次的特点。 文章在分析动态规划的特点的同时，还根据这些特点分析了我们在解题中应该怎样利用这些特点，怎样运用动态规划。这对我们的解题实践有一定的指导意义。 【正文】 动态规划是编程解题的一种重要的手段，在如今的信息学竞赛中被应用得越来越普遍。最近几年的信息学竞赛，不分大小，几乎每次都要考察到这方面的内容。因此，如何更深入地了解动态规划，从而更为有效地运用这个解题的有力武器，是一个值得深入研究的问题。 要掌握动态规划的应用技巧，就要了解它的各方面的特点。首要的，是要深入洞悉动态规划的本质。 1 动态规划的本质 动态规划是在本世纪 50 年代初，为了解决一类多阶段决策问题而诞生的。那么，什么

3、样的问题被称作多阶段决策问题呢？ 1.1 多阶段决策问题 说到多阶段决策问题，人们很容易举出下面这个例子。 例 1 多段图中的最短路径问题：在下图中找出从 A1 到 D1 的最短路径。 仔细观察这个图不难发现，它有一个特点。我们将图中的点分为四类（图中的 A、B、C、D） ，那么图中所有的边都处于相邻的两类点之间，并且都从前一类点指向后一类点。这样，图中的边就被分成了三类（AB、BC、CD） 。我们需要从每一类中选出一条边来，组成从 A1 到 D1 的一条路径，并且这条路径是所有这样的路径中的最短者。 从上面的这个例子中，我们可以大概地了解到什么是多阶段决策问题。更精确的定义如下： 多阶段决策

4、过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列1。要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。 从上述的定义中，我们可以明显地看出，这类问题有两个要素。一个是阶段，一个是决策。 1.2 阶段与状态 阶段：将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便按次序去求每阶段的解。常用字母 k 表示阶段变量。1 阶段是问题的属性。多阶段决策问题中通常存在着若干个阶段，如上面的例子，就有 A、B、C、D 这四个阶段。在一般情况下，阶段是和时间有关的；但是在很多问题（我的感觉，特别是信息学

5、问题）中，阶段和时间是无关的。从阶段的定义中，可以看出阶段的两个特点，一是“相互联系” ，二是“次序” 。 阶段之间是怎样相互联系的？就是通过状态和状态转移。 状态：各阶段开始时的客观条件叫做状态。描述各阶段状态的变量称为状态变量，常用 sk 表示第 k 阶段的状态变量，状态变量 sk 的取值集合称为状态集合，用 Sk 表示。1 状态是阶段的属性。每个阶段通常包含若干个状态，用以描述问题发展到这个阶段时所处在的一种客观情况。在上面的例子中，行人从出发点 A1 走过两个阶段之后，可能出现的情况有三种，即处于C1、C2 或 C3 点。那么第三个阶段就有三个状态 S3=C1,C2,C3。 每个阶段的

6、状态都是由以前阶段的状态以某种方式“变化”而来，这种“变化”称为状态转移（暂不定义） 。上例中 C3 点可以从 B1 点过来，也可以从 B2 点过来，从阶段 2 的 B1 或 B2 状态走到阶段 3的 C3 状态就是状态转移。状态转移是导出状态的途径，也是联系各阶段的途径。 说到这里，可以提出应用动态规划的一个重要条件。那就是将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的发展，而只能通过当前的这个状态。换句话说，每个状态都是“过去历史的一个完整总结1” 。这就是无后效性。对这个性质，下文还将会有解释。 1.3 决策和策略 上面的阶段与状态只是多

7、阶段决策问题的一个方面的要素，下面是另一个方面的要素决策。 决策：当各段的状态取定以后，就可以做出不同的决定，从而确定下一阶段的状态，这种决定称为决策。表示决策的变量，称为决策变量，常用 uk(sk)表示第 k 阶段当状态为 sk 时的决策变量。在实际问题中，决策变量的取值往往限制在一定范围内，我们称此范围为允许决策集合。常用 Dk(sk)表示第 k 阶段从状态 sk 出发的允许决策集合。显然有 uk(sk) ?Dk(sk)。1 决策是问题的解的属性。决策的目的就是“确定下一阶段的状态” ，还是回到上例，从阶段 2 的 B1 状态出发有三条路，也就是三个决策，分别导向阶段 3 的 C1、C2、

8、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,

9、n，使整个问题达到最有效果的策略就是最优策略。1 说到这里，又可以提出运用动态规划的一个前提。即这个过程的最优策略应具有这样的性质：无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略1。这就是最优化原理。简言之，就是“最优策略的子策略也是最优策略” 。 1.4 最优化原理与无后效性 这里，我把最优化原理定位在“运用动态规划的前提” 。这是因为，是否符合最优化原理是一个问题的本质特征。对于不满足最优化原理的一个多阶段决策问题，整体上的最优策略 p1,n 同任何一个阶段k 上的决策 uk 或任何一组阶段 k1k2 上的子策略 pk1,k2 都不存在任何关系。如

10、果要对这样的问题动态规划的话，我们从一开始所作的划分阶段等努力都将是徒劳的。 而我把无后效性定位在“应用动态规划的条件” ，是因为动态规划是按次序去求每阶段的解，如果一个问题有后效性，那么这样的次序便是不合理的。但是，我们可以通过重新划分阶段，重新选定状态，或者增加状态变量的个数等手段，来是问题满足无后效性这个条件。说到底，还是要确定一个“序” 。 在信息学的多阶段决策问题中，绝大部分都是能够满足最优化原理的，但它们往往会在后效性这一点上来设置障碍。所以在解题过程中，我们会特别关心“序” 。对于有序的问题，就会考虑到动态规划；对于无序的问题，也会想方设法来使其有序。 1.5 最优指标函数和规划

11、方程 最优指标函数：用于衡量所选定策略优劣的数量指标称为指标函数，最优指标函数记为 fk(sk)，它表示从第 k 段状态 sk 采用最优策略p*k,n 到过程终止时的最佳效益值1。 最优指标函数其实就是我们真正关心的问题的解。在上面的例子中，f2(B1)就表示从 B1 点到终点 D1 点的最短路径长度。我们求解的最终目标就是 f1(A1)。 最优指标函数的求法一般是一个从目标状态出发的递推公式，称为规划方程： 其中 sk 是第 k 段的某个状态，uk 是从 sk 出发的允许决策集合Dk(sk)中的一个决策，Tk(sk,uk)是由 sk 和 uk 所导出的第 k 1 段的某个状态 sk 1，g(

12、x,uk)是定义在数值 x 和决策 uk 上的一个函数，而函数 opt 表示最优化，根据具体问题分别表为 max 或 min。 ，称为边界条件。 上例中的规划方程就是： 边界条件为 这里是一种从目标状态往回推的逆序求法，适用于目标状态确定的问题。在我们的信息学问题中，也有很多有着确定的初始状态。当然，对于初始状态确定的问题，我们也可以采用从初始状态出发往前推的顺序求法。事实上，这种方法对我们来说要更为直观、更易设计一些，从而更多地出现在我们的解题过程中。 我们本节所讨论的这些理论虽然不是本文的主旨，但是却对下面要说的动态规划的特点起着基础性的作用。 2 动态规划的设计与实现 上面我们讨论了动态

13、规划的一些理论，本节我们将通过几个例子中，动态规划的设计与实现，来了解动态规划的一些特点。 2.1 动态规划的多样性 例 2 花店橱窗布置问题（IOI99）试题见附录 本题虽然是本届 IOI 中较为简单的一题，但其中大有文章可作。说它简单，是因为它有序，因此我们一眼便可看出这题应该用动态规划来解决。但是，如何动态规划呢？如何划分阶段，又如何选择状态呢？ 以花束的数目来划分阶段。在这里，阶段变量 k 表示的就是要布置的花束数目（前 k 束花） ，状态变量 sk 表示第 k 束花所在的花瓶。而对于每一个状态 sk，决策就是第 k-1 束花应该放在哪个花瓶，用 uk 表示。最优指标函数 fk(sk)

14、表示前 k 束花，其中第 k束插在第 sk 个花瓶中，所能取得的最大美学值。 状态转移方程为 规划方程为 （其中 A(i,j)是花束 i 插在花瓶 j 中的美学值） 边界条件 （V 是花瓶总数，事实上这是一个虚拟的边界） 以花瓶的数目来划分阶段。在这里阶段变量 k 表示的是要占用的花瓶数目（前 k 个花瓶） ，状态变量 sk 表示前 k 个花瓶中放了多少花。而对于任意一个状态 sk，决策就是第 sk 束花是否放在第 k 个花瓶中，用变量 uk=1 或 0 来表示。最优指标函数 fk(sk)表示前 k 个花瓶中插了 sk 束花，所能取得的最大美学值。 状态转移方程为 规划方程为 边界条件为 两种

15、划分阶段的方法，引出了两种状态表示法，两种规划方式，但是却都成功地解决了问题。只不过因为决策的选择有多有少，所以算法的时间复杂度也就不同。2 这个例子具有很大的普遍性。有很多的多阶段决策问题都有着不止一种的阶段划分方法，因而往往就有不止一种的规划方法。有时各种方法所产生的效果是差不多的，但更多的时候，就像我们的例子一样，两种方法会在某个方面有些区别。 所以，在用动态规划解题的时候，可以多想一想是否有其它的解法。对于不同的解法，要注意比较，好的算法好在哪里，差一点的算法差在哪里。从各种不同算法的比较中，我们可以更深刻地领会动态规划的构思技巧。 2.2 动态规划的模式性 这个可能做过动态规划的人都

16、有体会，从我们上面对动态规划的分析也可以看出来。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。 划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的，否则问题就无法求解。 选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。 确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。 写出规划方程（包括边界条件）：在第一部分中，我们已经给出了规划方程的通用形式化表达式。一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。 动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。大体上的框架如下： 对 f1(s1)初始化（边界条件） for k?2