Lecture 11 贪心算法的理论基础-拟阵.pptx

第4章 贪心算法 1 4.8 贪心算法的基础理论 1.拟阵 2.帯权拟阵的贪心算法 3.任务时间表问题 本讲主要内容： 2 4.8 贪心算法的理论基础 借助于拟阵[1]（Matroid）工具，可建立关于贪心算法的较一般的理论。 线性代数中有如下两条性质： （1）如果X＝{x1,x2,…,xk}是一个线性无关向量组，则对X的任意子集X’也是线性无关的。 （2）如果X＝{x1,x2,…,xr}和Y＝{y1,y2,…,ym}是两个线性无关向量组且mr，则必存在一个yi∈Y，使得X∪{yi}是一个线性无关向量组。 1935年，Whitney把以上两条性质进行了抽象推广，提出了拟阵概念。 [1]赖虹建. 拟阵论[M].北京: 高等教育出版社，2002年7月 3 4.8 贪心算法的理论基础 1.拟阵 独立公理集系统将拟阵M定义为满足下面3个条件的有序对(S,I) (1)S是非空有限集。 (2)I是S的一类具有遗传性质的独立[1]子集族，即若BI，则B是S的独立子集，且B的任意子集也都是S的独立子集(即该子集属于I)。空集必为I的成员。 (3)I满足交换性质，即若AI,BI且|A||B|，则存在某一元素xB-A，使得A∪{x}I。 [1]:此处的独立子集是线性无关(或线性独立)概念的推广，代表I的入集条件 4 4.8 贪心算法的理论基础 例1：如非空集合S的子集K的幂集I=ρ(K),(S,I)是否为拟阵？ 例2：无向图G=(V,E)的图拟阵： ，其中SG定义为图G的边集E，IG定义为SG的无循环边集族，AIG 当且仅当A构成图G的森林*。 注*：即IG是图G的无环支撑（生成）子图集合。 支撑子图（生成子图）：包含图G所有顶点的子图。 5 4.8 贪心算法的理论基础 证明： 满足拟阵(S,I)的3个条件。 (1)因为SG为图G的边集，显然非空； (2)由于从SG的一个无循环边集中去掉若干条边不会产生循环，即森林的子集还是森林，因此SG的无循环边集族IG具有遗传性质。 6 4.8 贪心算法的理论基础 (3)设A和B是图G的两个森林，且|B|＞|A|，即B的边比A多。由于图G中有k条边的森林恰由|V|-k棵树组成，因此B中的树比A中的少。很显然，B中至少存在一棵树T，它的顶点分别在森林A的两棵树中。由于T是连通的，故T中必有一条边(u,v)满足u,v分别在A的两棵树中。因此将(u,v)加入A不会产生循环。由此得出IG满足交换性质，即若AI,BI且|A||B|，则存在某一元素xB-A，使得A∪{x}I。 7 4.8 贪心算法的理论基础 2.拟阵的几个重要概念和性质 【定义】：给定拟阵M=(S,I)，对于I中的独立子集A I，若S有一元素x A，使得将x加入A后仍保持独立性，即A∪{x}  I,则称x为A的可扩展元素。 【定义】：当拟阵M中的独立子集A没有可扩展元素时，称A为极大独立子集，或拟阵的基。 8 4.8 贪心算法的理论基础 关于极大独立子集的性质 【定理4.1】 拟阵M中所有极大独立子集的势相同。 这个定理可以用反证法证明（P134）。 【定义】若对拟阵M=(S,I)中的S指定权函数W，使得对于任意x S，有W(x)0，则称拟阵M为带权拟阵。依此权函数，S的任一子集A的权定义为 。 9 4.8 贪心算法的理论基础 3.关于带权拟阵的贪心算法 许多用贪心算法求解的问题可以表示为求带权拟阵的最大权独立子集问题。 给定带权拟阵M=(S,I)，确定S的独立子集AI使得W(A)达到最大。这种使W(A)最大的独立子集A称为拟阵M的最优子集。由于S中任一元素x的权W(x)是正的，因此，最优子集也一定是极大独立子集(不存在可扩展元素)。 10 4.8 贪心算法的理论基础 例如，最小生成树问题可以表示为确定带权拟阵MG的最优子集问题。求带权拟阵的最优子集A的算法可用于解最小生成树问题。 带权拟阵最优子集的贪心算法框架如下： 输入：具有正权函数W的带权拟阵M=(S,I) 输出：M的最优子集A。 11 4.8 贪心算法的理论基础 Set greedy (M,W) { A=; 将S中元素依权值W（大者优先）组成优先队列； while (S!=) { S.removeMax(x); if (A∪{x}I) A=A∪{x}; } return A } 12 4.8 贪心算法的理论基础 算法Greedy的时间复杂度分析 计算时间由两部分组成： (1)设n＝|S|。将S中的元素依照其权值大小组成一个优先队列，并对其进行n次removeMax运算，需要O(n㏒n)的计算时间。 (2)如果检查A∪{x}是否独立需要O(f(n)