《组合最适化问题近似解法ppt培训课件》由会员分享，可在线阅读，更多相关《组合最适化问题近似解法ppt培训课件（58页珍藏版）》请在金锄头文库上搜索。
1、組合最適化問題近似解法,東京大学大学院工学系研究科 計数工学専攻 松井知己,発表目次,近似解法？ MAX SAT問題近似解法 /近似解法 0632近似解法 /近似解法 MAX CUT問題 0878近似解法 半正定値計画 MAX SAT問題0878近似解法,近似解法？,近似解法：近似精度存在解法 得解最適解距離見積存在 発見的解法：近似精度不明 近似比率： （最大化問題場合） （得解目的関数値）（最適値） 近似解法： 近似比率以上解必求解法,MAX SAT近似解法,SAT問題(問題例),SAT問題（Satisfiability problem：充足可能性問題) 変数：U=a1，a2，a3 ：=C
2、1 ，C，C， C， C， C C1 = a2 ， C = a1， a2，a3 ， C = a1，a2，a3 ， C = a1，a2， a3 ， C = a1，a2 ， C = a1， a3 （a a 否定意味）,中全真U 真偽割当？真中少真,SAT問題(問題例真偽割当),U= a1， a2， a3 T T F C1 = a2 T C = a1， a2，a3 T C = a1，a2，a3 T C = a1，a2， a3 F C = a1，a2 T C = a1， a3 T,中全真, U 真偽割当存在,SAT問題（定義）,SAT問題（Satisfiability problem：充足可能性問題)
3、 入力:変数U，集合 質問：? U 真偽割当，中全真：入力変数，否定 ：集合 真中少真 NP完全事示最初問題Cook71,MAX SAT(問題例),U= a1， a2， a3 例題提供:宮本裕一郎 T T F 重 C1 = a2 T 4 C = a1， a2，a3 T 1 C = a1，a2，a3 T 6 C = a1，a2， a3 F C = a1，a2 T 3 C = a1， a3 T 9 真重総和最大化,総和=重輪 ,MAX SAT問題（定義）,MAX SAT問題 入力:変数U，集合非負整数重:Z 問題：中真重和最大，U真偽割当求 各中個以下 MAX SAT MAX SAT問題NP困難
4、Garey，Johnson and Stockmeyer 71,MAX SAT1/2 近似解法,D.S.Johnson 74 非常単純化算法,/近似解法(数値例),/近似解法： 各変数/確率真1/2 1/2 1/2 （重総和=27） C1 = a2 (1/2) =2 C = a1， a2，a3 (7/8) =7/8 C = a1，a2，a3 (7/8) =21/4 C = a1，a2， a3 (7/8) =7/2 C = a1，a2 (3/4) =9/4 C = a1， a3 (3/4) =27/4 真重総和期待値=22,/近似解法,/近似解法： 各変数/確率真 解析：個含真確率 1-(1/2
5、)k 真重期待値， PrC 真w（C ）C ( 1-(1/2)k )w （C ）C，|C |= (1/2)w（C ）C (重総和)(最適値)， (1/2)w（C ）|C (1/2)*最適値,1-(1/2)k 近似解法,個以上含真確率 1-(1/2)k以上 任意個以上含，1/2 近似解法，1-(1/2)k 近似解法,MAX SAT0.632 近似解法,Goemans and Williamson 94 線形緩和問題用 問題例確率変化算法,整数計画定式化,変数集合 =a1,a2,.,an， 集合= C1,C2,.,C 添字集合1,2,.,n,n+1,.,2n in，iai ， nnin，ni ai
6、 対応 変数x1,x2,.,xn , xn+1,xn+2,.,x2n,z 1,z 2,.,z xi =1 ai 真， z =1 C 真,max.w j z j s.t. xi+xn+i =1 ( ), xi0,1 ( )，z j xi (), z j 0,1 ( ),i c,線形緩和問題,化算法： （x*，*）線形緩和問題最適解 各変数 ai 確率 xi*真,化算法(数値例), a2 a1， a2，a3 a1，a2，a3 a1，a2， a3 a1，a2 a1， a3 ,max.4z1+1z2+6z3+4z4+3z5+9z6s.t. x2 z1x4 + x2 + x6 z2x4 + x5 + x
7、6 z3x4 + x5 + x3 z4x1 + x5 z5x1 + x3 z6xi + xn+i = 1, 0xi , xn+i 1( i ),化算法：線形緩和問題最適解 x* =(3/4,3/4,1/2,1/,1/,1/2)最適値26 最適値上界各変数 ai 確率 xi*真,化算法（定義),（x*，*）線形緩和問題最適解 各変数 ai 確率 xi*真 真重総和期待値=,z j,z j *,補題証明,証明：相加相乗平均， 1- x*i1 （ （ 1 x*i ）/） 1（ /）z*j 関数 1（ z*j /） 凹性 1（1/）,i c,i c,z* j,z j *,Z*j,（1/ )近似解法,真
8、重和期待値？k :個含集合MAX kSAT，,0.632近似解法,MAX kSAT， 期待値 （1/ ) ) 1 3/4=0.75 19/27=0.703 175/256=0.684 11/e0.632,MAX SAT3/4 近似解法,Goemans and Williamson 94 1/2近似解法 0.632近似解法組合,1/2近似解法0.632近似解法, k個含， 1/2近似解法： 真確率（1/2) ) .632近似解法：真確率（/) ) （1/ ) ) （1/2) ) 1 1/2 3/4=0.75 3/4=0.75 19/27=0.703 7/8=0.875 175/256=0.684
9、 15/16=0.9735 11/e0.632 1,4/3近似解法,4/3近似解法 1/2近似解法 0.632 近似解法一方確率(1/2)選実行 任意正整数対， （1/ ) )（1/2) )/23/4成立 期待値 (MAX SAT線形緩和問題最適値) （1/ ) )（1/2) )/2 (MAX SAT最適値) (3/4),4/3近似解法(実際）,4/3近似解法 1/2近似解法 0.632 近似解法一方確率(1/2)選実行下方同良 1/2近似解法 0.632 近似解法両方実行良方選z1/2 :1/2近似解法期待値 zLP :0.632 近似解法期待値( z1/2 +zLP)/2 maxz1/2,
10、zLP,脱化(derandomization),脱化, a2 a1， a2，a3 a1，a2，a3 a1，a2， a3 a1，a2 a1， a3 a1 a2 a3真確率( x,1/2,1/2)期待値 4(1-1/2)+ 1(1-(1/2)2(1-x) +6 (1-(1/2)2 (1-x)+4 (1-(1/2)2(1-x)+3 (1-(1/2) x)+9 (1-(1/2)x) =19+(13/4) xx=1、22.25 a1 a2 a3真確率(1,y,1/2)期待値 4y+ 1(1-(1/2)y) +6 (1-(1/2) (1-y)+4 (1-(1/2) (1- y)+3 +9 =19+3.5yy=1、22.5 a1 a2 a3真確率(1,1,z)期待値 22+1(1-z)z=1、23 -,
