子集和问题算法_贪婪算法有多好？Submodularity告诉你

104 阅读 0 评论 69 点赞

我是靠谱客的博主专注秋天，最近开发中收集的这篇文章主要介绍子集和问题算法_贪婪算法有多好？Submodularity告诉你，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

贪婪算法可以说是最符合我们人类直觉的算法了，甚至有的时候贪婪算法就可以得到目标的最优解，比如说最小生成树算法。那么我们自然就会想知道，它能达到最优值吗？如何判断？实际上一个叫Matroid的东西是可以帮助我们判断是否能达到最优值的。但是如果不能达到最优，它到底有多近似呢？submodularity optimization对这个问题给予了一个答案。

我们形式化地定义一下这个贪婪算法的问题，对于元素N，我们希望找到一个使得f最大的最优子集

，即

，其中

这样的问题很显然，我们是不可能去遍历所有的子集来找这个最优解的，所以在什么条件下，这样的问题才可以求解？

submodularity condition

接下来，我们会对f做一些约束，赋予他一个叫monotone和submodularity的性质。我们可以把f想象成是一个评价雷达覆盖范围的函数，当我们在不同的点选择放置雷达的时候，他有可能会跟现有的一些雷达的范围有重合，但是可以肯定的是，当我们在不停放置雷达的时候，覆盖范围是肯定不会减少的，只会变得越来越大。即如果有集合

一定有