本文關鍵詞：RB模型實例集上置信傳播算法的收斂性　出處：《軟件學報》2016年11期 　論文類型：期刊論文

  更多相關文章： 置信傳播算法 收斂性 約束可滿足性問題 RB模型

【摘要】：置信傳播算法求解RB(k,n,a,r_c,p)模型實例時非常有效,幾乎能夠有效求解接近可滿足性相變點的難解實例.然而,因子圖帶有回路的實例,置信傳播算法不總有效,常表現(xiàn)為不收斂.對于這種現(xiàn)象,至今缺少系統(tǒng)的理論解釋.置信傳播算法是最為基礎的信息傳播算法,對置信傳播算法的收斂性分析是其他信息傳播算法收斂性分析的重要基礎.在RB(k,n,a,rc,p)模型中,取k=2,a1/k,r_c0均為常數(shù),且滿足ke~(-a/r_c)≥1.證明了如果p∈(0,n~(-2a)),則置信傳播算法在RB(k,n,a,r_c,p)模型產(chǎn)生的隨機實例集上高概率收斂.最后,在RB(k,n,a,r_c,p)模型上選取了幾組不同的數(shù)據(jù)進行數(shù)值模擬,實驗結(jié)果表明該結(jié)論有效.當問題規(guī)模n增大時,在RB(k,n,a,r_c,p)模型的可滿足區(qū)域,實驗收斂區(qū)間趨于一個固定范圍,而理論收斂區(qū)間逐漸變窄.原因在于,RB(k,n,a,r_c,p)模型是一個具有增長定義域的隨機CSP實例產(chǎn)生模型,不協(xié)調(diào)賦值的數(shù)目與參數(shù)p及問題規(guī)模n有關.
【作者單位】： 北方民族大學計算機科學系;貴州大學計算機科學系;
【基金】：國家自然科學基金(61462001,61262006)~~
【分類號】：TP18
【正文快照】： org.cn/1000-9825/4877.htm英文引用格式:Wang XF,Xu DY.Convergence of the belief propagation algorithm for RB model instances.Ruan Jian Xue Bao/Journal of Software,2016,27(11):2712?2724(in Chinese).http://www.jos.org.cn/1000-9825/4877.htmConvergence of the

【相似文獻】

相關期刊論文 前1條

1 高恩婷;顧一清;嚴建峰;;基于快速置信傳播算法的并行主題建模方法研究[J];南通大學學報(自然科學版);2013年01期

相關碩士學位論文 前1條

1 房卓群;基于置信傳播的WSN節(jié)點定位方法研究[D];沈陽建筑大學;2014年

，

本文編號：1322494