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