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