求解上模函數的近似算法

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

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

[關鍵詞]組合優化問題 上模函數 近似模函數算法

設V是一個非空有限集合,如果

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

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

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

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

定義函數h∶V→R:

顯然有有下列性質:

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

步驟如下:

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

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

3 如果val

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

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

步驟如下:

1

2

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

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

參考文獻:

[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.