组合优化（2).ppt

1、贪婪近似算法与次模势函数,王卫 Email: wang_ Cell phone:理科楼327,本讲主要内容,次模函数与集合覆盖问题的贪婪算法； 一般次模覆盖问题； 几个应用。,贪婪算法的概念,在算法执行的每一步，按照某一目标做出对当前最有利的选择（局部最优），因此贪婪算法是“目光短浅”的； 在算法的每一步一旦做出局部最优选择后，在后面的算法进行中不再更改，因此它是“一条道走到黑”；,贪婪算法的优、缺点,好处：时间复杂性低，易于实现。 （）成功的例子：可快速求出最小生成树（MST）问题可求出最优解。可进一步推广至拟阵（matroid) （）贪婪算法也是设计近似算法的一个

2、最基本的方法。对某些问题，如集合覆盖（Set Cover)问题，甚至可以给出最好可能的近似比。 但，一般而言，对大多数组合优化问题，贪婪算法在理论上无法给出成功的分析，即使有些算法在实际计算中表现良好。能够给出理论分析的贪婪算法大都具有次模势函数。,次模函数,令为一个有限集，是定义在的幂集上的函数，成为次模函数（submodular function) ,如果 令，则上述不等式可以写为 事实上，在第二 个不等式中令可得到第一个。,B,A,D=AB,次模函数的直观含义,次模函数在组合优化中的作用类似于连续优化中的凹函数； 其反映了一种边际效用递减规律。 令代表个汉堡，表示 一个人吃了中汉堡的效用

3、函数（满足感），则 有；这表示他吃了一个汉堡后再吃第二个汉堡所增加的效用，比他吃两个汉堡后再吃第三个汉堡增加的效用要大。,次模函数的例子,定义，则容易验证： 因此集合的势函数是次模函数（实际上是模函数） 令为一有限集，表示的一些子集构成的集簇。定义： ，其中 。 则可以验证，是次模函数。,事实上，表示出现在集簇所含的集合中的 元素的数目；表示既出现在中也出现在中的元素数目； 每个在中出现的元素一定同时在，中出现。 因此，,集合覆盖问题（Set Cover）,给定集合 及其子集簇C，求C 的所含集合数目最少的子簇A，使得，,1,4,2,5,3,B3,B2,B4,B1,一些应用背景,无线传感器网络

4、中，每个传感器监控一定范围，如何选数目最少的一组传感器，使得其可以监控整个地区。,对于C的每个子簇 ，定义次模函数 Set Cover问题的贪婪算法1：,贪婪算法示意图,1,4,3,2,定理 上述贪婪算法是集合覆盖问题的多项式时间 -近似算法。其中 表示C中所含元 素数目最多的集合的势。 证明：令 为贪婪算法按顺序挑选出来的集合。 令 ，令 表示为最小集合覆盖问题的最优解。,由贪婪准则， 是在所有剩余集合（除 中集合外）中能够最多覆盖未被 覆盖元素的集合。 未被 覆盖的元素数目为 ，而这些未被覆盖的元素可以被最优解中的所有集合覆盖，因此，最优解中平均每个集合可覆盖 个未被覆盖的元素。,上述证明

5、用到f的次模性了吗？,一般次模覆盖问题,加权集合覆盖问题,一般次模覆盖问题是许多问题的推广。譬如，一个子集簇 当且仅当 是一个集合覆盖。因此，SCP可看作加权的集合覆盖问题。 定义（Weighted Set Cover） 给定集合 及其子集簇C，C 中每个集合赋于一定权重，求C 的一个具有最小总权重的子集簇使得其覆盖 。,Able引理,定理的证明,证明的思路,1,2,3,应用：正面影响控制集问题,给定一个图G=（V，E）代表一些人按朋友个关系形成的一个社会网络。研究表明，一个人的某些不良习惯(譬如抽烟、酗酒等）与他的朋友圈关系很大。 假定一个人的一半朋友具有某种不良习惯，则这个人也具有该不良习惯。 问