第4章 贪心算法.ppt

1 第4章贪心算法 2 学习要点理解贪心算法的概念 掌握贪心算法的基本要素 1 最优子结构性质 2 贪心选择性质理解贪心算法与动态规划算法的差异理解贪心算法的一般理论通过应用范例学习贪心设计策略 1 活动安排问题 2 最优装载问题 3 哈夫曼编码 4 单源最短路径 5 最小生成树 6 多机调度问题 3 一个找硬币的例子 假设有四种硬币 二角五分 一角 五分和一分 现要找给顾客六角三分 显然 会拿出2个二角五分 1个一角和3个一分的硬币交给顾客 贪心方法思路 首先选出一个面值不超过六角三分的最大硬币 即二角五分 然后在剩余数中再选最大面值的硬币 依此类推 得到其解 4 若硬币面值改为 一角一分 五分和一分 而要找给顾客一角五分钱 用贪心算法将找给1个一角一分和4个一分的硬币 然而 3个五分硬币是最好的找法 此时 贪心算法没有得到整体最优解 但通常可得到最优解的很好近似 5 贪心算法总是作出在当前看来最好的选择 贪心算法并不从整体最优考虑 它所作出的选择只是在某种意义上的局部最优选择 希望贪心算法得到的最终结果也是整体最优的 虽然贪心算法不能对所有问题都得到整体最优解 但对许多问题它能产生整体最优解 在一些情况下 即使贪心算法不能得到整体最优解 其最终结果却是最优解的很好近似 6 贪心算法的一般框架 GreedyAlgorithm parameters 初始化 重复执行以下的操作 选择当前可以选择的最优解 将所选择的当前解加入到问题的解中去 直至满足问题求解的结束条件 7 4 1活动安排问题 活动安排问题 在所给的活动集合中选出最大的相容活动子集合 该问题要求高效地安排一系列争用某一公共资源的活动 贪心算法使得尽可能多的活动能兼容地使用公共资源 8 设有n个活动的集合E 1 2 n 其中每个活动都要求使用同一资源 如演讲会场等 而在同一时间内只有一个活动能使用这一资源 每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi 且si fi 如果选择了活动i 则它在 si fi 内占用资源 若 si fi 与 sj fj 不相交 则称活动i与j是相容的 即当si fj或sj fi时 活动i与活动j相容 活动安排问题就是求E的最大相容活动子集 9 活动安排问题的描述 用数组A分别存放所有活动的起始时间 结束时间以及是否予以安排的标记 某项活动结束时间愈早 安排其它活动的剩余区间愈大 贪心策略为尽量选择结束时间早的活动来安排 为此 将数组中的活动按结束时间的非减顺序排序 即f1 f2 fn 显然排序需要的时间为O nlogn 10 templatevoidGreedySelector intn Types Typef boolA A 1 true intj 1 for inti 2 i f j A i true j i elseA i false 活动安排问题的贪心算法GreedySelector 各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列 11 由于输入的活动以其完成时间的非减序排列 所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中 算法贪心选择的意义是使剩余的可安排时间段极大化 以便安排尽可能多的相容活动 当输入的活动已按结束时间的非减序排列 算法只需O n 的时间安排n个活动 使最多的活动能相容地使用公共资源 如果所给出的活动未按非减序排列 可以用O nlogn 的时间重排 12 例 设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下 13 4 1活动安排问题 算法greedySelector的计算过程如左图所示 图中每行相应于算法的一次迭代 阴影长条表示的活动是已选入集合A的活动 而空白长条表示的活动是当前正在检查相容性的活动 时间 14 若被检查的活动i的开始时间si小于最近选择的活动j的结束时间fi 则不选择活动i 否则选择活动i加入集合A中 贪心算法并不总能求得问题的整体最优解 但对于活动安排问题 greedySelector却总能求得整体的最优解 即它最终所确定的相容活动集合A的规模最大 这个结论可以用数学归纳法证明 15 贪心算法也能获得最优解 设活动集合E 1 2 n 已经按结束时间的非减顺序排列 活动1具有最早结束时间 首先 必定有一个最优解包含活动1 不然设A E是最优解且A中最早结束的活动是k 若k 1 则最优解包含活动1 若k 1 则活动1必与A中除k以外的活动相容 令B A k 1 则B也是一个最优解 其次 若A是原问题的包含活动1的最优解 则A A 1 是活动集合E i E si f1 的一个最优解 不然设B 是E 的解且 B A 则B 1 是E的解且 B 1 A 此与A是最优解矛盾 对贪心选择次数用数学归纳法即知 贪心算法最终产生原问题的最优解 16 4 2贪心算法的基本要素 考察用贪心算法求解的问题的一般特征对于一个具体问题 怎么知道是否可用贪心算法解此问题 以及能否得到问题的最优解呢 这个问题很难给予肯定的回答 从许多用贪心算法求解的问题中看到 这类问题一般具有2个重要性质 贪心选择性质和最优子结构性质 17 4 2 1 贪心选择性质 贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择 即贪心选择 来达到 这是贪心算法可行的第一个基本要素 也是贪心算法与动态规划算法的主要区别 动态规划算法通常以自底向上的方式解各子问题贪心算法则通常以自顶向下的方式进行 以迭代方式作出相继的贪心选择 每作一次贪心选择就将所求问题简化为规模更小的子问题 对具体问题 要确定它是否具有贪心选择性质 必须证明每一步所作的贪心选择最终导致问题的整体最优解 18 当一个问题的最优解包含其子问题的最优解时 称此问题具有最优子结构性质 问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征 4 2 2 最优子结构性质 19 共同点 贪心算法和动态规划算法都要求问题具有最优子结构性质 具有最优子结构的问题应该选用贪心算法 还是动态规划算法求解 是否能用动态规划算法求解的问题也能用贪心算法求解 下面研究2个经典的组合优化问题 并以此说明贪心算法与动态规划算法的主要差别 4 2 3 贪心算法与动态规划算法的差异 20 4 2 3 贪心算法与动态规划算法的差异 0 1背包问题 给定n种物品和一个背包 物品i的重量是wi 其价值为vi 背包的容量为c 应如何选择装入背包的物品 使得装入背包中物品的总价值最大 在选择装入背包的物品时 对每种物品i只有2种选择 即装入背包或不装入背包 不能将物品i装入背包多次 也不能只装入部分的物品i 21 4 2 3 贪心算法与动态规划算法的差异 背包问题 与0 1背包问题类似 所不同的是在选择物品i装入背包时 可以选择物品i的一部分 而不一定要全部装入背包 1 i n 这2类问题都具有最优子结构性质 极为相似 但背包问题可以用贪心算法求解 而0 1背包问题却不能用贪心算法求解 22 计算每种物品单位重量的价值vi wi依贪心选择策略 将尽可能多的单位重量价值最高的物品装入背包 若将这种物品全部装入背包后 背包内的物品总重量未超过C 则选择单位重量价值次高的物品并尽可能多地装入背包 依此策略一直地进行下去 直到背包装满为止 具体算法可描述如下 用贪心算法解背包问题的基本步骤 23 4 2 3 贪心算法与动态规划算法的差异 voidKnapsack intn floatM floatv floatw floatx Sort n v w inti for i 1 ic break x i 1 c w i if i n x i c w i 算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序 因此 算法的计算时间上界为O nlogn 为了证明算法的正确性 还必须证明背包问题具有贪心选择性质 24 0 1背包问题不适用贪心算法 背包容量为50kg 物品1 2和3的容量和价值分别为 10kg 60 20kg 100 和 30kg 120 单位重量价值最高的为物品1 6 kg 但是依照贪心算法首选物品1却不能获得最优解 物品1 物品2 物品1 物品3 物品2 物品3 总价值为 160 空余20kg 总价值为 180 空余10kg 总价值为 220 没有空余 25 对于0 1背包问题 贪心选择之所以不能得到最优解 是因为在这种情况下 无法保证最终能将背包装满 部分闲置的背包空间使每公斤背包空间的价值降低了 在考虑0 1背包问题时 应比较选择该物品和不选择该物品所导致的最终方案 然后再作出最好选择 由此导出许多互相重叠的子问题 这正是该问题可用动态规划算法求解的另一重要特征 26 贪心选择与最优子结构 满足贪心选择性质必满足最优子结构性质 若原问题E的最优解A是经过有限次贪心选择后获得的 则必定包含了贪心选择1 实际上在选择了贪心选择1后 就将原问题分解为子问题E 和E 贪心选择1显然是E 的最优解 而A 1 必定是E 的最优解 否则将导出A不是最优解的矛盾 因此原问题的最优解是由子问题的最优解组成的 用归纳法可证明其后的贪心选择同样保持最优子结构性质 但是满足最优子结构性质却未必满足贪心选择性质 因为原问题E尽管满足最优子结构性质 即它的最优解A是由两个子问题的最优解B1和B2所构成的 但B1和B2都不是用贪心选择可以做出的 例如在矩阵连乘积问题中 m i j mini k j m i k m k 1 j pi 1pkpj 这个断点k就不是用贪心选择可以做出来的 因此能够应用动态规划法的不一定能够应用贪心算法 虽然能够应用贪心算法一定能够应用动态规划法 但是一般来说 贪心算法的效率高于动态规划法 因而还是应用贪心算法 27 4 3最优装载 有一批集装箱 要装上一艘载重量为c的轮船 其中集装箱i的重量为wi 最优装载问题要求确定在装载体积不受限制的情况下 将尽可能多的集装箱装上轮船 算法描述最优装载问题可用贪心算法求解 采用重量最轻者先装的贪心选择策略 可产生最优装载问题的最优解 28 4 3最优装载 TemplatevoidLoading intx Typew Typec intn int t newint n 1 Sort w t n for inti 1 i n i x i 0 for inti 1 i n 29 2 贪心选择性质设集装箱已按其重量由小到大排序 x1 x2 xn 是最优装载问题的一个最优解 令若给定最优装载问题有解 则1 k n 1 当k 1时 x1 x2 xn 是一个满足贪心选择性质的最优解 2 当k 1时 取y1 1 yk 0 yi xi 1 i n i k 则故 y1 y2 yn 是所给最优装载问题的一个可行解 而由 y1 y2 yn x1 x2 xn 知 y1 y2 yn 是一个满足贪心选择性质的最优解 最优装载问题具有贪心选择性质 x1 0 xk 1 30 3 最优子结构性质若 x1 x2 xn 是最优装载问题的一个满足贪心选择性质的最优解 则有x1 1 x2 xn 是轮船载重量为c w1且待装集装箱为 2 3 n 时 相应最优装载问题的一个最优解 最优装载问题具有最优子结构性质 由最优装载问题的贪心选择性质和最优子结构性质 容易证明算法loading的正确性 算法loading的主要计算量在于将集装箱依其重量从小到大排序 故算法所需的计算时间为O nlogn 31 4 4电脑里的数据压缩 哈夫曼编码 第一 可以节省空间 第二 可以减少对带宽的占用 如果没有数据压缩技术 没法用WinRAR为Email中的附件瘦身 数码录音笔就只能记录不到20分钟的语音 从Internet上下载一部电影要花太长的时间 32 严格意义上的数据压缩起源于人们对概率的认识当对文字信息进行编码时 如果为出现概率较高的字母赋予较短的编码 为出现概率较低的字母赋予较长的编码 总的编码长度就能缩短不少 远在计算机出现之前 著名的Morse 摩尔斯式 电码就已经成功地实践了这一准则 在Morse码表中 每个字母都对应于一个唯一的点划组合 出现概率最高的字母e被编码为一个点 而出现概率较低的字母z则被编码为 显然 这可以有效缩短最终的电码长度 33 设计具体的压缩算法的过程通常更像是一场数学游戏 要寻找一种能尽量精确地统计或估计信息中符号出现概率的方法还要设计一套用最短的代码 描述每个符号的编码规则统计学知识对于前一项工作相当有效 已经陆续实现了静态模型 半静态模型 自适应模型 Markov模型 部分匹配预测模型等概率统计模型 相对而言 编码方法的发展历程更为曲折一些 34 第一个实用的编码方法是由D A Huffman在1952年的论文 最小冗余度代码的构造方法 AMethodfortheConstructionofMinimumRedundancyCodes 中提出的 Huffman编码在计算机界是如此著名 以至于连编码的发明过程本身也成了人们津津乐道的话题 直到今天 许多 数据结构 教材 在讨论二叉树时 仍要提及这种称为Huffman编码的方法 35 Huffman编码效率高 运算速度快 实现方式灵活 从20世纪60年代至今 在数据压缩领域得到了广泛的应用 早期UNIX系统上 一个不太为现代人熟知的压缩程序COMPACT 实际就是Huffman0阶自适应编码的具体实现 在许多知名的压缩工具和压缩算法 如WinRAR gzip和JPEG 中 都有Huffman编码的身影 然而 Huffman编码所得的编码长度 只是对信息熵计算结果的一种近似 还无法真正逼近信息熵的极限 现代压缩技术通常只将Huffman视作最终的编码手段 而非数据压缩算法的全部 36 字符编码问题 1 编码和解码数据压缩过程称为编码 即将文件中的每个字符均转换为一个惟一的二进制位串 数据解压过程称为解码 即将二进制位串转换为对应的字符 2 等长编码方案和变长编码方案给定的字符集C 可能存在多种编码方案 37 字符编码问题 字符abcdef频度 单位 千次 4513121695定长编码000001010011100101变长编码010110011111011100 设待压缩的数据文件共有100000个字符 这些字符均取自字符集C a b c d e f 其中每个字符在文件中出现的次数 简称频度 如下表 等长编码方案将给定字符集C中每个字符的码长定为 log C C 表示字符集的大小 等长编码需要3位二进制数字来表示六个字符 因此 整个文件的编码长度为300000位 38 变长编码方案将频度高的字符编码设置短 将频度低的字符编码设置较长 根据计算公式 45 1 13 3 12 3 16 3 9 4 5 4 1000 224000整个文件被编码为224000位 比定长编码方式节约了约25 的存储空间 前缀码方案对字符集进行编码时 要求字符集中任一字符的编码都不是其它字符编码的前缀 这种编码称为前缀 编 码 等长编码是前缀码 39 最优前缀码平均码长或文件总长最小的前缀编码称为最优的前缀码 最优的前缀码对文件的压缩效果亦最佳 其中 pi为第i个字符的频率li为码长 40 译码需要方便地取出编码的前缀 需要前缀码合适的数据结构 二叉树 BinaryTree 树叶代表给定的字符 每个字符的前缀码是从树根到代表该字符的树叶的一条道路 代码中0 1分别作为指示某结点的左儿子和右儿子的 路标 最优前缀码的二叉树总是一棵完全二叉树 41 树的路径长度定义为 树中每个结点的路径长度之和 结点的路径长度定义为 从根结点到该结点的路径上分支的数目 一棵树上两个结点间的路径 从一个结点到另一个结点之间所有的分支构成路径 42 A B C D E F G H I D到H的路径DGHD到H路径的长为2 A到H的路径ADGHA到H路径的长为3 树的路径长度 1 1 1 2 2 2 3 3 15 n个结点的二叉树路径长度最小的是完全二叉树 43 二叉树带权路径的长 A B C D E F G H I 每个叶子结点都带权的二叉树叫带权二叉树 7 5 2 4 叶结点C的权为7 根结点A到C走7次的路径长度称为A到C的带权路径的长 根到每个叶的带权路径的长的总和叫二叉树的带权路径的长 本树带权路径的长 7 3 5 2 2 3 4 3 49 带权路径的长WPL wklk k 1 n 44 n个叶结点 权分别为w1 w2 wn的二叉树中带权路径长度WPL最小的二叉树叫HuffmanTree最优二叉树也叫赫夫曼树哈夫曼树 霍夫曼树 5 2 7 4 5 2 7 4 WPL 49 WPL 7 5 2 4 2 36 45 5 2 4 7 5 2 4 7 WPL 36 WPL 7 5 2 2 3 4 3 35 哈夫曼树 46 哈夫曼编码 哈夫曼提出构造最优前缀码的贪心算法 贪心策略与最优二叉树 哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T 算法以 C 个叶结点开始 执行 C 1次的 合并 运算后 产生最终所要求的树T 47 哈夫曼算法 1 根据给定的权值 w1 w2 wn 构造n个二叉树F T1 T2 Tn 每个Ti只有一个根结点 权为wi 2 在F中选取两棵根结点的权值最小的树构成一棵新的二叉树 其根的权值为左右子树根的权值的和 3 F中删去这两棵树 加上新得的树 4 重复2 3 直到只剩一棵树 48 1 贪心选择性质 设C是编码字符集 C中字符c的频率为f c 设x y是C中具有最小频率的两个字符 则存在C的最优前缀码 使x y具有相同码长且仅有最后一位编码不同 证明 思路 设二叉树T是C的任意一个最优前缀码 只需要证明对T作适当的修改后得到一新的二叉树T 使得新树中x y是最深叶子且为兄弟 同时新树T 表示的前缀码也是C的一个最优前缀码 哈夫曼算法的正确性 49 设b c是T中最深叶子且为兄弟 设f b f c f x f y 则f x f b f y f c 在T中交换b x的位置得到T 继续在T 交换c y的位置得到T 50 首先 树T T 的前缀码的平均码长之差为 同样 可以证明 c与y不变 相减抵消 51 由于T是C的一个最优前缀码 故 新树T 表示的前缀码也是C的一个最优前缀码 x y是最深叶子且为兄弟 x y具有相同码长且仅有最后一位编码不同 52 2最优子结构性质 设T是表示C的一个最优前缀码的完全二叉树 C中字符c的频率为f c 设x y是T中两个叶子结点且为兄弟 z为它们的父结点 若将z看作是具有频率f x f y 的字符 则树T T x y 表示字符集C C x y z 的一个最优前缀码 证明 先证T的平均码长B T 可用T 的平均码长B T 表示 53 由 式和 式两端相加得 54 若T 表示的C 前缀码不是最优的 则存在T 表示的C 的最优前缀码 T B T z作为C 中的一个字符 故z作为T 中的一个叶子 若将x y加入T 中 作为z的儿子结点 得到表示C的前缀码的二叉树T 与 最优矛盾 T 表示的C 的前缀码是最优的 满足最优子结构性质 55 哈夫曼编码的实现 算法huffmanTree中 编码字符集中c的频率是f c 以f为键值的优先队列Q用在贪心选择时 有效地确定算法当前要合并的2棵具有最小频率的树 一旦2棵具有最小频率的树合并后 产生一棵新树 频率为其合并频率之和 并将新树插入优先队列Q 经过n 1次的合并后 优先队列中只剩下一棵树 即所要求的树T 初始化Q需要O n 计算时间 由于最小堆的removeMin和put运算均需O logn 时间 n 1次的合并总共需要O nlogn 计算时间 n个字符的哈夫曼算法的计算时间为O nlogn 56 4 5单源最短路径 给定一个图G V E 其中每条边的权是一个非负实数 另外给定V中的一个顶点v 称为源 问题 求从源v到所有其它各个顶点的最短路径 单源最短路径问题的贪心选择策略 选择从源v出发目前用最短的路径所到达的顶点 这就是目前的局部最优解 57 单源最短路径的贪心算法 基本思想 设置一个集合S 初始时S中仅含有源v 然后不断地用贪心选择来扩充这个集合 直至S包含所有V中顶点 把从源到u中间只经过S中顶点的路称为从源到u的特殊路径 用dist u 来记录当前顶点u所对应的最短特殊路径长度 贪心选择 每次找到最小的dist u 将u添加到S中 同时对数组dist 作必要的修改 58 Dijkstra算法 1972年E W Dijkstra 美Burroughs公司 获图灵奖 求最短路径的Dijkstra算法 哲学家晚餐 PV操作 同步 死锁 结构化程序设计 goto有害 等P操作和V操作是不可中断的程序段 称为原语 结构化程序设计 它的主要观点是采用自顶向下 逐步求精的程序设计方法 使用三种基本控制结构构造程序 任何程序都可由顺序 选择 重复三种基本控制结构构造 结构化程序设计曾被称为软件发展中的第三个里程碑 59 该方法的要点是 1 没有GOTO语句 2 一个入口 一个出口 3 自顶向下 逐步求精的分解 4 主程序员组 其中 1 2 是解决程序结构规范化问题 3 是解决将大划小 将难化简的求解方法问题 4 是解决软件开发的人员组织结构问题 60 Dijkstra 迪杰斯特拉 算法思想 由近到远逐步计算 每次最近的顶点的距离就是它的最短路径长度 再从这个最近者出发 即依据最近者修订到各顶点的距离 然后再选出新的最近者 如此走下去 直到所有顶点都走到 61 Dijkstra算法 Procedure 1 S 1 初始化S 2 fori 2tondo 初始化D 3 dist i C 1 i C i j 表示边 i j 的权 初始时为源到顶点i的一步距离 4 fori 1ton 1do 5 从V S中选取一个顶点u使得dist u 最小 6 将u加入到S中 将新的最近者加入S 7 for w V Sdo 依据最近者u修订dist w 8 dist w min dist w dist u C u w 62 Dijkstra算法举例 迭代Sudis 2 dis 3 dis 4 dis 5 初始 1 10 301001 1 2 21060301002 1 2 4 4105030903 1 2 4 3 3105030604 1 2 4 3 5 510503060 加权图G 由数组dis i 可知 从顶点1到顶点2 3 4 5的最短通路的长度分别为10 50 30和60 63 Dijkstra算法的计算复杂性 Dijkstra算法有两层循环 外层循环为n次 内层有两个循环 一个是选出最小的u 第5行 另一个是修订dis w 第7 8行 它们的次数都是n 2 所以内层循环的时间为O n Dijkstra算法的时间复杂度为O n2 Dijkstra算法能求出从源到其它各顶点的最短通路的长度 但是却并没有给出其最短通路 可借助prev数组得到 64 Dijkstra算法的正确性 算法的贪心选择 若u是V S中具有最短特殊路径的顶点 就将u选入S 并确定了从源到u的最短路径长度dist u i e 下一条最短路径是中间只经过S中顶点而最后到达u的路径 为什么从源到u没有更短的路径呢 若有 则如下图所示 若该路径经S外一点x到达u 则 dist x d x u dist u 从而dist x dist u 这与u的选取矛盾 类似可证最优子结构性质 65 4 6最小生成树 设G V E 是一个无向连通带权图 即一个网络 E的每条边 v w 的权为c v w 如果G的一个子图G 是一棵包含G的所有顶点的树 则称G 为G的生成树 生成树的各边权的总和称为该生成树的耗费 在G的所有生成树中 耗费最小的生成树称为G的最小生成树MST minimumspanningtree 66 树的基本性质 连通无回路的图G称为树 树是点比边多一的连通图 G连通且q p 1 树是点比边多一的无回路图 G无回路且q p 1 树若加条边就有回路 G无回路 但对任意的u v V G 若uv E G 则G uv中恰有一条回路 树若减条边就不连通 G连通 但对 e E G G e不连通 n个顶点的连通图的生成树含有n 1条边 67 最小生成树的贪心选择性质 令G中权最小的边为e1 必定有图G的一棵最小生成树包含了e1 若G的任何最小生成树都不包含e1 设T为G的最小生成树 e1 T 于是T e1是一个有回路的图且该回路中包含e1 该回路中必有条不是e1的边ei 令T T e1 ei T 也是G的生成树 又c T c T c e1 c ei c e1 c ei 从而c T c T T 是G的最小生成树且含有边e1 矛盾 故必定有图G的最小生成树包含了e1 选定第一条边e1以后 该如何选择第二条边呢 依据各条边的权重 依次选出权重较轻的n 1条边 这n 1条边必定包括了G的n个顶点 这样就得到了G的一棵最小生成树 这样做是否可以呢 不行 因为不能保证这n 1条边构成树 要保证这n 1条边构成树 必须使这n 1条边是连通的或者是无回路的 Prim算法的做法 在保证连通的前提下依次选出权重较小的n 1条边 在实现中体现为n个顶点的选择 Kruskal算法的做法 在保证无回路的前提下依次选择权重较小的n 1条边 68 Prim算法 基本思想 在保证连通的前提下依次选出权重较小的n 1条边 G V E 为无向连通带权图 令V 1 2 n 设置一个集合S 初始化S 1 T 贪心策略 如果V S中的顶点j与S中的某个点i连接 且 i j 是E中的权重最小的边 则选择j 将j加入S 并将 i j 加入T中 重复执行贪心策略 直至V S为空 69 Prim算法中的数据结构 图用连接矩阵C i j 给出 即C i j 为结点i到结点j的权重 为了有效地找出V S中满足与S中的某个点i连接且 i j 权重最小的顶点j 对其中的每个顶点j设立两个数组closest j 和lowcost j closest j 是S中与j最近的顶点 closest j j 即为选中的边 而lowcost j 是相应边的权 70 Prim算法的实现 Prim intn Type c 初始化 结点1放入S 并初始化lowcost 和closest 执行以下操作n 1次 依据lowcost 找出与S最近的点j并放入S 调整lowcost 和closest intj 1 s j true for inti 2 i n i closest i 1 lowcost i c 1 i s i false for inti 1 i n i Typemin inf for intk 2 k n k if lowcost k min s中仅加入了一个新成员j 因此只需要依据结点j调整lowcost 和closest for intk 2 k n k if c j k lowcost k closest k j 71 Prim算法的示例 给定一个连通带权图如下 1 2 3 4 5 6 1 6 5 5 5 3 6 6 2 4 初始时S 1 T 1 第一次选择 1 3 权最小 S 1 3 T 1 3 3 第二次选择 3 6 权最小 S 1 3 6 T 1 3 3 6 6 第三次选择 6 4 权最小 S 1 3 6 4 T 1 3 3 6 6 4 4 第四次选择 2 3 权最小 S 1 3 6 4 2 T 1 3 3 6 6 4 2 3 2 第五次选择 5 2 权最小 S 1 3 6 4 2 5 T 1 3 3 6 6 4 3 2 2 5 5 72 Kruskal算法 基本思想 在保证无回路的前提下依次选出权重较小的n 1条边 贪心策略 如果 i j 是E中尚未被选中的边中权重最小的 并且 i j 不会与已经选择的边构成回路 于是就选择 i j 问题 如何知道 i j 不会造成回路 若边 i j 的两个端点i和j属于同一个连通分支 则选择 i j 会造成回路 反之则不会造成回路 为此初始时将图的n个顶点看成n个孤立分支 将所有的边按权由小到大排序 并依边权递增顺序检查每一条边 73 Kruskal算法的数据结构 数组e 表示图的边 e i u e i v 和e i w 分别表示边i的两个端点及其权重 函数Sort e w 将数组e按权重w从小到大排序 一个连通分支中的顶点表示为一个集合 函数Initialize n 将每个顶点初始化为一个集合 函数Find u 给出顶点u所在的集合 函数Union a b 给出集合a和集合b的并集 重载算符 判断集合的不相等 74 Kruskal算法的实现 Kruskal intn e Sort e w 将边按权重从小到大排序initialize n 初始时每个顶点为一个集合k 1 k累计已选边的数目 j 1 j为所选的边在e中的序号while k n 选择n 1条边 a Find e j u b Find e j v 找出第j条边两个端点所在的集合if a b t k j Union a b 若不同 第j条边放入树中并合并这两个集合j 继续考察下一条边 75 Kruskal算法的例子 1 2 3 4 5 6 1 6 5 5 5 3 6 6 2 4 初始时为6个孤立点 1 2 3 4 5 6 选择了边1 于是1 3点合并为同一个集合 选择了边2 于是4 6点合并为同一个集合 选择了边3 于是2 5点合并为同一个集合 选择了边4 于是1 3 4 6点合并为同一个集合 考察边5 因为1 4点属于同一个集合 被放弃 选择边6 于是1 3 4 6 2 5点属于同一个集合 已经选择边了n 1条边 算法结束 结果如图所示 u v w 76 Prim与Kruskal算法复杂性 Prim算法为两重循环 外层循环为n次 内层循环为O n 因此其复杂性为O n2 Kruskal算法中 设边数为e 则边排序的时间为O eloge 确定边的时间为O loge 所以整个时间复杂性为O eloge 当e n2 e n2 时 Kruskal算法要比Prim算法差 当e O n2 e n2 时 Kruskal算法比Prim算法好得多 77 最小生成树 破圈法 管梅谷算法 1975年 我国管梅谷教授算法思想 1 先从图G任取一个圈 并从圈中去掉一条权最大的边 若在同一圈中有几条都是权最大边 则任选其中一边去掉 2 在余下的子圈中 重复上述步骤 直至没有圈止 1 2 3 4 5 6 1 6 5 5 5 3 6 6 2 4 1 2 3 4 5 6 78 管梅谷教授上海市人 1957年毕业于华东师范大学数学系 1957年至1990年在山东师范大学工作 33年 1984年至1990年担任山东师范大学校长1990年至1995年任复旦大学运筹学系主任1995年至今任澳大利亚皇家墨尔本理工大学交通研究中心高级研究员 国际项目办公室高级顾问及复旦大学管理学院兼职教授 79 4 7多机调度问题 多机调度问题要求给出一种作业调度方案 使所给的n个独立作业 在尽可能短的时间内 由m台相同的机器加工处理完成 这个问题是NP完全问题 到目前为止还没有有效的解法 对于这一类问题 用贪心选择策略有时可以设计出较好的近似算法 约定 每个作业均可在任何一台机器上加工处理 但未完工前不允许中断处理 作业不能拆分成更小的子作业 80 采用最长处理时间作业优先的贪心选择策略 可以设计出解多机调度问题的较好近似算法 当n m时 只要将机器i的 0 ti 时间区间分配给作业i即可 算法只需要O 1 时间 当n m时 将n个作业依其所需的处理时间从大到小排序 再依此顺序将作业分配给空闲的处理机 算法所需的计算时间为O nlogn 81 例如 设7个独立作业 1 2 3 4 5 6 7 由3台机器M1 M2和M3加工处理 各作业所需的处理时间分别为 2 14 4 16 6 5 3 按算法greedy产生的作业调度如下图所示 所需的加工时间为17 82 4 8贪心算法的理论基础 借助于拟阵工具 可建立关于贪心算法的较一般的理论 这个理论对确定何时使用贪心算法可以得到问题的整体最优解十分有用 1 拟阵拟阵M定义为满足下面3个条件的有序对 S I 1 S是非空有限集 2 I是S的一类具有遗传性质的独立子集族 即若B I 则B是S的独立子集 且B的任意子集也都是S的独立子集 空集 必为I的成员 3 I满足交换性质 即若A I B I且 A B 则存在某一元素x B A 使得A x I 83 4 8贪心算法的理论基础 例如 设S是一给定矩阵中行向量的集合 I是S的线性独立子集族 则由线性空间理论容易证明 S I 是一拟阵 拟阵的另一个例子是无向图G V E 的图拟阵 给定拟阵M S I 对于I中的独立子集A I 若S有一元素x A 使得将x加入A后仍保持独立性 即A x I 则称x为A的可扩展元素 当拟阵M中的独立子集A没有可扩展元素时 称A为极大独立子集 84 4 8贪心算法的理论基础 下面的关于极大独立子集的性质是很有用的 定理4 1 拟阵M中所有极大独立子集大小相同 这个定理可以用反证法证明 若对拟阵M S I 中的S指定权函数W 使得对于任意x S 有W x 0 则称拟阵M为带权拟阵 依此权函数 S的任一子集A的权定义为 85 2 关于带权拟阵的贪心算法许多可以用贪心算法求解的问题可以表示为求带权拟阵的最大权独立子集问题 给定带权拟阵M S I 确定S的独立子集A I使得W A 达到最大 这种使W A 最大的独立子集A称为拟阵M的最优子集 由于S中任一元素x的权W x 是正的 因此 最优子集也一定是极大独立子集 86 4 8贪心算法的理论基础 例如 在最小生成树问题可以表示为确定带权拟阵的最优子集问题 求带权拟阵的最优子集A的算法可用于解最小生成树问题 下面给出求带权拟阵最优子集的贪心算法 该算法以具有正权函数W的带权拟阵M S I 作为输入 经计算后输出M的最优子集A 87 4 8贪心算法的理论基础 Setgreedy M W A 将S中元素依权值W 大者优先 组成优先队列 while S S removeMax x if A x I A A x returnA 算法greedy的计算时间复杂性为 88 4 8贪心算法的理论基础 引理4 2 拟阵的贪心选择性质 设M S I 是具有权函数W的带权拟阵 且S中元素依权值从大到小排列 又设x S是S中第一个使得 x 是独立子集的元素 则存在S的最优子集A使得x A 算法greedy在以贪心选择构造最优子集A时 首次选入集合A中的元素x是单元素独立集中具有最大权的元素 此时可能已经舍弃了S中部分元素 可以证明这些被舍弃的元素不可能用于构造最优子集 89 4 8贪心算法的理论基础 引理4 3设M S I 是拟阵 若S中元素x不是空集 的可扩展元素 则x也不可能是S中任一独立子集A的可扩展元素 引理4 4 拟阵的最优子结构性质 设x是求带权拟阵M S I 的最优子集的贪心算法greedy所选择的S中的第一个元素 那么 原问题可简化为求带权拟阵M S I 的最优子集问题 其中 S y y S且 x y I I B B S x 且B x I M 的权函数是M的权函数在S 上的限制 称M 为M关于元素x的收缩 90 4 8贪心算法的理论基础 定理4 5 带权拟阵贪心算法的正确性 设M S I 是具有权函数W的带权拟阵 算法greedy返回M的最优子集 3 任务时间表问题给定一个单位时间任务的有限集S 关于S的一个时间表用于描述S中单位时间任务的执行次序 时间表中第1个任务从时间0开始执行直至时间1结束 第2个任务从时间1开始执行至时间2结束 第n个任务从时间n 1开始执行直至时间n结束 91 4 8贪心算法的理论基础 具有截止时间和误时惩罚的单位时间任务时间表问题可描述如下 1 n个单位时间任务的集合S 1 2 n 2 任务i的截止时间 1 i n 1 n 即要求任务i在时间之前结束 3 任务i的误时惩罚 1 i n 即任务i未在时间之前结束将招致的惩罚 若按时完成则无惩罚 任务时间表问题要求确定S的一个时间表 最优时间表 使得总误时惩罚达到最小 92 4 8贪心算法的理论基础 这个问题看上去很复杂 然而借助于拟阵 可