(转)Submodual

子模态定义

子模态是集合函数的一种性质。一个集合函数$f(x)$的定义要满足下面这个性质

即$f(x)$的定义域为集合$\Omega$的任何一个子集,值域为实数集。而这个集合函数如果要满足子模态性质的话,还需要满足下面三个等价条件中的任何一个。

  • 对于任何一个$X,Y\subset\Omega$且$X\subset Y$,以及对任何一个$X, Y\in\Omega$,下面的式子一定成立。
  • 对于任何一个$X,Y\subset\Omega$,下面的式子一定成立。
  • 对于任何一个$X\subset\Omega$及$x_1,x_2\in\Omega$,下面的式子一定成立

读者可以很轻松的验证这几个条件是等价的,这里就不去证明了。

根据这些条件,我们可以得出下面这个结论。设$f_1(x),f_2(x),⋯,f_k(x)$都是有子模态性质的函数,$c_1,c_2,⋯,c_k$是非负实数,则下面这个函数

仍然是子模态的。即多个子模态函数的非负线性组合仍然是子模态函数。这个推论可以很简单的验证出来,这里也就懒得做证明的。

子模态与贪心方法

接下来的问题就是,子模态这个函数性质有什么用。简单来说子模态这个函数性质在组合优化中很有用。特别是针对保持$\mid x \mid$的大小固定,然后去求$f(x)$的最大值这种问题。 这个子模态性质可以保证我们在贪心求解这个问题得到的解不会差,事实上贪心解$f(x)$的值不会小于$(1−1/e)∗OPT$,其中$OPT$为最优解。在该问题的贪心求解过程中,我们是从$0$开始构建目标集合$x$的。每一步我们将一个新的元素加入到$x$中,迭代$k$步。我们以$X_i$来代表迭代$i$次之后的$x$集合,初始$x_0 = \phi$。我们对下一个要加入的节点$u$的选取的贪心规则为

现在我们要证明在此贪心规则下

为此,我们先证明一个引理

其中$B=b_1,⋯,b_k$.此时我们定义$B_i=b_1,⋯,b_i$,则

设最优解为$T=t_1,⋯,t_k,\delta_i=f(X_i)−f(X_{i−1})$,根据上面这个不等式我们可以推出

综上我们可以得出这个结论

所以

通过上面的递推式,我们可以给出$f(X_i)$

这个是简单的递推数列求通项,这里也就懒得证明了。所以

这就是贪心大法好的证明。

本文参考链接: http://spiritsaway.info/algorithm/submodual.html

分享到