动态规划_搜索与最优化方法

《动态规划_搜索与最优化方法》由会员分享，可在线阅读，更多相关《动态规划_搜索与最优化方法（3页珍藏版）》请在金锄头文库上搜索。

1、栏目主持 : 石林才 E一m洲 : 。!ym P i 。 n e t t im氏n et .c n 享 今 初掌者园地 谁 缭、 乒才男 只 咬丸 题 东北育才学校 俞玮 最优化方法 近些年来 , 我们在解决信息学竞 赛试 题的过程中经 常会遇到一类问题 , 这类问题的解答都是用被称作 “动 态规划 ” 的方法解决的 。 可我们在对这些问题进行 研究 的时候 却发现 , 解 决 它 的方法虽 然同被 称为 “ 动态规 划 ”, 但解 决的途径却不尽相同 。 这也就 是动 态规划 方 法 与众不同的灵活性 。 F面我们就针讨动 态规划 的灵活 性而进行 一 些讨论 。 什 么是动态规划 们 么是

2、动态规划呢?这是我们首 先需要解决 的问题 。 我们用一个简单 的例 子来说明这个问题 。 【例 l】 给出 一个n 个节点的加权有向图 G , 图中的 边总是从编 号较小的节 点连到编 号较大 的节点的 。 求从 节点 l到节点 : 1 的最短路 径 。 七 士 我们注意到在这个图中 , 很 多 : 印盯 、二 都是进行了重 复计算的 。 例 如我们总共计算了两次 ,。叮。行州1 , 4 ) 长 次 厂。以u力 , 烈 1 , 2)及三次 : ,。q u 力 , 以l , 1) 。 这样重复的计算 很显然是无意义 的 , 我们 可 以把它 们改成如 下图所示的 计算方法 : 网络耐 技 代时

3、 争争匆橱 为了解决这个问题 , 我们约定用 厂。q u 厅 。 z 了 7夕 表示 求从 1 到 n 的最短路 的问题 。 这样 , 由于该最短路必然 是某条从1到某点 x 的最短路加卜从某点 x 再到 f l 的边构成 的 , 故对于所 有这样 的 X , 我们可 以得出如 下的式子 : 了 一口叮u 丁 : ,。 (l , n ) =m in; ,。叮。了 r口(l, x ) +g X ,n 例如对于图 l 中的例 子 , 我们 有 : r r req 照丝 夕(1 , 6) ) ) 茗茗弓 9 9拜 及以 , 2) ) ) r e, 泛二( l , 。 一 i 一 r eol r e

4、( l . 5 卜。 , 叫 理切二理( l , 勺十g日 , 6J j z, 和泛 )r o , 2 ) +g2 5 例泛咫( 1 , 幻+岌4 . 习 r e卯更r ez , 为+g2 , 4+g4 , 施 6 6 糟 解 二 5 , 6, , 理r e rlJ月 、l , 和,( l , 1 ) +g , “+ ) eq u如n , 2)+ 9 1 2 . 4 I w e e s 司 气 r. L g + 、 I L护e s 1.J 气 孕“( 1p 十9 11 , 2 十9 12 , 4+ 威4 , 6 f、列泛,口 , l ) + 或l , 2 1 + 就2 , 5 , In 1理切

5、 进召以,1 ) + 9 11 , 2+g t24 ) + 夙4 . 卯 Jr e ( l . l ) + 9 1 1 , 2 + 威2 , 月+9 1 4 、 6 m 理mr e 子 Ll l jql L 产 l 、 r a 这个式子并不是 一卜 分清晰, 我们现在用 图来表示这 个式子 : 娜雄绷翻翻瀚即日 也就是说 , 我们可以把已经计算出来的 : 阅l i 厂。 值保 存起来 , 然后在再次使用的时候直接查表找出来 , 而不 用再 次 计算 。 而在存储 l e叮u方二值的时候, 虽然 二。母叮 一。 有两个参 数 , 但山于 第一个参数均为 1 , 故不同的参数对只可能 有 n 个

6、, 所以我们可以用di 表示 二。母u1 二。(1,i) 的值并 保存 起来 。 这样 , 我们 就得到了一个对该 问题逆向求解 的动态规划的方法 。 我们还可 以按照i从 小到大的顺序依次计算出d i的 值 , 这样由于在 计算diJ的时候所有保证 g 、 , i 存在 x 的 。! x 的都已经计算出来了 , 故我们必然可 以得到d l i 的值 。 这 也就是一般的动态规划顺推的方 法 。 我们现在再来回顾 一下这一题 的解法 。 我们 首先是 45 栏目主持 : 石林才 E一m洲 : 。!ym P i 。 n e t t im氏n et .c n 享 今 初掌者园地 谁 缭、 乒才男

7、只 咬丸 题 东北育才学校 俞玮 最优化方法 近些年来 , 我们在解决信息学竞 赛试 题的过程中经 常会遇到一类问题 , 这类问题的解答都是用被称作 “动 态规划 ” 的方法解决的 。 可我们在对这些问题进行 研究 的时候 却发现 , 解 决 它 的方法虽 然同被 称为 “ 动态规 划 ”, 但解 决的途径却不尽相同 。 这也就 是动 态规划 方 法 与众不同的灵活性 。 F面我们就针讨动 态规划 的灵活 性而进行 一 些讨论 。 什 么是动态规划 们 么是动态规划呢?这是我们首 先需要解决 的问题 。 我们用一个简单 的例 子来说明这个问题 。 【例 l】 给出 一个n 个节点的加权有向图

8、G , 图中的 边总是从编 号较小的节 点连到编 号较大 的节点的 。 求从 节点 l到节点 : 1 的最短路 径 。 七 士 我们注意到在这个图中 , 很 多 : 印盯 、二 都是进行了重 复计算的 。 例 如我们总共计算了两次 ,。叮。行州1 , 4 ) 长 次 厂。以u力 , 烈 1 , 2)及三次 : ,。q u 力 , 以l , 1) 。 这样重复的计算 很显然是无意义 的 , 我们 可 以把它 们改成如 下图所示的 计算方法 : 网络耐 技 代时 争争匆橱 为了解决这个问题 , 我们约定用 厂。q u 厅 。 z 了 7夕 表示 求从 1 到 n 的最短路 的问题 。 这样 , 由

9、于该最短路必然 是某条从1到某点 x 的最短路加卜从某点 x 再到 f l 的边构成 的 , 故对于所 有这样 的 X , 我们可 以得出如 下的式子 : 了 一口叮u 丁 : ,。 (l , n ) =m in; ,。叮。了 r口(l, x ) +g X ,n 例如对于图 l 中的例 子 , 我们 有 : r r req 照丝 夕(1 , 6) ) ) 茗茗弓 9 9拜 及以 , 2) ) ) r e, 泛二( l , 。 一 i 一 r eol r e ( l . 5 卜。 , 叫 理切二理( l , 勺十g日 , 6J j z, 和泛 )r o , 2 ) +g2 5 例泛咫( 1 ,

10、幻+岌4 . 习 r e卯更r ez , 为+g2 , 4+g4 , 施 6 6 糟 解 二 5 , 6, , 理r e rlJ月 、l , 和,( l , 1 ) +g , “+ ) eq u如n , 2)+ 9 1 2 . 4 I w e e s 司 气 r. L g + 、 I L护e s 1.J 气 孕“( 1p 十9 11 , 2 十9 12 , 4+ 威4 , 6 f、列泛,口 , l ) + 或l , 2 1 + 就2 , 5 , In 1理切 进召以,1 ) + 9 11 , 2+g t24 ) + 夙4 . 卯 Jr e ( l . l ) + 9 1 1 , 2 + 威2

11、, 月+9 1 4 、 6 m 理mr e 子 Ll l jql L 产 l 、 r a 这个式子并不是 一卜 分清晰, 我们现在用 图来表示这 个式子 : 娜雄绷翻翻瀚即日 也就是说 , 我们可以把已经计算出来的 : 阅l i 厂。 值保 存起来 , 然后在再次使用的时候直接查表找出来 , 而不 用再 次 计算 。 而在存储 l e叮u方二值的时候, 虽然 二。母叮 一。 有两个参 数 , 但山于 第一个参数均为 1 , 故不同的参数对只可能 有 n 个 , 所以我们可以用di 表示 二。母u1 二。(1,i) 的值并 保存 起来 。 这样 , 我们 就得到了一个对该 问题逆向求解 的动态规

12、划的方法 。 我们还可 以按照i从 小到大的顺序依次计算出d i的 值 , 这样由于在 计算diJ的时候所有保证 g 、 , i 存在 x 的 。! x 的都已经计算出来了 , 故我们必然可 以得到d l i 的值 。 这 也就是一般的动态规划顺推的方 法 。 我们现在再来回顾 一下这一题 的解法 。 我们 首先是 45 替目主挤 右林才 E笼而a i ! : o l ympi c必。e tt i 邮 , 油仁 cn 初学者园地 我们不更改计算方法 , 那么第一 、 二条原则根本就没有 用武之 地 。 为什么呢?我们发现需要计算的总数事实上 是 一定的 , 而变换表示方法就是把所有 需要计算

13、的部分 按照他们 的某些性 质进行 分类 , 从而 在各类之 中造成重 复 。 例如在上例中 , 我们就是按照集合 S所对应的f ( s) 和 g (S )进行分类的 。 然后是对无序 的集合进行排序 , 例 如 我们从 x : 向 x, 计算的方法 。 这其实是一种在表示方法 上的技巧 , 为了是便于我们用数组 的下标来表示集合 。 因为我们无论按照什么样的方法计算出来的结果都是一样 的 , 而用一个数 n 来表示集合 x ,xZ, K , x n就是最 间接的方 法了 。 最后是我们状态选取 的问题 , 其实也还是如何应用 第三原则的问题 。 我们在状态表示的时候选取了集合S对应 藤绘棒扮

14、睡价犷篓献 的f( S )和 g( S)作为状态描述的一部分 。 这一方面是因为 f ( S )和 g ( S )为题目的限制 , 必须加入在状态的表示中 ; 另一 方面也是因为题目给出了他们的极值孺和蠕 , 使得我们得 以保存下来 。 这也就是说 , 我们在使用动态规划的时候还 要对注意题目的数据规模 , 换用不同的表示方法来的出最好 的表 示方法 。 策略的应用方法 其 实动态规划 的思想是非常简单的 。 无论是 最优化 原则还是什么状态的采用其实都是对 人们平时所习惯使用 的最优策略的一个抽象的概括 。 例如我们来看如下一道 最最 简 单的例题 : 例3给出 n 根重量为仁 l , 10

15、 间的整数的木棍的长 度 , 求不同重量的最长木 棍的长度 。 这题相信是大家闭着眼睛都可以做出来的题目了 。 只 要开一个 1二 1 0 的数组纪录不同重量的木棍的最大长度 , 并依次根据输入的木棍长度更新这个数组就可以了 。 那么 , 这个题目和动态 规划 有什么关系呢? 我们首先注 意到再解题 中我们是 “ 依次 ” 更新 。 这 样 , 在以k根 木棍对数组进行更新的时候 , 我们 当然要 用到前k 一1 根木棍的结果 , 也就是数组中原来的数据 。 这 与我们把对第1根到第k 一 1根木棍求解的结果保存下来其 实是一样的 。 还 有我们把木 棍按照它们 的重量分类分别 统计 , 也就

16、是采用数据规模较小 的重量而不是长度来表 示状态 。 这些都是动态规 划 的基本思想 。 试 回想起来 , 在求最大值的过 程中 , 相信没有 人会 每次把以前求出的 最大值重新 求一遍 , 然后再与当前值相比较的吧 ? 而按 照重量 进行 统计 , 也是很 自然的事 情 “ 自然 ” 的顺应 题目 , 这也就 是我们应用动态规划 时所采用的思路 。 数学模型的转化 最后 , 我们再举一个通过数学模型转化为动态规划方 法求解的问题为例说明一下应用动态规划解题的大概步骤 。 【 例4】现给出一个数列 a = a 1,aZ, K , a n , 并给出一 个定义在 这个数列上的运算 c on 。