本文關鍵詞：警示傳播算法收斂的充分條件

  更多相關文章： 警示傳播算法 收斂性 可滿足性問題 因子圖

【摘要】：信息傳播算法求解可滿足問題時有驚人的效果,難解區(qū)域變窄.然而,因子圖帶有環(huán)的實例,信息傳播算法不總有效,常表現(xiàn)為不收斂.對于這種現(xiàn)象,至今缺少系統(tǒng)的理論解釋.警示傳播(warning propagation,簡稱WP)算法是一種基礎的信息傳播算法,對WP算法的收斂性研究是其他信息傳播算法收斂性研究的重要基礎.在WP算法中,將警示信息的取值從{0,1}松弛為[0,1],利用壓縮函數(shù)的性質,給出了WP算法收斂的一個充分條件.選取了兩組不同規(guī)模的隨機3-SAT實例進行實驗模擬,結果表明:當子句與變元的比值?1.8時,該判定條件有效.
【作者單位】： 北方民族大學計算機科學系;貴州大學計算機科學系;
【關鍵詞】： 警示傳播算法 收斂性 可滿足性問題 因子圖
【基金】：國家自然科學基金(61462001,61262006,61402017) 寧夏自然科學基金(NZ14108) 北方民族大學基金(2014XYZ 03,2014XBZ04) “計算機應用技術”自治區(qū)重點學科項目~~
【分類號】：TP301.6
【正文快照】： 9825/4940.htm英文引用格式:Wang XF,Xu DY.Sufficient conditions for convergence of the warning propagation algorithm.Ruan Jian XueBao/Journal of Software,2016,27(12):3003?3013(in Chinese).http://www.jos.org.cn/1000-9825/4940.htmSufficient Conditions for Co

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 唐浩;;蟻群算法的研究與展望[J];牡丹江教育學院學報;2009年06期

2 鄧小波;曹聰聰;龍倫海;康耀紅;;蟻群算法搜索熵研究[J];海南大學學報(自然科學版);2007年04期

3 張康;顧幸生;;全局組搜索優(yōu)化算法及其應用研究[J];青島科技大學學報(自然科學版);2012年05期

4 李東曉;蔣珉;柴干;;蟻群算法優(yōu)化及其在高速公路緊急救援中的應用[J];計算機技術與發(fā)展;2010年11期

5 _5文龍 ,黃，

本文編號：1066814