国际大学生程序设计竞赛试题与算法分析_三_动态规划及.pdf

《国际大学生程序设计竞赛试题与算法分析_三_动态规划及.pdf》由会员分享，可在线阅读，更多相关《国际大学生程序设计竞赛试题与算法分析_三_动态规划及.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信夕息章赛试题与脚法分析三劫态视划友其表用录扳路问题郭篙山陈明睿中山大学信息科技学 院计算机科学系,广州动态规 划 实际上 是 研 究 一 类 最 优 化 问题 的方法,在经 济、工 程 技 术、企 业 管 理、工 农 业生产及 军事等 领 域 中都 有 广 泛的应用。近年 来,在中,使 用动态 规 划或部分 应 用动态规划 思维求解 的题不仅常见,而且形式也多种多样。而在与此相 近的各类信息学竞赛中,应用动态规划解题已经成为一种趋势,这和动态规划 的优势不无关系。与其说动态 规划是一种算法,不如说是一种思维方法来 得贴切。因为动态规划 没有固定 的框架,即便是应用到 同一道题上,也可以建立多

2、种形式的求解算法。许多隐式 图上 的算法,例如求单源最短路径 的算法、广度优先搜索算 法,都渗透着动态规划的思想。还有许多数学问题,表面上看起来与动态规划风马牛不相及,但是其求解思想 与动态规划是完全一致 的。正因为如此,今后我们还将会分几个专题,对动态规划的应用分 门别类地进行介绍。如场少找曰什州检且知饥匕心廿未”山南乃湘用动态规划的概念和基础什么是 动态规 划动 态 规 划 是 运 筹 学的一个分支。年美国数 学 家等人,根据一类多阶段问题 的特点,把 多 阶段 决策 问题变换 为一系列 互 相联 系 的单阶段 问题,然后逐 个 加以解 决。一些静态模型,只要 人 为地 引进“时 间”因素

3、,分 成时段,就 可以转 化 成 多 阶段的动 态模型,用动态规亚 洲上海 赛区中山大学二 队教练一亚 洲上海 赛区中山大学二 队主力队员划方法去处理。与此 同时,他提 出了解决这类问题的“最优化原理”。“一个过程 的最优 决 策具 有 这 样的性质即无论其初始状态和初始决策如何,其今后诸策略对以第一 个决策所形成 的状态作为初始状 态 的过程而言,必须构成最优策 略”。简言之,一个最优策 略的子策 略,对于它 的初态和终态而 言也必是最优 的。这个“最优 化原理”如果 用数学化 一点 的语 言来描述 的话,就是 假设为了解 决某一优化 问题,需要依 次作出个 决策,如若这个决 策序列是 最优

4、 的,对于任何一个 整数,不论前面个决策是怎样的,以后 的最优决策只取决于由前面决策所确定 的当前状 态,即以后 的决策,。也是 最优的。最优化原理是 动态规划 理论的基 础。动态规划实 际上是一种寻找组合最优化 问题的最优解 的方法,它将一个待求的最优化 问题分解成几个子问题,先寻找子 问题 的局部 最优 解,并 用逆推公式把原 问题的最优解 与子问题的局部最优解联系起来,最后 获得所求问题 的最优解。最优 化 原理说起来很简单,如何灵活应 用它则又是另一回事。它用途很广,由于运用最优化原理来解决的问题本身并没有固定不变 的算法,需要不断地探索其规律并进行归纳和 总结。因此,利用它来解决 问

5、题的本身也就是一种创造。我们 下面希望 通 过讲解 动态规划 的 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http:/信息萦赛一个重要 应用一一最 短路问题,来 帮助读 者初 步掌握它的技巧。最短路问题所谓最短路问题是 指给定起点及终点,并知道由起点到终点的各种 可 能 的路径,问题是要 找一条由起点 到终点的最短 的路,即长 度最短 的路。需要指出 的是 最 短路问题中的“长 度”可以是 通 常意 义下的距 离,也 可以是 运输的时 间或 者 运 输 费用等等。而且,有些

6、 与运输根本 没有关系的问题也可以化 为求最 短路的模型,例 如求关键路径实 际上是网中的最 长路问题等。由起点到 终点的路线图如图所 示,连接两地之间的路的长度用连 线上 的数字表示,求由起点到终点的最 短路。我们很 容 易可以得 到 一个递归形 式的算 法来求解最短路问题,求由几到的最短路的长度已求 出润田 日对所 有。四少 小声图一 般 地,求一个具有个结点的 图 的最 短路,如果使用穷举法,其运算量 是的指数函数。当比较大,同时 图 的深度 较深时,这个算法 在 时 间效率上是 不 可取的。如果用最 优化原 理来思考这个问题,我们可以注意 到 最 短路有 这样 一 个 特性,即如果 最

7、 短路的第站 通 过,则 这 一 最 短 路在 由出发到达终点的那一部分路径,对于起点为到终点所有可能的路径来说,必定也是长度最短的。引入几个记号。记妙日表示 由点到的最短路的长度,例如,私表示由到的最 短路的长度,几表示由到的最 短路的长度。表示从 点出发 到 下 一 步 所 选 的点,的集合。田,表示点到下 一步所选 的点的长度,例如,表示 由到的距离,即,二。则最短路这一特性 可 描述为日,【。公显 然 有哪二,而几勾尹是 未知的,我们将此作为初始 的已知条件。根据最 短路这一特性,职小【队,项,。调用,求出 的最 短路 为今今今今,长度 为,如图中粗线所示。我们 实际 上 是将 求解到

8、的 最 短路问题分解成 结构 相同的若干个子 问题,习,胆,这些 子 问题之 间可 能 有 重 叠,在求解 的过 程 中,如果某个需要求解 的子 问题已经解 出来了,就直接取其结果如果还没有解 出来,就递归进行求解,然后通过这些子问题的解来求出原问题的解。其结果,我们不仅得到了原 问题 的解,而且得,到了一连串子问题的解。动态规划之所以 比穷举法高效的原因,就在于它对每个子问题只求解一次。与穷举法相比,动态规划 的方法有 两个明显 的优点大大减少了计算量丰富了计算结果。从上面例子 的求解结果 中,我们得到 的不仅是由起点出发到终点的最短路,而且还得 到 了从所有各 中间点到终点的最短路,这对许

9、多实际问题来讲是很有用的。你也许会想,动态规划是不是分而治之呢其实,虽然 在分析许多 问题时,我们都使用了这 种将大问题分解成小 问题的思路,但是动态规划不是分治法,这一点我们将在以后 的专题中加以分析。另一种表示形式递推上面我们用递归 的形式描 述 了最 短路问题 的求解方法。既然每个子 问题只求解一次,我们是不是可以确定 出一个求解 子问题顺序,用递推的方法来求解 最短路问题呢其实这样 的顺序是很容 易确定的,例如,。事实涛福场少找“什”曹异翎饥匕心蟹矛”从小书伪湘用 1994-2009 China Academic Journal Electronic Publishing House.

10、All rights reserved.http:/上,如果 把 这个 路线图看 成是一 个 有 向带权 图的话,它的任 一个拓 扑序列的逆序都可以作为求解 子问题顺 序 的序列。于是我 们 就 得 到 了一 个求最 短路问题的递推 形 式 的算法令二,公是某个 求解 子 问题顺 序 的序列,而且且已经解 出二红二而,即项乓。我们 现在用手 工来计算一下,你就会对整个递推过程有更加 清 晰 的理解了邢二终 态,已知和于 硕和二耳二兀二项口,硕二,几 项,十红 习,曰耳 红,项月 卜,红而斑,项刁科,二毋汾翎项口,朝刃闯,翻刃习科舟寿门二红二项,红习,红,卜牡而硕,斑习,耳 刁二,二现 在 的

11、问题是,对任 意 给 定 的路线图,如何定出这个求解 子 问题顺序的序列 呢拓 扑 排序是其中的一种 考虑。但是我们不 要忘记,即使这个 图中含有长度 为 正数的回路,问题 还 是 有 解 的,不过 这个 图就不能进行拓扑 排序了。另外,如果 图中含有起点可达的负 权回路,算法 应该宣告 原 问题无解,但是这个算法并 不能很好地解决这个问题。信息劈赛性,我们可以得到一个由口日修正甲飞习瑞。的公式,【习、】川。公当所有 的红日都不能再改 进的时候,几中存放 的就是由点到点的最短路的长度。这个算法可以写成一个反复迭代的过程,直到整个“系统”稳定下来 的时候,迭代结束。我们可以看作这个迭代过程 收敛

12、于问题的最优解。二对 所有的点。对所有 的点氏,。卿卜职司队,卜口职卜红 日巴,卜罗婉罗这个算法 的好处 在于它 的形式很简单,但是它的效率较低,而且还 有一个 缺 陷当图 中含有起点可达 的负权回路时,这个 算法会陷人 死循环。其实,当图中含有起点可达 的负权回路时,最 短路问题是无解 的。所以当图中含有负权边 的时候,在使用这个算法之前,要进行 额外的检查。正反思维,多向求解要从这个困局之中摆脱出来,不妨用逆向思维,从另一个角度 来看 这个问题。之前的分析是从终点开始,从后 向前逐步 递推求出各点到的最 短路径,最后求得从到的最短路径。其 实,最 短路还 有 另一个性 质 从 起 点到终点

13、的最 短路也 是起 点到该路径上各 点 的最短路径。从 这个性 质出发,我们可以从起点 出发,递推求出其他点 的最短路的长度。现 在 我 们 改 记江日表示由到 点的最 短路的 长度,例如,红表示由到的最短路的长度,红表 示由到的最短路的长度。显然有,而几用尹是 未 知 的,就记为妙日。我们将此作为初始 的已知条件。根据最短路这一特求最短路的】算法有 没有能克服 上面两个问题的算法 呢答 案是肯定 的。首先不妨假设图,中不含 负权回路,则红 词二价一定是从起点到的最短路的长度,因为几不可能继续改进了。然后对所有在中的点进行改进,则下 一个肯定已经求出最 短路的必 定 是二日翻坑势比林”位县知饥

14、匕心始矛从本书几湘用,如 此 下 去,可以肯定 的说,经 过次 迭代,定能求出所有点的最短路长度。下面我们完整地用伪码描述这个算法红二,迁二笋二二取二取日一对所有红二倾,取,二 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http:/信息绪赛这就是求 单源最 短路径 的算法。现 在我们 来 考 虑图中含 有 负 权回路的情况。如果 在算 法 执行 的过程 中存在某个且二且耳,司二几,则图中一定含有 负权回路,这时算 法应 终 止并 返回原 问题无解。如 果 我 们只需 要求出从

15、到的最 短路,则上面 的算法可 改写为 我们 把判 断负权回路也考虑进 去红,环 尹红环日一对所有平,。迁任问题无解红取,二红解表空邢从上 面的分析可以看出,我们从已知的初始状态出发,利用最优化 原理,一步 一步 向未知的目标状态推进,直到目标 状态解 决。从已知推广到 未知,这就是 动态规划 思 维方法 的精髓。算法与广度优先搜索如果我们再换一个 角度,从 图的搜索来重新 审视 这 个算法,就 会 发 现 我 们生成了一棵以结 点为根的搜索树,在 扩 展 结 点 的 时候,我们 每 次总是挑选 深度最小 的结 点进 行 扩展,这种做法其实就是图的广度优先搜 索。换而言之,图的广度优先搜索的思

16、想本 质 与 动 态 规 划 是 一 致 的。下 面我们 从 这个角度再来 重 写求解 最 短路的算法,以加深读 者对动态规划 的认识红,红尹表初始 为空,表初始 为结 点算法的时间复杂度分析我们 来 简单分 析一 下算法 的 时间复 杂度。一般 情况下,算法的时间复 杂度是,但是 当图是一个稀疏图时,特别 地,当所 有顶点的度数都有上界是 常数,如果数 据结构组织得当 例如,采用堆来存放表,可以将算法的 时间复杂度降为脚。当特别大的时候,这一点就显得至关重要了。我们将在以后 的专题 中进行分析。本期将刊登题应用最短路问题求解 的例题,供读者分析和学习。希望读者 能够从 题目的分析中领会这一点

17、 应用动态规划解题是 富于技巧 和创造性 的,没有固定 的模式可套题目出现 的形式多种多样,而且大部分表面 上与动态规划看不出直接的联系,只有在充分把握其思想精髓的前提下大胆联想,才能达到得心应手,灵活运用 的境界。了从表中选择值最小的结点放人表对所有二江红,环汪在表 中问题 无解红红,了扩展 出结点将结点放人表第一题相邻项序列问题描 述对于 一个感的正 整数 矩 阵,存在从,开始 到,结束的相邻项 序列。两个项【,和,相邻的条件 是 指 满足如下情况之一士和二和土任务从文件中输 人矩 阵,从文 件中输人组,和,的值,对于每一组,和,求一 相邻项序列,使得相邻项之差 的绝对值之和为最小。输入格

18、式从键盘输人数据文件及数据文件的文件名。输人数据文件格 式如下一一一表示矩阵的大小每行有个数据,共行吻一例的少践“什州替异知饥匕心竺刀”从小击几翻用 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http:/输人 数据 文件格 式 如下一一一表示有组数据一一一表 示,及,的值,共行翻抚少伪“什川哲异栩饥八七心蟹乖”八上去街朋用输出格式输出到数据 文件,文件名 由键盘输人一一一表示第组数据相邻项 之差的绝对值之和的最 小值为一一一表示第组数据的相邻序列一一一表示第组数据相邻项 之差

19、 的绝对值之和的最小值为一一一表示第组数据的相邻序列算法分析本题若将 相邻的两个数看作是两个顶 点,两个数差 的绝 对值作为权,则 问题便 转化成 图论中的求两顶点 间的最 短路问题。对于有 向图,弧二,相应 地有权,对有 向图中两个 顶 点、,设是中从到的一条 路,定 义路的权 是中所 有弧的权之和,记作,所 谓 最短路 问题就是 在所有从到的路中,找出一条权最短的路,即求一条从到的路,令对于所有,即所有 的权 为非负值时,求最短路通 常使用标 号 法。所谓标 号 法 的基 本 思 想 是 从出发,逐 步地向外探寻最 短路。在 执 行 过 程 中,与每 个 点对应,记录下一个 数称为 这个

20、点的标 号,它 或 者 表示从到该 点 的最 短路的权称 为标 号,或者 表示这个权的上 界称为标号,具 体 做法是 每 扩 展一步,就将一个具标号 的点改为具标号 的点,从而使有 向图中具标 号的顶点数增多一个。如此一步步执行下去,就可求出从到各点 的最短路。为 简便起 见,我们可以称从,到,周的相邻项之差 的绝 对值之和最 小 的相 邻 项序列 为从到【,的“最 优序列”。这 样便可 用标 号法来求得从起点,到 矩阵的其它各项 的“最优 序列”。设,为从,到,的“最 优 序列”的相邻项 的绝 对值 之和。有,一,士且,或且土通 过 这 一 式 子,可以利 用 标 号 法 来求得从流息章赛,

21、到,的“最优序列”。在标号法 中,每一次扩展 都要 寻找一个项,其 中,是未改 为标号 的点,二,且,功是未 改为标号的点。这一步若采用二重循环来求则非 常耗 时。所以考虑采用一个队列来存储矩 阵 中待扩展 的项,使得该队列的各项 的值是由小到大排列 的。扩展时,只要 移动队列的首指针即可生成 的新的待扩展 的项,可以将其插 人 到队列 中 的适 当位 置,使插人后 队列的各项 的值仍是从小到大排列。为了较方便地插人 新 的待扩展 的项,采用指针结构来存储这个队列。具 体算法描述如下定义一个类型来记录待扩展 的项犷二,其中,为该 项在矩 阵中的坐标,为指针类型,以记录其在队列中的后继结点。置,

22、为或,置,为首指针后移一位若且二,则已找到从,到,的“最优 序列”,反 向链接、打印所经的路径并转,否则继续从,向上 下左右四个方 向扩展,现设 向,士且,或八且土扩展二,一,若二,则继续,否则转二,一,是,的前 趋项,记下从,到,的方 向,以便 打印时反 向链接所经路径生 成 一 新 待 扩 展 结 点,使 得”,并把插人到 队列 中,使得卫卫 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http:/信户息章赛插人后队列的各项 的值仍是从小到大排列转结束。用一框图描述如下置置

23、刀为口或,里,为首首指针后移一位。、补之塑二燮二一一一一一一厂一一一一打打印印向四个 方 向扩展设设设设 向方向扩 展的项为又万,戊羹羹羹薪薪薪薪薪薪薪薪薪薪薪薪薪薪薪薪薪薪薪薪薪薪薪薪薪薪薪马呵尹抽 咧犷涅叭沉卜 卿洲习习一一一一一一删一笼八八川川一一一屯一一心一玲玲玲玲田,沉马记记记记下从,到的方 向生成新的待扩展结点少二把把把把插人到队 列中去,使队列各项的值仍仍仍扶扶扶扶从小 到士排列对 时 间、空间复 杂度的分析本算法 的时 间复 杂度约 为。由于对矩 阵中的某一 项,当其值每 改 变一次,就会 在队列中生成 一个新 的结 点,而 原来 的代 表该项 的结点就荒废不用。所以,本算法比

24、较浪费空间,但如果改为对 原结 点进 行修改再重 新 放人 队列,尽 管节 省了空间,但耗 时较多,显得 不合算了。本算法是用 空间来换取时间。第二题 猫捉老鼠问题描述有 如下 图形一个笼子,笼子 中方 格边长 为,共有感,蕊个 方格,其中打“”的方格放 有障碍物,不 可进 人。现在 笼 中有一只猫和一只老 鼠,猫 的 初 始 位 置已知,老 鼠在毛秒 内的运 动轨迹已知。老鼠每秒走一步,猫每秒 走步。所谓 一步是 指在 笼 子中从方格,运动到方格,且 指满足 如下情 况 之 一卜土和和土左上角 方 格坐标 为,右下 角方格坐标 为,。捉住 老鼠,则先输出,再输 出最 短时 间及运动轨迹。如果

25、不能捉住老 鼠,则输出。所谓猫在秒 内捉住老 鼠是 指猫 鼠在秒末 的相距步数不超过步。输入格式从键盘输人数据文件 的文件名输人数据文件格 式如下一一一表示 笼子大小,一一一表示每行有个数据,共行一一一表示无障碍,表示有 障碍一一一表示猫每秒走步一一一表示猫 的初始位置一一一表示老鼠走 了秒一一一表示 老 鼠初始位置一一一表示老 鼠第秒末 的位置一一一表示 老 鼠第秒末的位置一一一表示老 鼠第秒末 的位置输出格式输出到数 据文件,文件名 由键盘输 人。一一一表示能捉住老 鼠否则输出一一一表示能在最短 时 间秒 内捉住老 鼠一一一表示猫初始位置一一一表示猫第秒末的位置算法分析本题思路 十分简单,

26、将 问题转化成求最短路径问题。也 就是说,对每一个位置,分 别求出猫和老鼠到该位置 的最短路径,并分别计算出猫和老 鼠最短沿路径到达该位置所需 的最短时 间,通过时 间的比较就可以判断出猫是否能捉住老 鼠。在实现上,首先用标号法求出猫到达任意位置所需 的步数 标号法请参见上一题相邻项序列 的分析,然后判 断猫 能否在规 定 时 间 内走 完 捉 鼠所需的步数。时 间、空间复 杂度 均为,最 坏情况下 运算万次。用一框图描述如下口口口口同同同同口口口口口口任务 判断猫在秒 内能否捉住老 鼠。如果 能主主程序序初初始化化计计算猫能到达 的位置及其步数数判判断及输出结果细肠仆找“什川公异翎饥己心始未

27、”从土击儿湘用 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http:/邵井井浑置猫走 到秒末老鼠的位里所需 的步数一一迢竺少一一输输输出,及路径径径退退退出出出输输出如坑少浅“什川替开扣饥己心竺为“八,小约翻用第三题 旅游预算问题描 述一个 旅 行 社 需 要 估算乘 汽 车 从 某 城 市 到另一城 市 的最 小 费用,沿路有若干 加 油 站,每个加 油站收 费不一定相同。旅游 预算有如下规则若油箱 的油过半,不停车加油,除非 油箱 中的油 不可支持 到下 一 站每 次加油

28、时都加 满在 一个加油站 加油时,司机 要 花 费元买东西 吃司机不必 为其他 意情 况而 准备额外的油汽车开 出时在起点加满 油箱计算精确到分元分。编 写 程 序估计实际行 驶 在 某 路 线 所 需 的最 小费用。输入格式从 当前目录下的文本文件,读人数据。按以下格式输人若干旅 行路线的情况第一行 为起 点 到 终 点 的距 离 实数第 二 行 为三个的实数,后 跟 一 个 整 数,每两个数据 间用一个空格分隔。其 中第 一个数 为 汽 车 油 箱 的 容 量升,第二个 数 是 每 升 汽 油行 驶的公里数,第三个数 是 在 起点 加 满油箱所需的费 用,第四个数是 加油站 的数量感、接

29、下 去 的每 行 包 括两个 实数,每 个数据之 间用一个空格分隔,其 中第一 个数是 该加油站离起 点 的距离,第二个数是 该加 油 站每 升 汽油的价格元升。加油站 按 它们与起点的距离升序排列。所有 的输入 都一定有解。输出格式答 案输 出到 当前目录 下的丈本文件“”中。该 文件包 含两行。第一 行 为一 个 实数和一 个整数,实数 为旅 行 的最 小 费用,以元为单位,精确到流息章赛分,整数表示途 中加油的站 的总数。第二行是个整数,表示个加油的站 的编 号,按 升序 排列。数据间用一个空格分隔,此外 没有多余的空格。输人输出举例输人文件输出文件算法分析本题 的求解与求有 向图的最短

30、路径比较相似,也是 选取两点间 的直 接 连 线 费用和经 过某个 中间结点进行转折 费用 中的最小者。因此,求总费用的最小值可以分解为求若干分段 的费用最小值,它满足优化 原则,所以本题可以采用动态规划 的方法进行求解。二一二一口江从能直接到,二从能直接 到的费用,求出直接从到的费用一从能直接到二从到的费用从到的费用,了【,二中间经过是否能减少费用动态规划的求解过程然 后,从各油站 中找到 能直接到终 点,而且从起点到该站的值最 小 的油站。则该旅程的最小费用为该值加上在起点 的费用。然后利用下 面 的迭代 式就可以求出,中途所停的油站,直到二收稿日期一一,1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http:/