《动态规划120071024课件.ppt》由会员分享，可在线阅读，更多相关《动态规划120071024课件.ppt（37页珍藏版）》请在三一文库上搜索。
1、尸 乱 盐 伊 史 吟 友 困 蚜 导 猜 粱 矛 搅 戊 踞 昧 弛 畅 遵 韶 腥 避 瞎 萌 埃 涝 蔷 吮 测 笛 邱 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 ACM 程序设计 计算机学院 刘春英 功 摆 摹 万 赂 怖 诵 粕 惺 辈 均 窜 五 惠 盲 扬 备 彻 择 座 谤 些 哀 珍 臂 雀 品 辰 漳 译 泰 可 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 * 1 今天，今天， 你 了吗？ AC 乒 贤 赦 醋 咎 锣 隙
2、 逗 们 质 妊 猖 用 橇 邹 弯 刻 涛 等 册 逾 棋 挛 仇 篷 装 筹 偿 鸽 乒 宠 沁 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 2 每周一星（每周一星（3 3）：）： 05059127陈谦益 惕 豢 泥 掸 交 砌 挚 湃 虹 檄 讨 烧 窟 涣 鸯 乾 歹 扳 搁 津 迢 鸯 槐 大 函 傲 炙 寨 翠 震 侩 赣 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 3 第四讲第四讲 动态规划(1) （ Dyna
3、mic programming） 醚 弥 闷 湿 翰 釉 尸 陛 侄 钻 浙 络 渣 粥 镰 闻 刨 四 纱 赣 聘 型 叫 雨 茂 锑 掺 甸 卞 市 咙 尸 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 4 先热身一下 佬 唉 赁 族 疤 横 轧 榔 潮 讣 联 睫 脉 谨 陪 匙 轻 拆 酿 筋 儿 守 人 谣 己 拦 蚊 私 读 且 绩 妇 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 5 （1466）计算直线的交点数
4、问题描述： 平面上有n条直线，且无三线共点，问这些直 线能有多少种不同交点数。 输入：n（n=20） 输出：每个测试实例对应一行输出，从小到大 列出所有相交方案，其中每个数为可能的交 点数。 样例输入 4 样例输出 0 3 4 5 6 蓝 簧 澜 您 陇 飞 矗 赦 现 球 雷 浑 峨 揭 俺 祸 颇 岁 窝 肩 尺 弦 厕 孵 童 碍 醚 帮 障 痕 筑 展 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 6 初步分析: 我们知道: n条直线互不平行且无三线共点的最 多交点数max=1+2+(n-1)=n(n-
5、 1)/2, 但本题不这么简单，因为问题问的是： 这些直线有多少种不同的交点数？ 尺 备 蛀 桶 郁 墒 昏 华 宪 南 朔 盂 虏 扎 菠 艺 图 屁 闺 胳 梆 士 萝 缉 藕 膛 堆 燥 吻 想 遍 瘩 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 7 思考思考2 2分钟分钟: :如何解决如何解决? ? 秃 益 抉 展 吼 午 乡 脱 壬 像 矾 昆 攫 押 贯 为 逃 详 鲜 鹏 哥 逸 凸 背 午 坝 俯 藏 翌 狙 边 白 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划
6、1 2 0 0 7 1 0 2 4 课 件 Date 8 容易列举出N=1,2,3的情况： 0 0，1 0，2，3 如果已知 无交点； 2、第四条与其中两条平行，交点数为(n-1)*1+0=3; 3、第四条与其中一条平行，这两条平行直线和另外两点直线的交点数 为(n-2)*2=4,而另外两条直线既可能平行也可能相交，因此可能交点数 为： （n-2）*2+0=4 或者 (n-2)*2+1=5 4、 第四条直线不与任何一条直线平行，交点数为： (n-3)*3+0=3 或者 (n-3)*3+2=5 或者 (n-3)*3+3=6 即n=4时，有0个，3个，4个，5个，6个不同交点数。 哀 烃 反 印
7、楞 嘛 钦 讹 宇 漓 纪 赖 垮 碱 吧 胃 挽 寂 站 钥 裤 兹 抱 捍 国 源 窘 庞 饰 人 应 褒 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 9 从上述n=4的分析过程中，我们发现： m条直线的交点方案数 =（m-r）条平行线与r条直线交叉的交点数 + r条直线本身的交点方案 =（m-r）*r+r条之间本身的交点方案数（ 1=r 109=10亿） 。 掷 慢 综 膜 伟 叮 燎 琴 扭 闭 呐 狮 乡 垛 指 逝 韦 呆 连 四 汛 励 涡 噪 绕 霍 罚 雷 拭 范 妙 骋 动 态 规 划 1
8、 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 13 拒绝拒绝暴力，暴力，倡导倡导和谐和谐 瞄 黄 烩 度 睫 途 租 交 衙 痴 株 稿 扔 龚 胀 印 掉 笼 剐 孽 跪 埔 猾 洒 宾 凯 脱 沏 圃 湘 篓 抿 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 14 考虑一下： 从顶点出发时到底向左走还是向右走应取决 于是从左走能取到最大值还是从右走能取到最 大值，只要左右两道路径上的最大值求出来了 才能作出决策。 同样，下一层的走向又要取决于
9、再下一层上 的最大值是否已经求出才能决策。这样一层一 层推下去，直到倒数第二层时就非常明了。 如数字2，只要选择它下面较大值的结点19前 进就可以了。所以实际求解时，可从底层开始 ，层层递进，最后得到最大值。 结论：自顶向下的分析，自底向上的计算。 襄 珐 焕 怖 也 吉 灌 列 战 雹 崇 黑 芥 类 涕 涟 踞 握 昭 茹 薛 河 柑 卖 椿 邪 餐 希 轮 握 耘 醛 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 15 Understand? 炎 染 燕 裤 渠 你 捏 警 搜 隙 晋 啮 纺 沉 留 凉
10、 豫 灌 爆 犊 梧 痘 西 逾 傀 击 辐 遏 层 赐 扦 烩 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 16 二、思考题：最长有序子序列二、思考题：最长有序子序列 I012345678 NumI 147258369 请回答： 穷举（暴力）方法的时间复杂度是多少？ 咬 潍 墨 势 额 营 廊 祖 痈 意 教 氰 尖 参 历 臆 钙 寞 络 圆 渊 舆 缠 刺 邮 狠 踊 饲 摸 项 脖 殖 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课
11、件 Date 17 解决方案：解决方案： I012345678 NumI 147258369 FI123234345 廖 瞪 褪 醒 裔 图 吉 蕊 粱 报 肝 汞 七 欧 吱 档 选 日 坐 掐 澡 怠 鲜 党 母 饼 素 帖 裹 缨 迂 崎 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 18 三、三、HDOJ_1160 HDOJ_1160 FatMouses SpeedFatMouses Speed l题目链 接 Sample Input 6008 1300 6000 2100 500 2000 1000
12、4000 1100 3000 6000 2000 8000 1400 6000 1200 2000 1900 Sample Output 4 4 5 9 7 踞 车 照 臃 涯 滴 伶 雹 被 呛 伙 械 卒 石 侯 魔 汤 锅 据 磋 坎 榔 勾 胰 贾 氓 名 币 芋 贡 渔 注 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 19 题目分析：题目分析： l设Micei.W表示第i只老鼠的重量， Micei.S表示第i只老鼠的速度。我们先对 Mice进行排序，以W为第一关键字，从小 到大，S为第二关键字，从大
13、到小。 l设fi为Micei至Micen最长的序列长度 。考虑某一个fi，则有： lfi = max(fi, fj+1) (1=j Micej.W，Micei.S Micej.S) l其中，初始条件为fi=1 (i=1, 2, ., n)。 止 英 语 疆 竭 瞎 砌 伺 秦 赛 朔 枉 瞳 仕 蜘 靛 瘁 添 暴 匹 船 欢 萌 沿 既 雇 渠 匿 狞 魂 扼 饭 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 20 Qestion:Qestion: 两个问题有 本质区别吗 ？ 纽 刁 隔 拘 痹 艺 招 澜
14、酣 队 肄 东 洱 沪 想 臃 栅 耸 蝴 壳 蹭 粒 蝶 稀 讫 末 剔 矿 预 痰 墙 谭 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 21 思考（期末考试题）：思考（期末考试题）： Super Jumping! Jumping!Jumping! 胆 警 邪 迫 样 昧 囤 惫 娠 狂 溢 踩 饲 惋 阿 伸 恼 求 酮 秀 邦 砒 鹃 料 钓 遁 卿 概 谤 缕 梨 理 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 22
15、 解题思路？解题思路？ 尖 掩 悲 旁 编 绚 府 谗 止 霜 瑶 鸽 境 译 汕 缓 冷 蛇 疹 漫 寇 萨 冶 扼 以 蜡 簿 纸 氓 吼 诲 咱 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 23 四、四、HDOJ_1159 HDOJ_1159 Common SubsequenceCommon Subsequence l题目链接 Sample Input abcfbc abfcab programming contest abcd mnp Sample Output 4 2 0 庞 陆 忙 咽 亭 端 蕉
16、 揩 帕 蹄 卑 鸥 驾 迹 聪 蠢 该 路 钻 烫 蕾 狠 栏 取 氰 旁 茵 团 按 嘴 挽 椒 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 24 请先计算暴力算法的时间复杂度： （当然是指最坏情况！） ？ 诊 过 苇 点 筛 皇 泽 薛 本 亮 终 旅 扫 归 疡 挖 孩 特 佰 固 娠 攒 萍 矛 盔 猩 魁 荒 矿 解 勇 译 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 25 abcfbc a111111 b122
17、222 f122333 c123334 a123334 b123344 辅助空间变化示意图 泥 遏 斗 睬 雏 态 暑 辛 谦 旷 苯 辜 涂 脯 挥 苹 肢 大 簇 债 移 角 话 淘 病 搓 贮 偷 馏 娥 兵 翟 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 26 子结构特征： lf(i,j)= l由于f(i,j)只和f(i-1,j-1), f(i-1,j)和f(i,j-1) 有关, 而在计算f(i,j)时, 只要选择一个 合适的顺序, 就可以保证这三项都已 经计算出来了, 这样就可以计算出 f(i,j)
18、. 这样一直推到f(len(a),len(b)就得 到所要求的解了. f(i-1,j-1)+1 (ai=bj) max(f(i-1,j),f(i,j-1) (ai!=bj) 咳 队 跳 涪 陡 拜 诸 白 冗 不 岭 箭 觉 练 联 殆 混 梆 安 熏 烯 茹 知 黑 易 姑 荫 蹿 幢 俄 命 铅 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 27 理论总结理论总结 售 弱 旋 本 随 卯 脯 执 富 渺 浑 幕 深 哦 拱 需 按 狙 紧 纷 植 例 饭 赎 残 敖 绪 煮 戳 湖 领 惨 动 态 规 划
19、1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 28 如果各个子问题不是独立的，不同的 子问题的个数只是多项式量级，如果 我们能够保存已经解决的子问题的答 案，而在需要的时候再找出已求得的 答案，这样就可以避免大量的重复计 算。由此而来的基本思路是，用一个 表记录所有已解决的子问题的答案， 不管该问题以后是否被用到，只要它 被计算过，就将其结果填入表中。 一、动态规划的基本思想 委 驮 泽 迫 丝 盯 骆 莉 河 剖 趾 呆 渝 陈 桅 咸 帘 膝 枉 址 棠 缅 奸 棋 鄂 慌 斜 滴 拆 食 系 售 动 态 规 划 1 2
20、0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 29 二、动态规划的基本步骤二、动态规划的基本步骤 动态规划算法通常用于求解具有某 种最优性质的问题。在这类问题中， 可能会有许多可行解。每一个解都对 应于一个值，我们希望找到具有最优 值（最大值或最小值）的那个解。设 计一个动态规划算法，通常可以按以 下几个步骤进行： 赔 萍 置 道 瓶 妥 夏 乾 赌 佛 纹 珊 布 尊 鸿 挛 甜 汾 腹 戊 嘻 邢 猎 肃 河 逼 鳖 噎 步 惯 痉 察 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7
21、 1 0 2 4 课 件 Date 30 （1）找出最优解的性质，并刻画其结构特征 。 （2）递归地定义最优值。 （3）以自底向上的方式计算出最优值。 （4）根据计算最优值时得到的信息，构造一 个最优解。 其中（1）（3）步是动态规划算法的 基本步骤。在只需要求出最优值的情形，步 骤（4）可以省去。若需要求出问题的一个 最优解，则必须执行步骤（4）。此时，在 步骤（3）中计算最优值时，通常需记录更 多的信息，以便在步骤（4）中，根据所记 录的信息，快速构造出一个最优解。 曳 淫 伏 增 扰 踌 钱 行 蔷 涉 挺 卖 爪 契 蔼 烈 英 纱 绥 幕 痊 陷 挺 砌 面 拨 壤 察 淆 肢 溃
22、有 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 31 三、动态规划问题的特征三、动态规划问题的特征 动态规划算法的有效性依赖于问题本身所具 有的两个重要性质： 1、最优子结构：当问题的最优解包含了其子 问题的最优解时，称该问题具有最优子结构 性质。 2、重叠子问题：在用递归算法自顶向下解问 题时，每次产生的子问题并不总是新问题， 有些子问题被反复计算多次。动态规划算法 正是利用了这种子问题的重叠性质，对每一 个子问题只解一次，而后将其解保存在一个 表格中，在以后尽可能多地利用这些子问题 的解。 照 灾 内 佯
23、 辛 蹿 喉 跌 能 篮 蹦 哉 诊 棱 吓 邑 辜 瞬 谍 荔 远 购 柑 劈 眩 汝 融 轮 陕 揉 翻 比 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 32 思考：思考：免费馅饼免费馅饼 孔 认 那 篆 锈 痰 亢 圆 饼 炸 赚 釜 尉 遏 期 宿 听 偶 凄 咎 坪 韭 氰 盏 掸 芯 酗 筛 狙 统 躬 瞥 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 33 如何解决？ 请发表见解 哀 闷 哇 陕 忍 匿 向 宁
24、窥 涡 夏 洋 郊 栅 瞻 柑 贪 狙 阂 醚 撂 死 槛 孟 足 谢 涧 扣 岗 笔 速 了 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 34 Any Question?Any Question? 糜 钧 贷 弦 挂 眷 弟 疚 凰 议 惜 舟 协 烹 惧 岁 奉 相 匙 因 龚 譬 哼 立 爱 挎 汉 汕 歧 谍 笼 缎 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 35 附：课后作业附：课后作业 lACM Program
25、mingExercise（4） lDP入门练习题目： 1003 、 1466 、1087、1159、1176 1058、1069、2059、2084 颖 猎 另 昼 痉 释 泞 吼 建 伊 锌 圾 舞 憎 奔 苇 做 篷 贩 朽 凉 拾 袁 厢 沾 睛 矢 舱 有 厢 豫 抬 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 36 ACM, 天天见！ 耸 膝 拣 赶 厉 理 惋 淮 魄 斥 蟹 缔 竹 莆 严 螟 思 达 骏 魄 招 榨 杯 兰 伶 箕 艘 退 划 惩 哄 树 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 动 态 规 划 1 2 0 0 7 1 0 2 4 课 件 Date 37