数据结构-第五部分.pptVIP

1 第15章算法设计技术 枚举法贪婪法分而治之法动态规划回溯法随机算法 介绍通用的算法设计模式 2 枚举法 枚举法适合于解的候选者是有限 可枚举的场合 枚举法就是对可能是解的众多候选者按某种顺序进行逐一枚举和检验 从中找出符合要求的候选解作为问题的解 基于枚举法的算法一般都比较直观 容易理解 但由于要检查所有的候选解 因此时间性能较差 3 枚举法实例 用50元钱买了三种水果 西瓜 苹果和桔子 各种水果加起来一共100个 假如 西瓜5元一个 苹果1元一个 桔子1元3个 设计一算法输出每种水果各买了几个 4 约束条件 三种水果一共100个 买三种水果一共花了50元 如果西瓜有mellon个 苹果有apple个 桔子有orange个 那么 mellon apple orange等于1005 mellon 1 apple orange 3等于50 5 直观的枚举 For mellon 1 mellon 99 mellon For apple 1 apple 99 apple For orange 1 orange 99 orange If mellon apple orange等于100并且5 mellon 1 apple orange 3等于50 输出此方案 列出所有的情况 检查是否满足两个约束条件 6 改进的方案 intmain intmellon apple orange for mellon 1 mellon 10 mellon for apple 1 apple 50 5 mellon apple orange 3 50 5 mellon apple if mellon apple orange 100 cout mellon mellon cout apple apple cout orange orange endl return0 按一个约束条件列出所有可行的情况 然后对每个可能解检查它是否满足第二个约束条件 7 执行结果 Mellon 1apple 18orange 81Mellon 2apple 11orange 87Mellon 3apple 4orange 93 8 第15章算法设计技术 枚举法贪婪法分而治之法动态规划回溯法随机算法 介绍通用的算法设计模式 9 贪婪法 贪婪法适合于分阶段完成的工作 在每一阶段都选择当前最好的答案 而不管将来如何 Dijkstra算法 prim算法和Kruskal算法都是贪婪算法贪婪法不一定能得到最优解 但是一个可行的 较好的解 10 最少背包问题 假设有许多盒子 每个盒子能保存的总重量为1 0 有N个项i1 i2 iN 它们的重量分别是w1 w2 wN 目的是用尽可能少的盒子放入所有的项 任何盒子的重量不能超过他的容量 例如 如果项的重量为0 4 0 4 0 6和0 6 最佳的方案是用两个盒子 但要得到最佳方案 必须尝试所有种组合情况 当n很大时 这是不可能的 一种解决方案使用贪婪法 11 解决策略 按给定的次序扫描每一个项 把每一个项放入能够容纳他而不至于溢出的最满的盒子 如果项的重量为0 4 0 4 0 6和0 6 贪婪法的方案是用三个盒子 其装载的重量分别为0 8 0 6 0 6 12 第15章算法设计技术 枚举法贪婪法分而治之法动态规划回溯法随机算法 介绍通用的算法设计模式 13 分而治之法 分而治之法的思想分 递归解决若干个较小的问题治 从子问题的答案中形成原始问题的解分治法的的算法至少有两个递归调用已见过的分治法算法 快速排序 树的遍历 14 分治法实例 最长连续子序列问题最近点问题数学计算问题 15 最长连续子序列问题 假设输入是 4 3 5 2 1 2 6 2 我们把这个输入划分成两部分 前四个和后四个 这样最大连续子序列的和可能出现在下面三种情况中 情况1 整个位于前半部 可递归计算 情况2 整个位于后半部 可递归计算 情况3 从前半部开始但在后半部结束 16 情况3的解决方法 从两半部分的边界开始 通过从右到左的扫描来找到左半段的最长序列 类似地 从左到右的扫描找到右半段的最长序列 把这两个子序列组合起来 形成跨越分割边界的最大连续子序列 在这个实例中 结果序列是从第一部分的第一个元素到第二部分的其余元素 总和是两个子序列的和 即4 7 11 17 算法总结 递归地计算整个位于前半部的最大连续子序列 递归地计算整个位于后半部的最大连续子序列 通过两个连续循环 计算从前半部开始但在后半部结束的最大连续子序列的和 选择三个和中的最大值 18 IntmaxSum inta intleft intright intmaxLeft maxRight center intleftSum 0 rightSum 0 intmaxLeftTmp NEGMAX maxRightTmp NEGMAX center left right 2 if left right returna left 0 a left 0 maxLeft maxSum a left center maxRight maxSum a center 1 right 19 for inti center i left i leftSum a i if leftSum maxLeftTmp maxLeftTmp leftSum for inti center 1 imaxRightTmp maxRightTmp rightSum returnmax3 maxLeft maxRight maxLeftTmp maxRightTmp 20 分治法实例 最长连续子序列问题最近点问题数学计算问题 21 最近点问题 在二维平面上有N个点 试找出距离最短的两个点 蛮力算法 计算两两之间的距离 从中找出最小的一个 N个点有N N 1 2对距离 因此时间复杂度为O N2 22 分治法解法 将所有的点按x值排序 取一个合适的x值 把所有点分成两半PL和PR 距离最近的两个点可能出现在PL中 dL 也可能出现在PR dR 中 也可能一个点在PL 一个点在PR dC dL和dR可用递归得到dC的计算 设 min dL dR 如果dC比 大 则没必要计算 因此用于计算dC的点必须落在分界线 的范围内 计算此范围中点对的距离中的最小值 23 24 优化 在最坏的情况下 所有的点都落在分界线 以内 但此时不一定要计算所有点对的距离 只要两点的y坐标大于 这两点之间的距离也不用算了 假设该区间中的点按y坐标排序 则可得下列算法 25 for i 0 i break elseif dist pj pj 1 dist pj pj 1 26 分治法实例 最长连续子序列问题最近点问题数学计算问题 27 数学计算问题 设X和Y是两个N位的整数 假如一位乘法花费一个单位时间 那么计算X Y的时间复杂性为O N2 分治法计算将X和Y均分成两半 分别称为XL XR YL YR 则X XL10N 2 XR Y YL10N 2 YR 那么 XY XLYL10N XLYR XRYL 10N 2 XRYR时间复杂度 T N 4T N 2 O N O N2 28 进一步改进 上述算法的问题是需要太多次 4次 的递归调用 如果能减少递归调用 则能提高时间性能注意 XLYR XRYL XL XR YR YL XLYL XRYR代入前式 XY XLYL10N XLYR XRYL 10N 2 XRYR XLYL10N XL XR YR YL XLYL XRYR 10N 2 XRYR可见只需3次递归调用时间复杂性 29 第15章算法设计技术 枚举法贪婪法分而治之法动态规划回溯法随机算法 介绍通用的算法设计模式 30 动态规划 用表代替递归例 斐波那契函数f n f n 1 f n 2 计算f n 需要计算f n 1 和f n 2 当计算f n 1 时要计算f n 2 和f n 3 因此在计算f n 中f n 2 被计算了两次 为了减少重复的递归调用 我们可以反过来计算 先计算f 2 有了f 2 再计算f 3 以此类推 计算到f n 在此过程中不需要任何递归 31 动态规划 硬币找零问题最优二叉查找树 32 找零问题 对于一种货币 有面值为C1 C2 CN 分 的硬币 最少需要多少个硬币来找出K分钱的零钱 33 贪婪法解法 我们不断使用可能的最大面值的硬币如 美元的硬币有1 5 10和25分的面值 忽略流通频率很低的50分硬币 我们可以通过使用2个25分 一个10分的硬币以及三个1分来找出63分钱 一共是6个硬币 如果美元中包含一个21分硬币时 贪心算法仍然给出一个用六个硬币的解 但是最佳的解是用三个硬币 三个都是21分的硬币 34 解法1 分治法 如果我们可以用一个硬币找零 这就是最小的 否则 对于每个可能的值i 我们可以独立计算找i分钱零钱和K i分钱需要的最小硬币数 然后选择这个和最小的i 35 怎样找出63分钱零钱 找出1分钱零钱和62分钱零钱分别需要的硬币数是1和4 因此 63分钱需要使用五个硬币 找出2分钱和61分钱分别需要2和4个硬币 一共是六个硬币 我们继续尝试所有的可能性 我们看到一个21分和42分的分解 它可以分别用一个和两个硬币来找开 因此 这个找零问题就可以用三个硬币解决 我们需要尝试的最后一种分解是31分和32分 我们可以用两个硬币找出31分零钱 用三个硬币找出32分零钱 一共是五个硬币 因此最小值是三个硬币 36 intcoin intk inti tmp intcoinNum k if 能用一个硬币找零 return1 for i 1 i k i if tmp coin i coin k i coinNum coinNum tmp returncoinNum 37 上述解法分析 此算法的效率很低事实上63分钱找零的问题是不会在一个合理的时间内解决的 就如Finbonacci函数一样 38 解法2 通过指定其中的一个硬币来递归地简化问题 例如 对于63分钱 我们可以给出以下找零的办法 一个1分的硬币加上递归地分派62分钱一个5分的硬币加上递归地分派58分钱一个10分的硬币加上递归地分派53分钱一个21分的硬币加上递归地分派42分钱一个25分的硬币加上递归地分派38分钱该算法的问题仍然是效率问题 39 动态规划解 效率低下主要是由于重复计算造成的 因此 可把已有子问题的答案存放起来 当再次遇到此子问题时就不用重复计算了 在本例中 我们用coinsUsed i 代表了找i分零钱所需的最小硬币数 40 算法思想 先找出一分钱的找零方法 把最小硬币数存入coinUsed 1 依次找出2分钱 3分钱 的找零方法 知道到达要找零的钱为止 对每个要找的零钱i 可以把i分解成某个coins j 和i coins j 所需硬币数为coinUsed i coins j 1 对所有的j 取最小的coinUsed i coins j 1作为i元钱找零的的答案 41 函数原型 Voidmakechange intcoins intdifferentCoins intmaxChange intcoinUsed Coins存放所有不同的硬币值 不同的硬币个数为differentCoins maxChange为要找的零钱数 42 voidmakechange intcoins intdifferentCoins intmaxChange intcoinUsed coinUsed 0 0 for intcents 1 centscents continue if coinUsed cents coins j 1 minCoins minCoins coinUsed cents coins j 1 coinUsed cents minCoins 43 动态规划 硬币找零问题最优二叉查找树 44 最优二叉查找树 有一组词w1 w2 wN 他们的出现概率分别为p1 p2 pN 构建一棵二叉排序树使得访问时间的期望值最小 即如果wi所在的层次是di 那么该问题类似于哈夫曼树 概率大的靠近根 概率小的远离根 但它比哈夫曼树更复杂 因为它还要满足二叉排序树的特性 45 贪婪法的解法 选择出现概率最大的词作为树根 把剩余的词分成两组 小于根的和大于根的 递归构建左子树和右子树 显然不是最优的 代价为 2 43 46 最优解法 假如要对wleft到wright构建一棵最优二叉排序树 那么这棵树的形式一定是根为wi 左子树的节点为left到i 1 右子树的节点为i 1到right 左子树和右子树也是最优的设Cleft right是树的代价 那么 47 最优解法 对a am and egg if the two对所有的可能的情况计算它的代价 从中找出最小的 根为a 左子树为空 右子树为am two 根为am 左子树为a 右子树为and two 根为and 左子树为a am 右子树为egg two 根为egg 左子树为a am and 右子树为if two 在上述每一种情况中 我们需要继续递归 如 在尝试根为egg 左子树为a am and 右子树为if two的情况时 要找出最优的左子树 我们又要尝试根节点为a 左子树为空 右子树为am和and根节点为am 左子树为a 右子树为and根节点为and 左子树为a和am 右子树为空 48 动态规划解法 从上述分析可以看出 在找出由a到two组成的最优树时 由a组成的树 由a和am组成的树 由am和and组成的树 会分别被计算很多次 解决方法 从小到大计算由n个节点组成的最优树 并把它保存在一个表中 当所有的节点形成了一棵树时 任务就完成了 每棵树的保存用两个信息 根和代价 49 生成过程 先生成由一个节点组成的树 树的代价就是节点的权值 保存这些树和相应的代价 生成所有由两个节点组成的树 将第一个节点作为根 第二个节点作为右子树 计算代价 将第二个节点作为根 第一个节点作为右子树 计算代价 取代价小的树作为最终的树保存下来 生成由三个节点组成的树 四个节点组成的树 50 i 1i 2i 3i 4i 5i 6i 7 51 第15章算法设计技术 枚举法贪婪法分而治之法动态规划回溯法随机算法 介绍通用的算法设计模式 52 第15章算法设计技术 枚举法贪婪法分而治之法动态规划回溯法随机算法 介绍通用的算法设计模式 53 回溯法 八皇后问题分书问题 首先暂时放弃问题规模大小的限制 并将问题的候选解按某种顺序逐一枚举和检验 当发现候选解不可能是解时 就选择下一候选解 如果当前候选解除了不满足规模要求外 满足其他所有要求时 继续扩大当前候选解的规模 并继续试探 如果当前的候选解满足包括问题规模在内的所有要求时 该候选解就是问题的一个解 54 八皇后问题 在一个8 8的棋盘上放8个皇后 使8个皇后中没有两个以上的皇后会在同一行 同一列或同一对角线上 55 八皇后问题的求解过程 求解过程从空配置开始 在第一列到第m列为合理配置的基础上再配置m 1列 直到第n列的配置也时合理时 就找到了一个解 另外在一列上也有n种配置 开始时配置在第一行 以后改变时 顺序选择第二行 第三行 第n行 当配置到第n行时还找不到一个合理的配置时 就要回朔 去改变前一列的配置 56 算法 m 0 从空配置开始 good true 配置中的皇后不冲突 do if good if m 8 输出解 重新寻找下一可行的解 else向前试探 扩展至下一列 else回朔 形成下一候选解 good 检查当前候选解的合理性 while m 0 57 棋盘的数据结构的设计 比较直观的方法是采用一个二维数组 但仔细考察 就会发现 这种表示方法给调整候选解及检查其合理性会带来困难 对于本题来说 我们关心的并不是皇后的具体位置 而是 一个皇后是否已经在某行和某条斜线合理地安置好了 因为在每一列上恰好放一个皇后 所以引入一个一维数组 设为col 9 值col j 表示在棋盘第j列上的皇后位置 如col 3 的值为4 就表示第三列的皇后在第四行 另外 为了使程序在找完了全部解后回溯到最初位置 设定col 0 的初值为0 当回溯到第0列时 说明程序已求得全部解 或无解 结束程序执行 58 候选解的合理性检查 引入以下三个工作数组数组a 9 a A true表示第A行上还没有皇后 数组b 16 b A true表示第A条右高左低斜线上没有皇后 从左上角依次编到右下角 1 15 数组c 16 c A true表示第A条左高右低斜线上没有皇后 从左下角依次编到右上角 1 15 59 voidqueen a11 intk 在8x8棋盘的第k列上找合理的配置 inti j charawn for i 1 i awn if awn Q awn q exit 0 elsequeen a11 k 1 递归至第k十1列a i b k i 1 c 8 k i true 恢复对应位置无皇后 60 主程序 intcol 9 boola 9 b 17 c 17 intmain intj for j 0 j 8 j a j true for j 0 j 16 j b j c j true queen a11 1 return0 61 回溯法 八皇后问题分书问题 首先暂时放弃问题规模大小的限制 并将问题的候选解按某种顺序逐一枚举和检验 当发现候选解不可能是解时 就选择下一候选解 如果当前候选解除了不满足规模要求外 满足其他所有要求时 继续扩大当前候选解的规模 并继续试探 如果当前的候选解满足包括问题规模在内的所有要求时 该候选解就是问题的一个解 62 分书问题 有编号为0 1 2 3 4的5本书 准备分给5个人A B C D E 每个人的阅读兴趣用一个二维数组描述 Like i j truei喜欢书jLike i j falsei不喜欢书j写一个程序 输出所有皆大欢喜的分书方案 63 存储设计 用一个二维数组like存储用户的兴趣用一个一维的整型数组take表示某本书分给了某人 Take j i表示第j本书给了第i个人 64 解题思路 依次尝试把书j分给人i 如果第i个人不喜欢第j本书 则尝试下一本书 如果喜欢 并且第j本书尚未分配 则把书j分配给i 如果i是最后一个人 则方案数加1 输出该方案 否则调用try i 1 为第i 1个人分书 回溯 让第i个人退回书j 尝试下一个j 即寻找下一个可行的方案由于在每次try中都要用到like take以及目前找到的方案数n 因此可将它们作为全局变量 以免每次函数调用时都要带一大串参数 设计一个函数try i 给第i个人分书 65 voidtrynext inti intj k for j 0 j 5 j if like i j 66 当like矩阵的值为 调用trynext 0 的结果为 67 第14章算法设计技术 枚举法贪婪法分而治之法动态规划回溯法随机算法 介绍通用的算法设计模式 68 随机算法 在算法中 至少有一个地方使用随机数作决策 随机算法的时间复杂度取决于选择的随机数随机算法的时间复杂度用期望的运行时间来表示 一般假设随机数的选择是均匀分布的例如 在快速排序中将中间点用随机数来选择 则快速排序成为一个随机算法 可以证明 期望的时间复杂度为O NlogN 69 随机算法实例 跳表素数检测 70 跳表 以O logN 的期望的时间复杂性支持插入和删除的数据结构跳表的概念 支持动态查找必须用链表 但链表查找的时间为N 可以用增加链的方式提高查找效率增加一条链 让头节点指向第二个节点 第二个节点指向第四个节点 第四个节点指向第六个节点 查找时间为再增加一条链 让头节点指向第四个节点 第四个节点指向第八个节点 第八个节点指向第十二个节点 查找时间为推而广之 对于2i N 2i 1个节点 设置i条链 第j条链指向其后的第2j个节点 71 72 查找过程 节点x 首先查找第i条链 如下一节点比x大 则查找第i 1条链 否则继续查找第i条链 依次执行 直到找到或找不到x最坏情况下的时间性能 73 插入过程 当插入一节点时 所有的节点都要变化 为了避免这个变化 插入采用随机算法定义 有k条链的节点称为level k节点在跳表中 level i的节点有N 2i个 即level i的节点出现的概率为1 2i 插入过程 查找到插入点生成一个新节点按概率生成节点的level插入该节点因此跳表并不一定是严格的隔2i个节点有一条第i层的链 而只是从概率上讲符合此分布 74 随机算法实例 跳表素数检测 75 素数检测 方法一 依次检测1到N能否被N整除 如果能被整除的数的个数等于2 则N是素数 时间复杂度为O N 方法二 依次检测2 3 5 7到sqrt N 只要有一个能整除N 则N为非素数 最坏情况的时间复杂度O N1 2 上述两方法对小素数适合 大素数不适合方法三 随机算法 该算法能保证 当声称是非素数时 100 为非素数 当声称是素数时 有