• / 115
  • 下载费用:25 金币  

算法设计与分析_王红梅 第二版 第6章动态规划PPT课件

关 键 词:
算法设计与分析_王红梅第二版第6章动态规划PPT课件
资源描述:
Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial 第6章 动态规划 Dynamic Programming 算法设计与分析算法设计与分析 本科本科生课程生课程 Design and Analysis of AlgorithmDesign and Analysis of Algorithm 海南大学信息科学技术学院 College of Information Science and Technology Hainan University Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial 2 2 教学重点动态规划法的设计思想 各种经典问题的动态规划思想 教学难点多阶段决策过程 最优性原理 各种经典问题的动态规划思想 教学内容及目 标 知识点教学要求 了解理解掌握熟练掌握 多阶段决策过程 动态规划法的设计思想 多段图的最短路径问题 多源点最短路径问题 TSP问题 最长递增子序列问题 最长公共子序列问题 0 1背包问题 最优二叉查找树 近似串匹配问题 学习目标 Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming 3 3 本章要点 6 1 概 述 6 2 图问题中的动态规划法 6 3 组合问题中的动态规划法 6 4 查找问题中的动态规划法 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming 4 4 6 1 概 述 n动态规划 n在1950年代由美国数学家贝尔曼为研究最优控 制问题而提出的概念 n它是一种求解多阶段决策最优化问题的工具 n与分治法的关系 n动态规划法也将待求解问题分解成若干子问题 但各问题间往往不是独立的 n分治法对子问题的重叠部分要被重复计算多次 n动态规划法将每个子问题只求解一次并保存在 表中 下次查表获得解 免去重复计算 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming 5 5 n 最优化问题 有 n 个输入 它的解由这 n 个输入的一个子集组成 这个子集必须满足某些事先给定的条件 这些条 件称为约束条件 满足约束条件的解称为问题的可 行解 满足约束条件的可行解可能不只一个 为了 衡量这些可行解的优劣 事先给出一定的标准 这 些标准通常以函数的形式给出 这些标准函数称为 目标函数 使目标函数取得极值 极大或极小 的 可行解称为最优解 这类问题就称为最优化问题 6 1 1 多阶段决策过程 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming 8 8 最优性原理 n对于一个具有n个输入的最优化问题 其求解过程往往可以 划分为若干个阶段 每一阶段的决策仅依赖于前一阶段的状态 由决策所采取的动作使状态发生转移 成为下一阶段决策的 依据 n从而 一个决策序列在不断变化的状态中产生 这个决策序 列产生的过程称为多阶段决策过程 A P1 P2 P7 动态规划的决策过程 BCDE P3 P4 P5 P6 初始状态 最终状态 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming 9 9 多阶段决策过程满足最优性原理 Optimal Principle 无论决策过程的初始状态和初始决策是 什么 其余的决策都必须相对于初始决策所产生的 当前状态 构成一个最优决策序列 各子问题的解 只与它前面的子问题的解相关 而且各子问题的解 都是相对于当前状态的最优解 整个问题的最优解 是由各个子问题的最优解构成 如果一个问题满足最优性原理通常称此问题具 有最优子结构性质 最优性原理 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming1010 动态规划法的设计思想 动态规划法将待求解问题分解成若干个相互重叠 的子问题 每个子问题对应决策过程的一个阶段 一般来说 子问题的重叠关系表现在对给定问题求 解的递推关系 也就是动态规划函数 中 将子问 题的解求解一次并填入表中 当需要再次求解此子 问题时 可以通过查表获得该子问题的解而不用再 次求解 从而避免了大量重复计算 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming1111 原问题的解 原问题 填 表 子问题1子问题2 子问题n 动态规划法的求解过程 动态规划法的设计思想 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming1212 n求解过程 n动态规划法设计算法一般分成三个阶段 n分段 将原问题分解为若干个相互重叠的子问题 n分析 分析问题是否满足最优性原理 找出动态规划 函数的递推式 n求解 利用递推式自底向上计算 实现动态规划过程 动态规划法的设计思想 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming1313 n 5时分治法计算斐波那契数的过程 F 5 F 4 F 3 F 3 F 2 F 2 F 1 F 2 F 1 F 1 F 0 F 1 F 0 F 1 F 0 例 计算斐波那契数 分治法求解 重复计算 动态规划法的设计思想 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming1414 0123456789 0112358132134 动态规划法求解斐波那契数F 9 的填表过程 注意到 计算F n 是以计算它的两个重叠子问题 F n 1 和F n 2 的形式来表达的 所以 可以设计一张表填入n 1个 F n 的值 填表法 动态规划法的设计思想 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial 一个简单的例子 数塔问题 问题描述 从数塔的顶层出发 在每一个结点可 以选择向左走或向右走 一直走到最底层 要求 找出一条路径 使得路径上的数值和最大 8 12 39 15 6 810512 91018416 第6章 动态规划法Page 15 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial 数塔问题 想法 8 12 39 15 6 810512 91018416 第6章 动态规划法Page 16 想法 从顶层出 发下一层选择 取决于两个4层 数塔的最大数 值和 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial 求解初始子问题 底层的每个数字可看作1层数塔 则最大数值和就是其自身 再求解下一阶段的子问题 第4层的决策是在底层决策的基础上进行求解 可 以看作4个2层数塔 对每个数塔进行求解 再求解下一阶段的子问题 第3层的决策是在第4层决策的基础上进行求解 可以看作3个2层的数塔 对每个数塔进行求解 以此类推 直到最后一个阶段 第1层的决策结果就是数塔问题的整体最优解 数塔问题 想法 第6章 动态规划法Page 17 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial 1 初始化数组maxAdd的最后一行为数塔的底层数据 for j 0 j n j maxAdd n 1 j d n 1 j 2 从第n 1层开始直到第 1 层对下二维数组maxAdd i j 执行下述操作 2 1 maxAdd i j d i j max maxAdd i 1 j maxAdd i 1 j 1 2 2 如果选择下标j的元素 则path i j j 否则path i j j 1 3 输出最大数值和maxAdd 0 0 4 根据path数组确定每一层决策的列下标 输出路径信息 数塔问题 算法 第6章 动态规划法Page 18 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial 数塔问题 算法 第6章 动态规划法Page 19 算法分析 步骤1的时间代价是O n 步骤2进行填表 工作 需填写n 1行 由于数组maxAdd是下三角矩阵 第i行只需填写i个元素 故步骤2的时间代价是 O n2 由于数组path已经记载每个决策的列下标 步骤4只需输出每行的决策结果 时间代价是O n 所以算法的时间复杂性是O n2 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming2020 n那些问题可以用动态规划法求解 n能用动态规划法求解问题所具有的特征 n能够分解为相互重叠的若干子问题 n满足最优性原理 也称最优子结构性质 该问题的 最优解中包含着其子问题的最优解 n分析问题是否满足最优性原理的方法 是用反证法 n先假设由问题的最优解导出的子问题的解不是最优的 n然后再证明在这个假设下可构造出比原问题最优解更 好的解 从而导致矛盾 动态规划法的设计思想 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming2121 本章要点 6 1 概 述 6 2 图问题中的动态规划法 6 3 组合问题中的动态规划法 6 4 查找问题中的动态规划法 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming2222 6 2 图问题中的动态规划法 6 2 3 TSP问题 6 2 1 多段图的最短路径问题 6 2 2 多源点最短路径问题 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming2323 多段图的最短路径问题 多段图的最短路径问题 设图G V E 是一个带权有向连通图 如果把顶点集 合V 划分成k个互不相交的子集Vi 2 k 1 i k 使得E中的任何一条边 u v 必有u Vi v Vi m 1 i k 1 m 则称图G为多段图 称s V1为源点 t Vk为终点 多段图的最短路径问题 是求从源点到终点的最小代价路径 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming2424 2 1 20 3 4 5 6 7 8 9 4 9 3 8 7 6 8 4 7 5 6 8 6 6 5 3 7 一 个 多 段 图 n划分顶点子集 将顶点划分为 k 个互不相交的子集 所以 多段图划分为 k段 每一段包含顶点的一个子集 n顶点编号 将顶点集合V中的所有顶点按照段的顺序进行编号 子集中的 顶点互不邻接 段内顶点间相互顺序无关紧要 n设顶点数为n 源点s的编号为0 终点t 的编号为n 1 对E中的任何一条边 u v 顶点u 的编号小于顶点 v 的编号 多段图的最短路径问题 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming2525 n下图是多段图吗 多段图的最短路径问题 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming2626 设s s1 s2 sp t是从s到t的一条最短路径 从源点s开 始 设从s到下一段的顶点s1已经求出 则问题转化为求从 s1到t的最短路径 显然s1 s2 sp t一定构成一条从s1到t的 最短路径 如若不然 设s1 r1 r2 rq t是一条从s1到t的 最短路径 则s s1 r1 r2 rq t将是一条从s到t的路径且比 s s1 s2 sp t的路径长度要短 从而导致矛盾 所以 多 段图的最短路径问题满足最优性原理 证明多段图问题满足最优性原理 多段图的最短路径问题 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming2727 多段图的决策过程 多段图的边 u v 用cuv 表边的权值 从源点s到终点t的最短路 径记为d s t 则从源点0到终点9的最短路径d 0 9 由下式确定 d 0 9 min c01 d 1 9 c02 d 2 9 c03 d 3 9 上面是最后阶段的决策 它又依赖于d 1 9 d 2 9 和d 3 9 其中 d 1 9 min c14 d 4 9 c15 d 5 9 d 2 9 min c24 d 4 9 c25 d 5 9 c26 d 6 9 d 3 9 min c35 d 5 9 c36 d 6 9 这一阶段的决策又依赖于d 4 9 d 5 9 和d 6 9 多段图的最短路径问题 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming2828 d 4 9 min c47 d 7 9 c48 d 8 9 d 5 9 min c57 d 7 9 c58 d 8 9 d 6 9 min c67 d 7 9 c68 d 8 9 这一阶段的决策依赖d 7 9 和d 8 9 而d 7 9 和d 8 9 可以直 接获得 d 7 9 c79 7 7 9 d 8 9 c89 3 8 9 再向前推导 有 d 6 9 min c67 d 7 9 c68 d 8 9 min 6 7 5 3 8 6 8 d 5 9 min c57 d 7 9 c58 d 8 9 min 8 7 6 3 9 5 8 d 4 9 min c47 d 7 9 c48 d 8 9 min 5 7 6 3 9 4 8 多段图的最短路径问题 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming2929 d 3 9 min c35 d 5 9 c36 d 6 9 min 4 9 7 8 13 3 5 d 2 9 min c24 d 4 9 c25 d 5 9 c26 d 6 9 min 6 9 7 9 8 8 15 2 4 d 1 9 min c14 d 4 9 c15 d 5 9 min 9 9 8 9 17 1 5 d 0 9 min c01 d 1 9 c02 d 2 9 c03 d 3 9 min 4 17 2 15 3 13 16 0 3 最后 得到最短路径为0 3 5 8 9 长度为16 多段图的最短路径问题 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming3030 多段图的最短路径问题的填表过程 l前提条件 u设数组cost n 作为存储子问题解的表格 cost i 表示从顶点i 到终 点t 的最短路径或最小花费 u设数组path n path i 存放从顶点i 到终点t 的最小花费路径上顶点i 的下一个顶点编号 u设设数组组route i 用于存放最短路径顶顶点子集 l填表过程 n第一阶段 确定第k 1段的所有顶点到达终点t 的花费最小的通路 n第二阶段 用第一阶段的信息 确定第k 2段的所有顶点到达终点t 的花费最小的通路 n如此依次进行 直到最后确定源点s到达终点t 的花费最小的通路 多段图的最短路径问题 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming3131 n最后 从源点s的path信息中 确定它的前方顶点编号p1 n从p1的path信息中 确定p1的前方顶点编号p2 n如此递推 直到终点t 动态规划函数为 cost i min cij cost j i j n 且顶点j i是邻接点 式6 7 path i 取 min cij cost j 的 j 式6 8 多段图的最短路径问题 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming3232 n步骤 1 对所有的i 0 i0 继续计算 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming3535 多段图的最短路径问题 最短路径 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming3636 多段图的最短路径问题 计算最短路径顶点集route n i 0 i i 1 If route i 0 i 2 1 对顶点i 的每一个邻接点j 根据式6 7计算cost i 2 2 根据式6 8计算path i 3 输出最短路径长度cost 0 4 计算route i 并输出最短路径经过的顶点 4 1 i 0 4 2 循环直到route i n 1 输出route i path route i 1 多段图的最短路径问题 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming4040 算法6 2主要由三部分组成 n第一部分是初始化部分 其时间性能为O n n第二部分是依次计算各个顶点到终点的最短路径 由两层嵌套的 循环组成 外层循环执行n 1次 内层循环对所有出边进行计算 并且在所有循环中 每条出边只计算一次 假定图的边数为m 则 这部分的时间性能是 O m n第三部分是输出最短路径经过的顶点 设多段图划分为k段 其时 间性能是O k 如忽略第一部分 算法6 2的时间复杂性为O m k 多段图的最短路径问题 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming4141 6 2 2 多源点最短路径问题 问题 给定带权有向图G V E 对任意顶点vi和vj i j 求顶点vi 和vj的最短路径长度 想法 设d vi vj V 是从顶点vi到vj经过顶点集合V的最短路径长度 初始子问题 d vi vj 即vi到vj弧 若不存在则为 下个子问题 d vi vj v0 取vi vj和vi v0 vj较短者 下个子问题 d vi vj v0 v1 取d vi vj v0 和vi v1 vj较短者 d vi vj v0 vk min d vi vj v0 vk 1 d vi vk v0 vk 1 d vk vj v0 vk 1 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming4242 6 2 2 多源点最短路径问题 动态规划函数 0 i j n 1 d vi vj cij d vi vj v0 vk min d vi vj v0 vk 1 d vi vk v0 vk 1 d vk vj v0 vk 1 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming4343 6 2 2 多源点最短路径问题 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming4444 6 2 2 多源点最短路径问题 算法实现 设图G V E 中顶点的编号为 0 1 n 1 有向边上的 权值存储在代价矩阵arc n n 中 数组dist n n 存放在迭代过程 中求得的最短路径长度 初始为图的邻接矩阵 在迭代过程中 根据如下递推关系式进行迭代 dist 1 i j arc i j distk i j min distk 1 i j distk 1 i k distk 1 k j 0 k n 1 distk i j 是从顶点vi到vj经过顶点集合 v0 vk 的最短路径长度 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming4545 6 2 2 多源点最短路径问题 const int n 10 void floyd int arc n n int dist n n int i j k for i 0 i n i 初始化矩阵dist for j 0 j n j dist i j arc i j for k 0 k n k 进行n次迭代 for i 0 i n i for j 0 j n j if dist i k dist k j dist i j dist i j dist i k dist k j Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming4646 6 2 2 多源点最短路径问题 算法分析 Floyd算法的基本语句是比较操作dist i k dist k j dist i j 设图中有n个顶点 三层嵌套的循环实现对二维数组dist迭代 n次 其时间复杂性是O n3 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming4747 TSP问题 TSP问题问题 是指旅行家要旅行n个城市 要求各个城市经历经历 且仅经历仅经历 一次然后回到出发发城市 并要求所走的路程最短 也 就是在有向带权图带权图 G 中 寻寻找路径最短的哈密尔问题问题 设设4个城市间间的距离可以用代价矩阵阵来表示 C 3 6 7 5 2 3 6 4 2 3 7 5 带权图的代价矩阵 Cij 1 2 3 4 1 2 3 4 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming4848 设s s1 s2 sp s是从s出发的一条路径长度最短 的简单回路 假设从s到下一个城市s1已经求出 则 问题转化为求从s1到s的最短路径 显然s1 s2 sp s 一定构成一条从s1到s的最短路径 如若不然 设s1 r1 r2 rq s是一条从s1到s的 最短路径且经过n 1个不同城市 则s s1 r1 r2 rq s 将是一条从s出发的路径长度最短的简单回路且比s s1 s2 sp s要短 从而导致矛盾 所以 TSP问题 满足最优性原理 首先证明 TSP 问题满足最优性原理 TSP问题 Five weeks of practice ended in this way and my feelings can only be summed up in eight words although hard but very substantial Chapter 6 Dynamic ProgrammingChapter 6 Dynamic Programming4949 解TSP问题的过程描述如下 设从i出发 V V i 令d i V 表示从顶点i 出发 经过V 中各个顶点一次 且仅一次 最终回到顶点i的最短路径长度 d k 从顶点k出发 回到i点的最短路径长度 d k V k 从k出发 经过V k 的点 回到i的最短路径长度 则TSP的动态规划函数为 d i V i d i V min cik d k V k k V 式6 5 d k cki k i 式6 6 TSP问题 从城市0出发经城市1 2 3然后
展开阅读全文
  麦档网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:算法设计与分析_王红梅 第二版 第6章动态规划PPT课件
链接地址:https://www.maidoc.com/p-16696677.html

当前资源信息

范文库

编号: 20181015151747903243

类型: 共享资源

格式: PPT

大小: 2.33MB

上传时间: 2020-05-23

关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

[email protected] 2018-2020 maidoc.com版权所有  文库上传用户QQ群:3303921 

麦档网为“文档C2C模式”,即用户上传的文档所得金币直接给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的金币归上传人(含作者)所有。
备案号:蜀ICP备17040478号-3  
川公网安备:51019002001290号 

本站提供办公文档学习资料考试资料文档下载


收起
展开