组合优化（2)

《组合优化（2)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、步推广至拟阵（matroid)（２）贪婪算法也是设计近似算法的一个最基本的方法。对某些问题，如集合覆盖（SetCover)问题，甚至可以给出最好可能的近似比。但，一般而言，对大多数组合优化问题，贪婪算法在理论上无法给出成功的分析，即使有些算法在实际计算中表现良好。能够给出理论分析的贪婪算法大都具有次模势函数。次模函数令　　为一个有限集，　　　　　是定义在Ｘ的幂集上的函数，　成为次模函数（submodularfunction),如果令　　　　　　　　　　　，则上述不等式可以写为事实上，在第二个不等式中令　　　　可得到第一个

3、。BAD=AB次模函数的直观含义次模函数在组合优化中的作用类似于连续优化中的凹函数；其反映了一种边际效用递减规律。令　　　　　　代表５个汉堡，　　　　　表示一个人吃了Ｅ中汉堡的效用函数（满足感），则有　　　　　　　　；这表示他吃了一个汉堡后再吃第二个汉堡所增加的效用，比他吃两个汉堡后再吃第三个汉堡增加的效用要大。次模函数的例子定义　　　　　　　　，则容易验证：因此集合的势函数是次模函数（实际上是模函数）令　为一有限集，Ｃ表示　的一些子集构成的集簇。定义：，其中。则可以验证，　是次模函数。事实上，　　表示出现在集簇Ａ所含

4、的集合中的元素的数目；　　　　　　　　　　表示既出现在Ａ中也出现在Ｂ中的元素数目；每个在　　　中出现的元素一定同时在Ａ，Ｂ中出现。因此，ＢＡＡ３Ａ２Ａ１集合覆盖问题（SetCover）给定集合及其子集簇C，求C的所含集合数目最少的子簇A，使得，14253B3B2B4B1一些应用背景无线传感器网络中，每个传感器监控一定范围，如何选数目最少的一组传感器，使得其可以监控整个地区。对于C的每个子簇，定义次模函数SetCover问题的贪婪算法1：贪婪算法示意图1432定理上述贪婪算法是集合覆盖问题的多项式时间-近似算法。其中表示C

5、中所含元素数目最多的集合的势。证明：令为贪婪算法按顺序挑选出来的集合。令，令表示为最小集合覆盖问题的最优解。由贪婪准则，是在所有剩余集合（除中集合外）中能够最多覆盖未被覆盖元素的集合。未被覆盖的元素数目为，而这些未被覆盖的元素可以被最优解中的所有集合覆盖，因此，最优解中平均每个集合可覆盖个未被覆盖的元素。上述证明用到f的次模性了吗？一般次模覆盖问题加权集合覆盖问题一般次模覆盖问题是许多问题的推广。譬如，一个子集簇当且仅当是一个集合覆盖。因此，SCP可看作加权的集合覆盖问题。定义（WeightedSetCover）给定集合

6、及其子集簇C，C中每个集合赋于一定权重，求C的一个具有最小总权重的子集簇使得其覆盖。Able引理定理的证明证明的思路123应用：正面影响控制集问题给定一个图G=（V，E）代表一些人按朋友个关系形成的一个社会网络。研究表明，一个人的某些不良习惯(譬如抽烟、酗酒等）与他的朋友圈关系很大。假定一个人的一半朋友具有某种不良习惯，则这个人也具有该不良习惯。问题：从图G中选择最少具有不良习惯的人，使得其改变不良习惯，从而使得网络G中每个人朋友圈中有一半以上具有好的习惯。f次模性的证明Thanks,End