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

信 夕息章赛 试题与脚法分析三 劫态视划友其表用 录扳路问题 郭篙山陈明睿 中山大学信息科技学 院计算机科学系 广州 动态规 划 实际上 是 研 究 一 类 最 优 化 问题 的方 法 在经 济 工 程 技 术 企 业 管 理 工 农 业生产及 军 事等 领 域 中都 有 广 泛的应用 近年 来 在 中 使 用动态 规 划或部分 应 用动态规划 思 维求解 的题不仅常见 而且形式也多种多样 而在 与此相 近的各类信息学竞赛中 应用动态规划解题 已经成为一种趋势 这和动态规划 的优势不无关系 与其说动态 规划是一种算法 不如说是一种思 维方法来 得贴切 因为动态规划 没有固定 的框架 即便是应用到 同一道题上 也可以建立多种形式的 求解算法 许多隐式 图上 的算法 例如求单源最短路 径 的算法 广度优 先搜索算 法 都渗透着动 态规划的思想 还有许多数学问题 表面上看起来与 动态规划风马牛不相及 但是其求解思想 与动态规 划是完全一致 的 正因为如此 今后我们还将会分几 个专题 对动态规划的应用分 门别类地进行介绍 如 场少找 曰 什 州 检且 知饥 匕心廿 未 山南乃湘用 动态规划的概念和基础 什么是 动态规 划动 态 规 划 是 运 筹 学的一个 分支 年美国数 学 家等人 根据一 类多阶段问题 的特点 把 多 阶段 决策 问题变换 为一 系列 互 相联 系 的单阶段 问题 然后逐 个 加以解 决 一些静态模型 只要 人 为地 引进 时 间 因素 分 成 时段 就 可以转 化 成 多 阶段的动 态模型 用动态规 亚 洲上海 赛区中山大学二 队教练 一 亚 洲上海 赛区中山大学二 队主力队员 划方法去处理 与此 同时 他提 出了解决这类问题 的 最优化原理 一个过程 的最优 决 策具 有 这 样的性质即无 论其初始状态和初始决策如何 其今后诸策略对以 第一 个决策所形成 的状态作为初始状 态 的过程而 言 必须构成最优策 略 简言之 一个最优策 略的 子策 略 对于它 的初态和终态而 言也必是最优 的 这个 最优 化原理 如果 用数 学化 一点 的语 言 来描述 的话 就是 假设为了解 决某一优化 问题 需 要依 次作出个 决策 如若这个决 策 序列是 最优 的 对于任何一个 整数 不论 前面个决策是怎样的 以后 的最优决策只取决于 由前面决策所确定 的当前状 态 即以后 的决策 也是 最优的 最优化原理是 动态规划 理论的基 础 动态规 划实 际上是一种寻找组合最优化 问题的最优解 的 方法 它将一个待求的最优化 问题分解成几个子问 题 先寻找子 问题 的局部 最优 解 并 用逆推公式把 原 问题的最优解 与子问题的局部最优解联系起来 最后 获得所求问题 的最优解 最优 化 原理说起来 很简单 如何灵活应 用它则又是另一回事 它用途 很广 由于运用最优化原理来解决的问题本身并没 有固定不变 的算法 需要不断地探索其规律并进行 归纳和 总结 因此 利用它来解决 问题的本身也就 是一种创造 我们 下面希望 通 过讲解 动态规划 的 1994 2009 China Academic Journal Electronic Publishing House All rights reserved 信息萦赛 一个重要 应用一一最 短路问题 来 帮助读 者初 步掌 握它的技巧 最短路问题 所谓最短路问题是 指给定起点及终点 并知道 由起点到终点的各种 可 能 的路径 问题是要 找一条 由起点 到终点的最短 的路 即长 度最短 的路 需要 指出 的是 最 短路问题中的 长 度 可 以是 通 常意 义 下的距 离 也 可以是 运输的时 间或 者 运 输 费用等 等 而且 有些 与运输根本 没有关系的问题也可以 化 为求最 短路的模型 例 如求关键路径实 际上是 网中的最 长路问题等 由起点到 终点的路线图如图所 示 连 接两地之间的路的长度用连 线上 的数字表示 求由 起点到终点的最 短路 我们很 容 易可以得 到 一个递归形 式的算 法来求解 最短路问题 求由几到 的最短路的长度 已求 出 润田 日 对所 有 四 少 小 声 图 一 般 地 求一个具有个结点的 图 的最 短路 如果使用穷举法 其运算量 是的指数函数 当 比较大 同时 图 的深度 较深时 这个算法 在 时 间效 率上是 不 可取的 如果用最 优化原 理来思考这个 问题 我们可以注意 到 最 短路有 这样 一 个 特性 即 如果 最 短路的第站 通 过 则 这 一 最 短 路在 由 出发到达终点的那一部分路径 对于起点为到 终点所有可能的路径来说 必定也是长度最短的 引入几个记号 记妙日表示 由点到的最 短路的长度 例如 私 表示由到的最 短路的 长度 几 表示由到的最 短路的长度 表示从 点出发 到 下 一 步 所 选 的点 的集合 田 表示点 到下 一步所选 的点的长度 例如 表示 由到 的距离 即 二 则最短路这一特性 可 描述为 日 公 显 然 有 哪 二 而几勾 尹 是 未知的 我们 将此作为初始 的已知条件 根据最 短路这一特性 职小 队 项 调用 求出 的最 短路 为 今今今今 长度 为 如图中粗线所示 我们 实际 上 是将 求解到的 最 短路问题 分解成 结构 相同的若干个子 问题 习 胆 这些 子 问题之 间可 能 有 重 叠 在求 解 的过 程 中 如果某个需要求解 的子 问题已经解 出 来了 就直接取其结果如果还没有解 出来 就递归 进行求解 然后通过这些子问题的解来求出原问题 的解 其结果 我们不仅得到了原 问题 的解 而且得 到了一连串子问题的解 动态规划之所以 比穷举法 高效的原因 就在于它对每个子问题只求解一次 与穷举法相比 动态规划 的方法有 两个明显 的 优点 大大减少了计算量 丰富了计算结果 从上面例子 的求解结果 中 我们得到 的不仅是 由起点出发到终点的最短路 而且还得 到 了 从所有各 中间点到终点的最短路 这对许多实际问 题来讲是很有用的 你也许会想 动态规划是不是分而治之呢其 实 虽然 在分析许多 问题时 我们都使用了这 种将 大问题分解成小 问题的思路 但是动态规划不是分 治法 这一点我们将在以后 的专题中加以分析 另一种表示形式递推 上面我们用递归 的形式描 述 了最 短路问题 的 求解方法 既然每个子 问题只求解一次 我们是不 是可以确定 出一个求解 子问题顺序 用递推的方法 来求解 最短路问题呢其实这样 的顺序是很容 易 确定的 例如 事实 涛 福场少找 什 曹异 翎饥 匕 心蟹矛 从小书伪湘用 1994 2009 China Academic Journal Electronic Publishing House All rights reserved 上 如果 把 这个 路线图看 成是一 个 有 向带权 图的 话 它的任 一个拓 扑序列的逆序都可以作为求解 子 问题顺 序 的序列 于是我 们 就 得 到 了一 个求最 短 路问题的递推 形 式 的算法 令 二 公是某个 求解 子 问题顺 序 的 序列 而且且已经解 出 二 红 二 而 即项乓 我们 现在用手 工来计算一下 你就会对整个递 推过程有更加 清 晰 的理解了 邢 二 终 态 已知 和于 硕 和 二 耳 二 兀 二 项口 硕 二 几 项 十红 习 曰 耳 红 项月 卜 红而 斑 项刁科 二 毋汾翎项口 朝刃闯 翻刃习 科舟寿门 二 红 二 项 红习 红 卜 牡 而硕 斑习 耳 刁二 二 现 在 的 问题是 对任 意 给 定 的路线图 如何定 出这个求解 子 问题顺序的序列 呢拓 扑 排序是其 中的一种 考虑 但是我们不 要忘记 即使这个 图中 含有长度 为 正数的回路 问题 还 是 有 解 的 不过 这 个 图就不能进行拓扑 排序了 另外 如果 图中含有 起点可达的负 权回路 算法 应该宣告 原 问题无解 但是这个算法并 不能很好地解决这个问题 信息劈赛 性 我们可以得到一个由口日修正甲飞习瑞 的 公式 习 川 公 当所有 的红日都不能再改 进的时候 几中存 放 的就是由点到点的最短路的长度 这个算 法可以写成一个反复迭代的过程 直到整个 系统 稳定下来 的时候 迭代结束 我们可以看作这个迭 代过程 收敛于问题的最优解 二 对 所有的点 对所有 的点氏 卿 卜 职司队 卜口 职 卜 红 日 巴 卜 罗婉 罗 这个算法 的好处 在于它 的形式很简单 但是它 的效率较低 而且还 有一个 缺 陷当图 中含有起点 可达 的负权回路时 这个 算法会陷人 死循环 其 实 当图中含有起点可达 的负权回路时 最 短路问 题是无解 的 所以当图中含有负权边 的时候 在使 用这个算法之前 要进行 额外的检查 正反思维 多向求解 要从这个困局之中摆脱出来 不妨用逆向思 维 从另一个角度 来看 这个问题 之前的分析是从终点开始 从后 向前逐步 递推 求出各点到的最 短路径 最后求得从到的 最短路径 其 实 最 短路还 有 另一个性 质 从 起 点 到终点的最 短路也 是起 点到该路径上各 点 的最短 路径 从 这个性 质出发 我们可以从起点 出发 递 推求出其他点 的最短路的长度 现 在 我 们 改 记江日表示由到 点的最 短 路的 长度 例如 红表示由到的最短路的长 度 红 表 示由到的最短路的长度 显然有 而几用 尹 是 未 知 的 就记为 妙日 我们将此作为初始 的已知条件 根据最短路这一特 求最短路的 算法 有 没有能克服 上面两个问题的算法 呢答 案 是肯定 的 首先不妨假设图 中不含 负权 回路 则红 词 二 价一定是从起点到 的最短路的长度 因为几不可能继续改进了 然 后对所有在中的点进行改进 则下 一个肯定已 经求出最 短路的必 定 是 二 日 翻 坑 势 比 林 位 县 知饥 匕心始矛从本书几湘用 如 此 下 去 可以肯定 的说 经 过次 迭代 定能求出所有点的最短路长度 下面我们完整地用伪码描述这个算法 红 二 迁 二 笋 二 二 取 二 取日 一 对所有红 二 倾 取 二 1994 2009 China Academic Journal Electronic Publishing House All rights reserved 信息绪赛 这就是求 单源最 短路径 的算法 现 在我们 来 考 虑图中含 有 负 权回路的情 况 如果 在算 法 执行 的过程 中存在某个且 二 且耳 司 二 几 则图中一定含有 负权 回路 这时算 法应 终 止并 返回原 问题无解 如 果 我 们只需 要求出从到的最 短路 则 上面 的算法可 改写为 我们 把判 断负权回路也考虑 进 去 红 环 尹 红环日 一 对所有 平 迁 任 问题无解 红取 二 红 解 表空 邢 从上 面的分析可以看出 我们从已知的初始状 态出发 利用最优化 原理 一步 一步 向未知的目标 状态推进 直到目标 状态解 决 从已知推广到 未 知 这就是 动态规划 思 维方法 的精髓 算法与广度优先搜索 如果我们再换一个 角度 从 图的搜索来重新 审 视 这 个算法 就 会 发 现 我 们生成了一棵以结 点 为根的搜索树 在 扩 展 结 点 的 时候 我们 每 次总是 挑选 深度最小 的结 点进 行 扩展 这种做法其实就是 图的广度优先搜 索 换而言之 图的广度优先搜索 的思想本 质 与 动 态 规 划 是 一 致 的 下 面我们 从 这 个角度再来 重 写求解 最 短路的算法 以加深读 者对 动态规划 的认识 红 红 尹 表初始 为空 表初始 为结 点 算法的时间复杂度分析 我们 来 简单分 析一 下算法 的 时间复 杂度 一 般 情况下 算法的时间复 杂度是 但 是 当图是一个稀疏图时 特别 地 当所 有顶点的 度数都有上界是 常数 如果数 据结构组织得 当 例如 采用堆来存放表 可以将 算法的 时间复杂度降为 脚 当特别大的时 候 这一点就显得至关重要了 我们将在以后 的专 题 中进行分析 本期将刊登题应用最短路问题求解 的例题 供读者分析和学习 希望读者 能够从 题目的分析 中领会这一点 应用动态规划解题是 富于技巧 和创 造性 的 没有固定 的模式可套题目出现 的形式多 种多样 而且大部分表面 上与动态规划看不出直接 的联系 只有在充分把握其思想精髓的前提下大胆 联想 才能达到得心应手 灵活运用 的境界 了 从表中选择值最小的结点放人表 对所有 二 江红 环 汪 在表 中 问题 无解 红红 了扩展 出结点 将结点放人表 第一题相邻项序列 问题描 述 对于 一个 感 的正 整数 矩 阵 存 在从 开始 到 结束的相邻项 序 列 两个项 和 相邻的条件 是 指 满足 如下情况之一 士 和 二 和 土 任务从文件中输 人矩 阵 从文 件中输 人组 和 的值 对于每 一组 和 求一 相邻项序列 使 得相邻项之差 的绝对值之和为最小 输入格式 从键盘输人数据文件及数据文件的文件名 输人数据文件格 式如下 一一一 表示矩阵的大小 每行有个数据 共行 吻 一例的 少 践 什 州替 异知饥 匕心竺 刀 从 小击几翻用 1994 2009 China Academic Journal Electronic Publishing House All rights reserved 输人 数据 文件格 式 如下 一一一表示有 组数据 一一一表 示 及 的值 共行 翻抚少 伪 什 川 哲异栩饥 八七 心蟹乖 八上去街朋用 输出格式 输出到数据 文件 文件名 由键盘输人 一一一表示第 组数据相邻项 之差的 绝对值之和的最 小值为 一一一表示第 组数据的相邻序列 一一一表示第 组数据相邻项 之差 的 绝对值之和的最小值为 一一一表示第 组数据的相邻序列 算法分析 本题若将 相邻的两个数看作是两个顶 点 两个 数差 的绝 对值作为权 则 问题便 转化成 图论中的求 两顶点 间的最 短路问题 对于有 向图 弧 二 相应 地有 权 对有 向图中两个 顶 点 设 是中从到的一条 路 定 义路的权 是 中所 有弧的权之和 记作 所 谓 最短路 问题 就是 在所有从到的路中 找出一条权最短的 路 即求一条从到的路 令 对于所有 即所有 的权 为非负值时 求 最短路通 常使用标 号 法 所谓标 号 法 的基 本 思 想 是 从出发 逐 步地 向外探寻最 短路 在 执 行 过 程 中 与每 个 点对应 记录下一个 数称为 这个 点的标 号 它 或 者 表示从 到该 点 的最 短路的权称 为标 号 或者 表示这 个权的上 界称为标号 具 体 做法是 每 扩 展一 步 就将一个具标号 的点改为具标号 的点 从而 使有 向图中具标 号的顶点数增多一个 如此一 步步执行下去 就可求出从到各点 的最短路 为 简便起 见 我们可以称从 到 周的 相邻项之差 的绝 对值之和最 小 的相 邻 项序列 为从 到 的 最 优序列 这 样便可 用标 号法 来求得从起点 到 矩阵的其它各项 的 最优 序列 设 为从 到 的 最 优 序 列 的相邻 项 的绝 对值 之和 有 一 士 且 或 且 土 通 过 这 一 式 子 可以利 用 标 号 法 来求得从 流息章赛 到 的 最优序列 在标号法 中 每 一次扩展 都要 寻找一个项 其 中 是未改 为标号 的点 二 且 功是未 改为 标号的点 这一步若采用二重循环来求则非 常耗 时 所 以考虑采用一个队列来存储矩 阵 中待扩展 的项 使 得该队列的各项 的值是由小到大排列 的 扩 展时 只要 移动队列的首指针即可生成 的新的待扩 展 的项 可以将其插 人 到队列 中 的适 当位 置 使插 人后 队列的各项 的值仍是从小到大排列 为 了较方便地插人 新 的待扩展 的项 采用指针结构来 存储这个队列 具 体算法描述如下 定义一个类型来记录待扩展 的项 犷 二 其中 为该 项在矩 阵中的坐标 为 指针类型 以记录其在队列中的后继结点 置 为或 置 为 首指针后移一位 若且 二 则已找到从 到 的 最优 序列 反 向链 接 打印所经 的路径并转 否 则继续 从 向上 下左右四个方 向扩展 现设 向 士 且 或 八 且 土 扩展 二 一 若 二 则继 续 否 则转 二 一 是 的 前 趋项 记下从 到 的方 向 以便 打印时反 向链接所经路径 生 成 一 新 待 扩 展 结 点 使 得 并把插人到 队列 中 使得 卫卫 1994 2009 China Academic Journal Electronic Publishing House All rights reserved 信 户息章赛 插人后队列的各项 的值仍是从小到大排列 转 结束 用 一 框图描述如下 置置 刀为口或 里 为 首首指针后移一位 补之 塑二燮二一一一 一一一厂一一一 一 打打印印向四个 方 向扩展 设设设设 向方向扩 展的项为 又 万 戊 羹羹羹薪薪薪薪薪薪薪薪薪薪薪薪薪薪薪薪薪薪薪薪薪薪薪薪薪薪薪 马呵尹抽 咧犷涅 叭沉卜 卿 洲 习习 一一一一一一 删 一笼八 八川 川 一一一 屯一一心一 玲玲玲玲 田 沉 马 记记记记下从 到的方 向 生成新的待扩展结点 少 二 把把把把插人到队 列中去 使队列各项 的值仍仍仍 扶扶扶扶从小 到士排列 对 时 间 空 间复 杂度的分析 本算法 的时 间复 杂度约 为 由于对矩 阵 中的某一 项 当其值每 改 变一次 就会 在队列 中生成 一个新 的结 点 而 原来 的代 表该项 的结点就 荒废不用 所以 本算法比较浪费空间 但如果改为 对 原结 点进 行修改再重 新 放人 队列 尽 管节 省了空 间 但耗 时较多 显得 不合算了 本算法是用 空间来 换取时间 第二题 猫捉老鼠 问题描述 有 如下 图形一个笼子 笼子 中方 格边长 为 共 有 感 蕊 个 方格 其中打 的 方格放 有障碍物 不 可进 人 现在 笼 中有一只猫和 一只老 鼠 猫 的 初 始 位 置已知 老 鼠在 毛 秒 内的运 动轨迹已知 老鼠每秒走一步 猫每秒 走 步 所谓 一步是 指在 笼 子中从方格 运动到 方格 且 指满足 如下情 况 之 一卜 土 和 和 土 左上角 方 格坐标 为 右下 角方格坐标 为 捉住 老鼠 则先输出 再输 出最 短时 间及运动 轨迹 如果不能捉住老 鼠 则输出 所谓猫在 秒 内捉住老 鼠是 指猫 鼠在秒末 的相距步数不超 过步 输入格式 从键盘输人数据文件 的文件名 输人数据文件格 式如下 一一一表示 笼子大小 一一一表示每行有个数据 共行 一一一表示无障碍 表示有 障碍 一一一表示猫每秒走步 一一一表示猫 的初始位置 一一一表示老鼠走 了秒 一一一表示 老 鼠初始位置 一一一表示老 鼠第 秒末 的位置 一一一表示 老 鼠第秒末的位置 一一一表示老 鼠第 秒末 的位置 输出格式 输出到数 据文件 文件名 由键盘输 人 一一一表示能捉住老 鼠 否则输出 一一一表示能在最短 时 间秒 内捉住老 鼠 一一一表示猫初始位置 一一一表示猫第 秒末的位置 算法分析 本题思路 十分简单 将 问题转化成求最短路径 问题 也 就是说 对每一个位置 分 别求出猫和老 鼠到该位置 的最短路径 并分别计算出猫和老 鼠最 短沿路径到达该位置所需 的最短时 间 通过时 间的 比较就可以判断出猫是否能捉住老 鼠 在实现上 首先用标号法求出猫到达任意位置 所需 的步数 标号法请参见上一题相邻项序列 的分 析 然后判 断猫 能否在规 定 时 间 内走 完 捉 鼠所需 的步数 时 间 空间复 杂度 均为 最 坏情况下 运 算万次 用 一 框图描述如下 口口口口 同同同同 口口口口口口 任务 判断猫在秒 内能否捉住老 鼠 如果 能 主主程序序 初初始化化 计计算猫能到达 的位置及其步数数 判判断及输出结果 细 肠仆 找 什 川 公 异 翎饥己心始未 从土击儿湘用 1994 2009 China Academic Journal Electronic Publishing House All rights reserved 邵 井井浑置 猫走 到秒末老鼠的位里所需 的步数 一一迢竺少 一 一 输输输出 及路径径径 退退退出出出 输输出 如 坑少 浅 什 川 替 开扣饥 己心竺为 八 小 约翻用 第三题 旅游预算 问题描 述 一个 旅 行 社 需 要 估算乘 汽 车 从 某 城 市 到另一 城 市 的最 小 费用 沿路有若干 加 油 站 每个加 油站 收 费不一定相同 旅游 预算有如下规则 若油箱 的油过半 不停车加油 除非 油箱 中 的油 不可支持 到下 一 站 每 次加油时都加 满 在 一个加油站 加油时 司机 要 花 费元买 东西 吃 司机不必 为其他 意情 况而 准