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