![](https://csdnimg.cn/release/download_crawler_static/18687389/bg1.jpg)
第 29 卷第 3 期 温 州 大 学 学 报·自 然 科 学 版 2008 年 6 月
Vol 29, No 3 Journal of Wenzhou University · Natural Sciences Jun, 2008
求解下模集函数最大值问题的局部搜索算法
王武民,张防防,柘晓莉,何尚录
(兰州交通大学数理与软件工程学院,甘肃兰州 730070)
摘 要:给出了求解具有简单约束的下模集函数最大值问题的一种局部搜索算法,并讨论了所给算法
的性能保证.该算法的基本思想是:算法每次迭代总是在当前近似解集的邻域内,求出使目标函数取
得最大的集合,将其作为新的近似解集.分析表明,所给算法是一种多项式时间近似算法.
关键词:组合优化;下模集函数;近似算法;性能保证
中图分类号:O224 文献标识码:A 文章编号:1006-0375(2008)03-0012-06
设
{1, 2 , , }In= "
,
{
}XX IΩ= ⊆
是由 I 的所有子集组成的集合,若
:fRΩ→
满足
() () ( ) ( )fX fY fX Y fX Y+≥∩+∪
,
,XY∀∈Ω
则称
f 为定义在
Ω
上的下模集函数.关于下模集函数的详细资料可参考文献[1].
本文考虑如下具有简单约束的下模集函数最大值问题
max ( )
..| | ,
fX
st X P X=∈Ω
(1)
其中,
pn<
为给定的正整数.
首先需要说明的是,上述问题在组合优化问题中具有非常重要的作用.譬如,著名的最大
p
-
设施定位问题对应于求
XI⊆ ,使其满足
Xp= 且使下模集函数 ()fX达到最大.
求下模集函数的最大值问题属于 NP-难问题,没有非常有效的求解方法.人们主要研究求解
此类问题的比较有效的近似算法,对多项式时间算法的研究很少.在求解各种组合优化问题的近
似算法中,贪婪算法和局部搜索法是其中比较简单且有效的算法.最近,Ilev 和 Linker
[2-3]
给出了
求解具有简单约束的非负非减上模集函数最小值问题的一种贪婪算法,并讨论了所给算法的性能
保证.本文将给出求解具有简单约束的非负非减下模集函数的最大值问题的一种局部搜索法,并
分析所给算法的性能保证.
本文采用如下记号:对
,XIxX⊆∈及
yIX∈ ,用 {}Xy+ 表示 {}Xy∪ ,用 {}Xx− 表
示
{}Xx
.
1 若干引理及其证明
设
:fRΩ→
是非负非减下模集函数(即对满足 XY⊆ 的任何
,XY I⊆
有
() ()fX fY≤
),
收稿日期:2007-07-05
作者简介:王武民(1981- ),男,甘肃靖远人,硕士研究生,研究方向:最优化计算方法