本文關(guān)鍵詞：RB模型實(shí)例集上置信傳播算法的收斂性　出處：《軟件學(xué)報(bào)》2016年11期 　論文類型：期刊論文

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

【摘要】：置信傳播算法求解RB(k,n,a,r_c,p)模型實(shí)例時(shí)非常有效,幾乎能夠有效求解接近可滿足性相變點(diǎn)的難解實(shí)例.然而,因子圖帶有回路的實(shí)例,置信傳播算法不總有效,常表現(xiàn)為不收斂.對(duì)于這種現(xiàn)象,至今缺少系統(tǒng)的理論解釋.置信傳播算法是最為基礎(chǔ)的信息傳播算法,對(duì)置信傳播算法的收斂性分析是其他信息傳播算法收斂性分析的重要基礎(chǔ).在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)生的隨機(jī)實(shí)例集上高概率收斂.最后,在RB(k,n,a,r_c,p)模型上選取了幾組不同的數(shù)據(jù)進(jìn)行數(shù)值模擬,實(shí)驗(yàn)結(jié)果表明該結(jié)論有效.當(dāng)問題規(guī)模n增大時(shí),在RB(k,n,a,r_c,p)模型的可滿足區(qū)域,實(shí)驗(yàn)收斂區(qū)間趨于一個(gè)固定范圍,而理論收斂區(qū)間逐漸變窄.原因在于,RB(k,n,a,r_c,p)模型是一個(gè)具有增長定義域的隨機(jī)CSP實(shí)例產(chǎn)生模型,不協(xié)調(diào)賦值的數(shù)目與參數(shù)p及問題規(guī)模n有關(guān).
【作者單位】： 北方民族大學(xué)計(jì)算機(jī)科學(xué)系;貴州大學(xué)計(jì)算機(jī)科學(xué)系;
【基金】：國家自然科學(xué)基金(61462001,61262006)~~
【分類號(hào)】：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

【相似文獻(xiàn)】

相關(guān)期刊論文 前1條

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

相關(guān)碩士學(xué)位論文 前1條

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

，

本文編號(hào)：1322494