警示傳播算法收斂的充分條件
大小：1.36 MB 人氣： 2018-01-05 需要積分：2
標簽：
信息傳播算法求解可滿足問題時有驚人的效果，難解區(qū)域變窄．然而，因子圖帶有環(huán)的實例，信息傳播算法不總有效，常表現(xiàn)為不收斂，對于這種現(xiàn)象，至今缺少系統(tǒng)的理論解釋．警示傳播（waming propagation，簡稱WP）算法是一種基礎的信息傳播算法，對WP算法的收斂性研究是其他信息傳播算法收斂性研究的重要基礎．在WP算法中，將警示信息的取值從{0，1}松弛為［0，1］，利用壓縮函數(shù)的性質，給出了WP算法收斂的一個充分條件．選取了兩組不同規(guī)模的隨機3-SAT實例進行實驗模擬，結果表明：當子句與變元的比值a《1.8時，該判定條件有效．
非常好我支持^.^
(0) 0%
不好我反對
(0) 0%