C语言 动态规划ppt课件.ppt

2020 4 7 1 第十章动态规划 用递推代替递归用空间换时间 2020 4 7 2 10 1什么是动态规划 1 最短路径问题2 数塔问题 2020 4 7 3 下图表示城市之间的交通路网 线段上的数字表示费用 单向通行由A E 试用动态规划的最优化原理求出A E的最省费用 1最短距离问题 2020 4 7 4 如图从A到E共分为4个阶段 即第一阶段从A到B 第二阶段从B到C 第三阶段从C到D 第四阶段从D到E 除起点A和终点E外 其它各点既是上一阶段的终点又是下一阶段的起点 例如从A到B的第一阶段中 A为起点 终点有B1 B2两个 因而这时走的路线有两个选择 一是走到B1 一是走到B2 若选择B2的决策 B2就是第一阶段在我们决策之下的结果 它既是第一阶段路线的终点 又是第二阶段路线的始点 在第二阶段 再从B2点出发 对于B2点就有一个可供选择的终点集合 C1 C2 C3 若选择由B2走至C2为第二阶段的决策 则C2就是第二阶段的终点 同时又是第三阶段的始点 同理递推下去 可看到各个阶段的决策不同 线路就不同 2020 4 7 5 很明显 当某阶段的起点给定时 它直接影响着后面各阶段的行进路线和整个路线的长短 故此问题的要求是 在各个阶段选取一个恰当的决策 使由这些决策组成的一个决策序列所决定的一条路线 其总路程最短 如何解决这个问题呢 要求在各阶段选取一个恰当的决策 2020 4 7 6 决策过程 1 由目标状态E向前推 可以分成四个阶段 即四个子问题 D EC EB EA E 2 策略 每个阶段到E的最省费用为本阶段的决策路径 用动态规划法求解 2020 4 7 7 3 D1 D2是第一次输入的结点 他们到E都只有一种费用 f D1 5f D2 2 目前无法定下 哪一个点将在全程最优策略的路径上 第二阶段计算中 5 2都应分别参加计算 2020 4 7 8 4 C1 C2 C3是第二次输入结点 他们到D1 D2各有两种费用 此时应计算C1 C2 C3分别到E的最少费用 f C1 min C1D1 f D1 C1D2 f D2 计算结果是f C1 C1D1 f D1 8 D1 同理C2的决策路径计算结果是C2 D2 E f C2 7 同理C3的决策路径计算结果是C3 D2 E f C3 10 2020 4 7 9 5 第三次输入结点为B1 B2 而决策输出结点可能为C1 C2 C3 仿前计算可得Bl B2的决策路径为如下情况 Bl B1C1费用f B1 5 8 13 B2 B2C1费用f B2 6 8 14 2020 4 7 10 6 第四次输入结点为A 决策输出结点可能为B1 B2 同理可得决策路径为A AB2 费用5 14 19此时才正式确定每个子问题的结点中 那一个结点将在最优费用的路径上 子问题的决策中 只对同一城市 结点 比较优劣 而同一阶段的城市 结点 的优劣要由下一个阶段去决定 2020 4 7 11 2 数塔问题 有形如下图所示的数塔 从顶部出发 在每一结点可以选择向左走或是向右走 一直走到底层 要求找出一条路径 使路径上的值最大 2020 4 7 12 用暴力的方法 可以吗 2020 4 7 13 这道题如果用枚举法 暴力思想 在数塔层数稍大的情况下 如31 则需要列举出的路径条数将是一个非常庞大的数目 2 30 1024 3 10 9 10亿 试想一下 2020 4 7 14 拒绝暴力 倡导和谐 2020 4 7 15 从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值 只要左右两道路径上的最大值求出来了才能作出决策 可见 由下层的子问题可以得到上层的子问题 所以 可从底层开始 层层递进 最后得到最大值 结论 自顶向下的分析 自底向上的计算 考虑一下 2020 4 7 16 如果各个子问题不是独立的 不同的子问题的个数只是多项式量级 如果我们能够保存已经解决的子问题的答案 而在需要的时候再找出已求得的答案 这样就可以避免大量的重复计算 由此而来的基本思路是 用一个表记录所有已解决的子问题的答案 不管该问题以后是否被用到 只要它被计算过 就将其结果填入表中 10 2动态规划的基本思想 2020 4 7 17 动态规划的基本步骤 动态规划算法通常用于求解具有某种最优性质的问题 在这类问题中 可能会有许多可行解 每一个解都对应于一个值 我们希望找到具有最优值 最大值或最小值 的那个解 设计一个动态规划算法 通常可以按以下几个步骤进行 2020 4 7 18 1 找出最优解的性质 并刻画其结构特征 2 递归地定义最优值 3 以自底向上的方式计算出最优值 4 根据计算最优值时得到的信息 构造一个最优解 其中 1 3 步是动态规划算法的基本步骤 在只需要求出最优值的情形 步骤 4 可以省去 若需要求出问题的一个最优解 则必须执行步骤 4 此时 在步骤 3 中计算最优值时 通常需记录更多的信息 以便在步骤 4 中 根据所记录的信息 快速构造出一个最优解 基本步骤 2020 4 7 19 动态规划问题的特征 动态规划算法的有效性依赖于问题本身所具有的两个重要性质 1 最优子结构 当问题的最优解包含了其子问题的最优解时 称该问题具有最优子结构性质 2 重叠子问题 在用递归算法自顶向下解问题时 每次产生的子问题并不总是新问题 有些子问题被反复计算多次 动态规划算法正是利用了这种子问题的重叠性质 对每一个子问题只解一次 而后将其解保存在一个表格中 在以后尽可能多地利用这些子问题的解 2020 4 7 20 10 3最长有序子序列 2020 4 7 21 子问题的构造 子问题 求以ak k 1 2 3 N 为终点的最长上升子序列的长度 虽然这个子问题和原问题形式上并不完全一样 但是只要这N个子问题都解决了 那么这N个子问题的解中 最大的那个就是整个问题的解 该子问题可以递推求解 2020 4 7 22 假定MaxLen k 表示以ak做为 终点 的最长上升子序列的长度 那么 MaxLen 1 1MaxLen k Max MaxLen i 1 i k且ai ak且k 1 1 2020 4 7 23 实例 所求最大值是F n 吗 2 2020 4 7 24 10 4最长公共子序列 一个给定序列的子序列是在该序列中删去若干元素后得到的序列 给定两个序列X和Y 当另一序列Z既是X的子序列又是Y的子序列时 称Z是序列X和Y的公共子序列 2020 4 7 25 例如 若X A B C B D B A Y B D C A B A 则序列 B C A 是X和Y的一个公共子序列 但它不是X和Y的一个最长公共子序列 序列 B C B A 也是X和Y的一个公共子序列 它的长度为4 而且它是X和Y的一个最长公共子序列 因为X和Y没有长度大于4的公共子序列 2020 4 7 26 给定2个序列X和Y 当另一序列Z既是X的子序列又是Y的子序列时 称Z是序列X和Y的公共子序列 问题 给定2个序列X x1 x2 xm 和Y y1 y2 yn 找出X和Y的最长公共子序列 最长公共子序列 2020 4 7 27 典型应用 计算两个文本的相似程度生物学上的基因比较 2020 4 7 28 人类基因组计划的研究成果 一个细胞核内的23个染色体含31亿个核苷酸 只有A G T C四种 基因数在3万 3 5万 每个基因有几千个核苷酸 人与人之间有99 99 的基因序列是相同的 2020 4 7 29 生物学家对鉴别人类基因和确定他们的功能很感兴趣 因为这对诊断人类疾病和开发新药很有用 一旦一段基因被确定后 接下来的工作便是确定它的功能 这个工作一般是通过搜索基因数据库来进行的 数据库中存储了很多基因序列及其相应的功能 将返回与新基因序列功能相似的已知序列 生物学家们假设类似的基因表示类似的功能 确定与待研究基因最相近的一个已知基因对生物试验非常必要 2020 4 7 30 那么如何确定两个基因序列的相似性呢 这主要是通过相似性函数来判断的 比如已知两个序列AGTGATG和GTTAG 他们有多相似 一个判断的方法是在两个序列中分别插入若干空格使得两序列的长度相等 AGTGAT G GT TAG这种匹配的函数值是 3 5 5 3 3 5 3 5 8 2020 4 7 31 穷举法 对X的所有子序列 检查它是否也是Y的子序列 从而确定它是否为X和Y的公共子序列 X的所有子序列都检查过后即可求出X和Y的最长公共子序列 X的每个子序列相应于下标集 1 2 m 的一个子集 因此 共有2m个不同子序列 故穷举搜索法需要指数时间 而事实上 最长公共子序列问题具有最优子结构性质 2020 4 7 32 最长公共子序列的结构 首先引入前缀的概念 给定一个序列X x1 x2 xm 对i 1 m定义X的第i个前缀为Xi x1 x2 xi 例如 X A B C B D A B 则X4 A B C B X0为空序列 2020 4 7 33 最长公共子序列的结构 设序列X x1 x2 xm 和Y y1 y2 yn 的最长公共子序列为Z z1 z2 zk 则 1 若xm yn 则zk xm yn 且zk 1是xm 1和yn 1的最长公共子序列 2 若xm yn 则zk xm蕴涵Z是xm 1和Y的最长公共子序列 3 若xm yn 则zk yn蕴涵Z是X和yn 1的最长公共子序列 由此可见 2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列 因此 最长公共子序列问题具有最优子结构性质 如X ABCB Y BDCAB Z BCB 如X ABCBD Y BDCAB Z BCB 如X ABCB Y BDCBA Z BCB 2020 4 7 34 子问题的递归结构 由以上三个性质可知 要X x1 x2 xm 和Y y1 y2 yn 的最长公共子序列 可能要检查如下子问题 若xm yn时 我们就要找出Xm 1和Yn 1的LCS 将xm yn拼接到这个LCS后 就得到Xm和Yn的LCS若xm yn时 我们需要解决两个子问题 找出Xm 1和Yn的LCS 和Xm和Yn 1的LCS 取两者中较长的作为Xm和Yn的LCS 2020 4 7 35 子问题的递归结构 由最长公共子序列问题的最优子结构性质可知 要找出X和Y的最长公共子序列 可按如下方式递归的进行 若xm yn时 LCS Xm Yn LCS Xm 1 Yn 1 xm 若xm yn时 LCS Xm Yn max LCS Xm 1 Yn LCS Xm Yn 1 max LCS Xm 1 Yn 1 LCS Xm 2 Yn max LCS Xm 1 Yn 1 LCS Xm Yn 2 2020 4 7 36 子问题的递归结构 由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系 用c i j 记录序列Xi x1 x2 xi 和Yj y1 y2 yj 的最长公共子序列的长度 由最优子结构性质可建立递归关系如下 2020 4 7 37 计算最优值 由于在所考虑的子问题空间中 总共有 mn 个不同的子问题 因此 用动态规划算法自底向上地计算最优值能提高算法的效率 输入 X x1 x2 xm 和Y y1 y2 yn 输出 数组c c i j 存储Xi x1 x2 xi 和Yj y1 y2 yj 的最长公共子序列的长度 2020 4 7 38 算法 对i 1到m做对j 1到n做若 x i y j c i j c i 1 j 1 1 否则若c i 1 j c i j 1 c i j c i 1 j 否则 c i j c i j 1 LCS Xm Yn LCS Xm Yn xm 2020 4 7 39 例 X ABCBDAB Y BDCABA 0BDCABA 0ABCBDAB A AB ABC ABCB ABCBD ABCBDA ABCBDAB B BD BDC 2020 4 7 40 例 X ABCBDAB Y BDCABA 0BDCABA 0ABCBDAB 2020 4 7 41 voidLCS intm intn char x char y char z int c 不用数组b 构造最优解的非递归算法inti m j n intk c m n 最长公共子序列的长度while i 0 构造最长公共子序列 2020 4 7 42 10 50 1背包问题 给定n种物品和一背包 物品i的重量是wi 其价值为vi 背包的容量为C 问应如何选择装入背包的物品 使得装入背包中物品的总价值最大 目标 使装入背包中物品的总价值最大约束条件 装入的物品总重不得超过C 2020 4 7 43 海盗盗宝问题 海盗有一背包 最大容积为9 现有5件宝物 体积si分别是2 3 4 5和4公斤价值vi分别是3 7 5 9和8请给出装载方案 使背包价值达到最大 C 9 2020 4 7 44 一开始 见物品就装 物品1 2 3全装入 背包装满了 得到背包总价值为15 这是不是最大价值呢 考虑只有前三个物品的情况 2020 4 7 45 物品4该不该装 有两个选择 1 不装 背包价值不变 为15 2 装入 它占去的体积为5 得到价值为9 剩下容积4最多可以装下多大价值 考虑只有前4个物品的情况 2020 4 7 46 这是一个n 3 从前三个物品中选择 容量c 4的子问题 目前最优 装入物品2和物品4 总价值为16 若已知这个子问题的解是 装物品2 得价值为7 2 装入物品4 它占去的体积为5 得到价值为9 剩下容积4最多可以装下多大价值 2020 4 7 47 考虑5个物品的情况 物品5该不该装 1 不装 得到背包价值仍为16 2020 4 7 48 2 若装入物品5 占用体积为4 得价值为8 背包剩余容积为5 如何在前4个物品中选择装入 使背包价值最大化 这是n 4 c 5的一个子问题 若得到该子问题的解为 装入物品1 2 得价值为10 考虑5个物品的情况 目前最优 装入物品5和1 2 总价值为18 16 2020 4 7 49 子问题的构造 当n 1时 只有一个物品 s1 2 v1 3若背包容量c 0 1 则无法装入物品1 得到背包价值为0若背包容量c 2 3 4 5 6 7 8 9则可装入物品1 得到背包价值为3 C 1 0 0C 1 1 0C 1 2 3C 1 3 3C 1 4 3C 1 5 3C 1 6 3C 1 7 3C 1 8 3C 1 9 3 2020 4 7 50 考虑两个物品的情况 当n 2时 有两个物品 s1 2 v1 3 s2 3 v2 7若背包容量c 0 1 得到背包价值为0若背包容量c 2 可装入物品1 得总价值m 2 2 3若背包容量c 3 m 2 3 7 若背包容量c 4 m 2 4 7若背包容量c 5 m 2 5 10 若不装物品2 m 2 3 m 1 3 3若装入物品2 m 2 3 v 2 m 1 3 3 7 0 7 m 2 6 10m 2 7 10m 2 8 10m 2 9 10 若不装物品2 m 2 5 m 1 5 3若装入物品2 m 2 5 v 2 m 1 5 3 7 3 7 2020 4 7 51 递推关系的建立 用m i j 来表示从前i个物品中选取物品装入容量为j的背包所得的最大价值 则要寻求的是m n c m i j 是以下两个值的最大值 1 m i 1 j 即不装入物品i 背包价值与仅考虑前i 1个物品时情况相同 2 v i m i 1 j s i 即装入物品i 再从前i 1个物品中选取 使背包剩余容积j s i 价值最大化 2020 4 7 52 构造价值数组 背包容量j 从前i个物品中选取 2020 4 7 53 背包容量j 从前i个物品中选取 2020 4 7 54 构造最优解