读书人

子模的本质(submodular)

发布时间: 2013-01-26 13:47:03 作者: rapoo

子模的性质(submodular)

A是B的子集,

则对于函数f(),

如果:f(A+e)-f(A)>=f(B+e)-f(B)成立,则说f()函数是子模的。

增益递减。

例子如下:

u={1,2,3,4,5,6,7,8}

A={1,2,3}

B={1,2,3,5,6}

f(A)=|A| 集合A的个数

所以:f(A+e)-f(A)>=f(B+e)-f(B),例如e={3,4,5}

读书人网 >其他相关

热点推荐