梁國宏 劉光榮 宋修朝 馮軍慶

[摘要]根據(jù)上模函數(shù)的定義,給出了在某個有限集合上的近似模函數(shù)的定義及其性質(zhì),主要研究了求解上模函數(shù)的近似算法及模函數(shù)的算法。

[關(guān)鍵詞]組合優(yōu)化問題 上模函數(shù) 近似模函數(shù)算法

設(shè)V是一個非空有限集合,如果

則稱f∶2琕是上模函數(shù)。類似地,上式(1)中取“≤”時稱f為下模函數(shù);取上式(1)中“=”時稱f為模函數(shù)。

定義1:已知上模函數(shù)f∶2琕→R,如果模函數(shù)h璶∶2琕→R滿足:

h璶(A)≤g(A),歇罺,則稱函數(shù)h璶是函數(shù)g的近似模函數(shù).特別地,如果函數(shù)h璶是函數(shù)g的近似模函數(shù),且h璶(A璶)≤g(A璶),歇璶罺,則稱函數(shù)h璶是函數(shù)g的在A璶上的完全近似模函數(shù)。

性質(zhì)1:假設(shè)g∶2琕→R是一個上模函數(shù),π是V的任一排列.設(shè)W={π(1),π(2),…,π(i)}有W﹟V|=V

定義函數(shù)h∶V→R:

顯然有有下列性質(zhì):

算法1:給定上模函數(shù)g與f,求f-g的近似最小值。

步驟如下:

1 給定集V的任意排列π0,n=0,min=∞;

2 h璶=(g,π﹏-1)的模近似, ,π﹏+1,表示A璶開始的任意排列,n=n+1;

3 如果val

性質(zhì)2:上述所提到的每個h是g的展開基擬陣的一個頂點,且這個頂點可以合適的置換中得到。此外,如果c是R﹟V|中的一個向量,那么上面的貪婪算法求解以下的優(yōu)化問題:

算法2:給定上模函數(shù)g和π排列,求上模函數(shù)g的模近似函數(shù)h.

步驟如下:

1

2

3 如果n≤|V|,則轉(zhuǎn)2;否則,停止計算。

算法1給出了求一個給定的上模函數(shù)g與f的f-g的近似最小值的有效算法;算法2給出了求上模函數(shù)g的模近似函數(shù) 的算法。

參考文獻(xiàn):

[1]M.Narasimhan and J.Bilmes."PAC learning bounded treewidth graphical models".Proceed-ings of the 20th conference on Uncertainty in Artificial Intelligece,2004.

[2]M,Grotschel,L.Lovasz and Schrijver."The ellipsoid method and its consequences in combinatorial optimization".In Combinatorica, v.1,Pages 169-197,1981.

[3]Mukund Narasimhan and Jeff Bilmes,"A submodular-supermodular Procedure with applications to discriminative structure learning".in Combinatorial structures and their applications,1970.