子模集合函数（Submodular set function）

子模函数是一个集合函数，有减小回转属性（diminishing returns ），适用于多种应用，包括近似算法，博弈理论（函数建模）和电网络。

定义

如果Ω是一个集合，一个子模函数是一个集合函数， $f :2^Ω to mathbb R$ ，其中$2^Ω$ 表示集合Ω的幂集，满足一下等式：

$1. 对所有X,Y subseteq Ω，其中Xsubseteq Y ,则对所有xinΩsetminus Y 有f(Xcup {x})-f(X)ge f(Ycup {x})-f(Y).$
$2. 对所有S,T subseteq Omega 有 f(S)+f(T) ge f(S cup T)+f(S cap T).$
$3. 对所有X subseteq Omega ,x_1,x_2 in Omega ,我们有 f(X cup {x_1})+ f(X cup {x_2} ge f(X cup {x_1,x_2})+f(X).$

子模函数的类型

单调性

对每一个$T subseteq S, 有f(T) le f(S).$ 单调子模型函数包括以下几种类型：

• 线性函数
  函数型如$f(S)=sum_{iin S}w_i$ 被称为一个线性函数。如果 $forall i,w_ige0$,则函数f是单调的。
• 预算可加函数（Budget-additive function）
  函数形如$f(S)=min(B,sum_{iin S}w_i)$ 对于任意的的 $w_ige 0，Bge 0$ 称为预算可加的。
• 收敛函数（Coverage function）
  令$Omega ={E_1,E_2,...,E_n}$ 是基本集$Omega ^‘$ 的集合。函数
• 熵
  令$Omega={ X_1,X_2,...X_n}$ 为随机变量的集合，对于任意的$S subseteq Omega$,$H(S)$ 是一个子模函数，其中$H(S)$ 是随机变量集合$S$ 的熵。
  -拟阵秩函数
  令$Omega ={ e_1,e_2,...e_n}$ 作为一个定义拟阵的基本集。则拟阵的秩函数是一个子模函数。

非单调性

如对称函数，图像分割，互信息

优化问题

子模函数有属性类似于凸函数或者凹函数。因此考虑凸或凹函数的优化的优化问题同样可以考虑到子模函数上，即在一些约束下的最大化或最小化子模函数。
最简单的最小化问题是在无约束的情况下找到一个集合$Ssubseteq Omega$ 最小化子模函数，这个问题是可以计算的。
而对于子模函数的最大化问题通常的NP难的。如最大切割，最大覆盖问题可以被视为在合适约束下的通常最大化问题。通常这些问题的近似算法是基于如贪心算法或者是本地搜索算法。对于无约束下的最大化对称非单调子模函数符合1/2近似算法。如计算图的最大分割。对于最大化一个单调子模函数，在基数约束下符合$1-1/e$ 近似算法。最大覆盖问题是这个的一个典型例子。

最后

以上就是甜甜小蝴蝶为你收集整理的子模集合函数（Submodular set function）的全部内容，希望文章能够帮你解决子模集合函数（Submodular set function）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。