求解最大p-中心問題的一種近似算法

《求解最大p-中心問題的一種近似算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學術(shù)論文-天天文庫。

1、第30卷第6期四川兵工學報2009年6月求解最大P一中心問題的一種近似算法黃輝，王忠思，梁國宏2(1．海軍士官學校，安徽蚌埠233012；2．空軍工程大學，西安710051)摘要：求解最大P一中心問題屬于計算下模集函數(shù)最大值問題，該類問題在組合優(yōu)化問題中具有非常重要的應用．為此，給出了求解具有簡單約束的最大P一中心問題的一種局部搜索算法，并討論了所給算法的性能保證．關(guān)鍵詞：組合優(yōu)化問題；下模集函數(shù)；近似算法；性能保證．中圖分類號：0241文獻標識碼：A文章編號：1006—0707(2009)06—0085—04考慮如下的P～中心問

2、題的最大值問題maxf(X)(1)s．t．IXI=P，XEn其中，P

3、似算法．Ilev和Linker_2]給出了求解具有簡單約束的非負非減上模集函數(shù)最小值問題的一種貪婪算法，并討論了所給算法的性能保證．本文中將給出求解具有簡單約束的非負非增最大P一中心問題的一種局部搜索算法，并分析所給算法的性能保證．本文中采用如下記號：對X，，∈及Y∈』＼X，用+Y表示XU{Y)，用X—表示＼{}．1若干引理及其證明設，：n—為非負非增下模集函數(shù)，(即對滿足XY的任何X，YC，有，()≥，(1，))，對任何，，∈，定義_d(X)=f(X—)一，(X)(2)則有d()i>o，稱其為，在處關(guān)于的向后差分．關(guān)于d()有引

4、理1若x，Yc，滿足xY且∈x，則有d()≤(y)．_證明由廠的下模性有，()+廠(Y—)≥，((Y—)n)+，(y)．從而有dx(X)：f(X—)一，(X)=f((Y—)n)一，()≤／(X)一f(Y)一f(x)+，(Y—)=，(Y—)一，(Y)=d(Y)引理1證畢．定義(，m)a011(3)d，>，∈o，收稿日期：2009—03—26作者簡介：黃輝(1982一)，女，安徽蚌埠人，碩士，主要從事最優(yōu)化理論與算法的研究86四)11兵工學報容易看出目滿足O≤≤1．因此，可以作為衡量，的函數(shù)值變化快慢的參數(shù)．引理2對任何∈，有，(1一

5、d(，)≤d({})．證明由定義有d(，)一d({))≥——廠從而當d(，)>0時有：(1一日)(，)≤dx({))；而當d(，)=0時顯然有(1一日)d(，)≤d({))故結(jié)論成立，引理2證畢．下面令A=＼{a1，?，口)，={口1，?，a)，A0=，，0=A，、{口“，aj)，={a,1，?，aj)，(=1，?，k)B=，、{b”，bf)，百={b1，?，b1)，B0=，，o=西Bi=¨{b，)，={bl，?，bj)，(J=1，?，f)引理3設一d6(一1)．．。廠為非負非增的下模函數(shù)，則有f(B)≥．6∈、^J證明由于，(B

6、o)=f(，)≥0，故有，()=(^)=f(B^．1＼{b))=，(B一＼{bk))一，(B一1)+，(一1)=d(B—1)+，(一1)=?=d(Bo)+db2(曰-)+一-∑d^(一)。E—J．又由f的非增性可知，對任意6∈西，都有d6(毋一1)≥O．故可得，(曰)≥(一)≥、j叱(一)引理證畢．引理4f(An=，(+d(曰N一·)=，(A)+(An一·)·4c^、?目pL、?證明先證第一個等式，由于f，(BNA一1)吼簪Bf(An=，(BnAk)_，((BNak-1)＼1，(BNAk-I)+dBNA㈦)A類似地有f，(BNA一

7、2)a^1B卜(BAA)+(BNAk-2)lEB＼A依次類推可得S(AnB)：S(BNA。)+∑d(BnAJ一1)=，(B)+(BN一)。EA、。、用類似的方法可證明第二個等式，引理證畢．引理5設IAI：IBI：P，IA＼BI=IB＼AI=k且A＼B='[ai，n，?，(ti)，B＼A=(6j，bi，?，)，則有(1一+)，()一(1一目)廠(A)≥喜[，(A+{)一{))一，(A)】證明由引理4有(1一)，(一(1一目)，(A)：(1一)∑db．(An一1)一(1)∑一d(曰N-)(4)∈”由弓l理1、引理2知，對任何∈＼吾有(

8、1一)d。(BnA卜1)≤(1一)do．(，)≤d({ay))≤d(A+{))對任何∈B一、A一有(AnB卜1)≥dh({))≥【1一)d6(D≥(1一)db,(A+{))．由(4)式有(1一)，(B)一(1一)A)≥(1一)∑dbi(A+{})一