[工学]《算法设计与分析》第4讲.ppt

第4章 贪心法 4.1 贪心算法概述 4.1.1什么是贪心法 贪心法（greedy approach）是一种极为直接的算法设计技术，可应用于多种问题的求解。 因此，贪心法(Greedy algorithm)是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是最好或最优的算法。 最优化问题（optimization problems）是指这样一类问题，问题给定某些约束条件（constraint），满足这些约束条件的问题解称为可行解（feasible solution）。通常满足约束条件的解不是惟一的。为了衡量可行解的好坏，问题还给出了某个数值函数，称为目标函数（objective function），使目标函数取最大（或最小）值的可行解称为最优解（optimal solution）。 最优量度标准 最优子结构 4.2 背包问题 问题描述 贪心法求解 算法正确性 4.3 磁带最优存储 4.3.1 单磁带最优存储 4.3.2 多带最优存储 4.4 作业调度 问题描述 贪心法求解 4.5 启发式算法 用贪心法解决了一些问题并得到了最优解。 但是，贪心法并不总是产生最优解。事实上，有很多问题，要得到它们的最优解是很困难的。 此时，启发式算法可以提供一种新的设计思路。当一个问题的最优解算法的复杂度很高时，如果利用某种办法产生的算法能很快地得到较好的解（或称为次优解、满意解），可能就相当满意了。 例: 货郎担问题（TSP问题） 给定一个带有权值的连通有向图（或无向图），以及它的邻接矩阵，称此邻接矩阵为权矩阵。希望在该图中寻找一条闭合回路，使得回路经过每一个图顶点，且回路中各边的权之和最小，称这样的一条闭合回路为最小周游路线。 4.6 贪心法的理论基础 借助于拟阵工具，可建立关于贪心算法的较一般的理论。这个理论对确定何时使用贪心算法可以得到问题的整体最优解十分有用。 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。 例如，设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为极大独立子集。 下面的关于极大独立子集的性质是很有用的。 定理4.1：拟阵M中所有极大独立子集大小相同。 这个定理可以用反证法证明。 若对拟阵M=(S,I)中的S指定权函数W，使得对于任意x? S，有W(x)0，则称拟阵M为带权拟阵。依此权函数，S的任一子集A的权定义为 。 2、关于带权拟阵的贪心算法 许多可以用贪心算法求解的问题可以表示为求带权拟阵的最大权独立子集问题。 给定带权拟阵M=(S,I)，确定S的独立子集A?I使得W(A)达到最大。这种使W(A)最大的独立子集A称为拟阵M的最优子集。由于S中任一元素x的权W(x)是正的，因此，最优子集也一定是极大独立子集。 例如，在最小生成树问题可以表示为确定带权拟阵 的最优子集问题。求带权拟阵的最优子集A的算法可用于解最小生成树问题。 下面给出求带权拟阵最优子集的贪心算法。该算法以具有正权函数W的带权拟阵M=(S,I)作为输入，经计算后输出M的最优子集A。 Set greedy (M,W) {A=?; 将S中元素依权值W（大者优先）组成优先队列； while (S!=?) { S.removeMax(x); if (A∪{x}?I) A=A∪{x}; } return A } 算法greedy的计算时间复杂为 。 引理4.2(拟阵的贪心选择性质) 设M=(S,I)是具有权函数W的带权拟阵，且S中元素依权值从大到小排列。又设x? S是S中第一个使得{x}是独立子集的元素，则存在S的最优子集A使得x? A。 算法greedy在以贪心选择构造最优子集A时，首次选入集合A中的元素x是单元素独立集中具有最大权的元素。此时可能已经舍弃了S中部分元素。可以证明这些被舍弃的元素