• ISSN 0258-2724
  • CN 51-1277/U
  • EI Compendex
  • Scopus 收录
  • 全国中文核心期刊
  • 中国科技论文统计源期刊
  • 中国科学引文数据库来源期刊

信息传播算法收敛的后门集

王晓峰,  许道云,  秦永彬

downloadPDF
文章导航 > 西南交通大学学报  > 2012 >  25(1): 32-38,62.
王晓峰, 许道云, 秦永彬. 信息传播算法收敛的后门集[J]. 西南交通大学学报, 2012, 25(1): 32-38,62. doi: 10.3969/j.issn.0258-2724.2012.021.01.006
引用本文: 王晓峰, 许道云, 秦永彬. 信息传播算法收敛的后门集[J]. 西南交通大学学报, 2012, 25(1): 32-38,62. doi: 10.3969/j.issn.0258-2724.2012.021.01.006
shu
WANG Xiaofeng, XU Daoyun, QIN Yongbin. Backdoors of Message Propagation Algorithm Convergence[J]. Journal of Southwest Jiaotong University, 2012, 25(1): 32-38,62. doi: 10.3969/j.issn.0258-2724.2012.021.01.006
Citation: WANG Xiaofeng, XU Daoyun, QIN Yongbin. Backdoors of Message Propagation Algorithm Convergence[J]. Journal of Southwest Jiaotong University, 2012, 25(1): 32-38,62. doi: 10.3969/j.issn.0258-2724.2012.021.01.006
shu

信息传播算法收敛的后门集

doi: 10.3969/j.issn.0258-2724.2012.021.01.006
基金项目: 

国家自然科学基金资助项目(60863005)

详细信息
    作者简介:

    王晓峰(1980-),男,博士研究生,研究方向为算法分析与设计,电话:15086011980,E-mail:wxf_gzu@163.com

Backdoors of Message Propagation Algorithm Convergence

    摘要
  • 摘要: 为了探讨WP(警示传播)算法的收敛性,给出了WP算法收敛的后门集.通过对此后门集中的变元赋 值,可将布尔公式简化成其因子图为树型结构的子公式,WP算法在子公式上收敛.最后,设计了一个求解该后 门集的随机算法,并分析了该算法的可行性.结果表明,所提出的求解该后门集的随机算法是有效的.

     

    Abstract: In order to investigate the convergence of the WP (warning propagation) algorithm, backdoors of the WP algorithm were given. By assigning values to variables in the backdoors, the Boolean formula can be simplified to sub-formula having factor graph with tree structures, and the convergence of the WP algorithm can be guaranteed in the sub-formula. Finally, a randomized algorithm for solving the backdoors was designed and its feasibility was analyzed. The result show that the randomized algorithm is feasible.

     

    • HTML全文
    • 参考文献(1)
  • 　　[1]　CHEESEMAN P, KANEFSKY B,TAYLOR W M. Where the really hard problems are[C]∥Proceedings of the 12th International Joint Conference on Artificial Intelligence. San Francisco: Morgan Kaufmann,1991: 331-337. 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 [2]　FRIEZE A M, MOLLOY M. The satisfiability threshold for randomly generated binary constraint satisfaction problems[J]. Proceedings of Random, 2006, 28(3): 323-339. 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 [3]　ZHANG W. Phase transitions and backbones of 3-SAT and maximum 3-SAT[C]∥Proceedings of the 7th International Conference on Principles and Practice of Constraint Programming. London: Springer, 2001: 153-167. 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 [4]　YANNAKAKIS M. Node and edge deletion NP-complete problems[C]∥Proceedings of the 10th Annual ACM Symposium on Theory of Computing. New York: ACM, 1978: 253-264. 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 [5]　DUBOIS O, DEQUEN G. A backbone search heuristic for efficient solving of hard 3-SAT formulae[C]∥Proceedings of the 17th International Joint Conference on Artificial Intelligence. San Francisco: Morgan Kaufmann, 2001: 248-253. 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 [6]　SLANEY J, WALSH T. Backbones in optimization and approximation[C]∥Proceedings of the 17th Interna-tional Joint Conference on Artificial Intelligence. San Francisco: Morgan Kaufmann, 2001: 254-259. 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 [7]　KILBY P, SLANEY J, THIEBAUX S, et al. Backbones and backdoors in satisfiability[C]∥Proceedings of the 20th National Conference on Artificial Intelligence. Pittsburgh: AAAI, 2005: 1368-1373. 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 [8]　WILLIAMS R, GOMES C P, SELMAN B. Backdoors to typical case complexity[C]∥Proceedings of the 18th International Joint Conference on Artificial Intelligence. San Francisco: Morgan Kaufmann, 2003: 1173-1178. 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 [9]　NISHIMURA N, RAGDE P, SZEIDER S. Detecting backdoor sets with respect to horn and binary clauses[C]∥Proceedings of the 17th International Conference on Theory and Applications of Satisfiability Testing. Vancouver: Elsevier, 2004: 96-103. [10]　SAMER M, SZERDER S. Backdoor trees[C]∥Proceedings of the 23rd National Conference on Artificial Intelligence. Chicago: AAAI, 2008: 363-368. 　　　　 [11]　RUAN Y, KAUTZ H, HORVITZ E. The backdoor key: a path to understanding problem hardness[C]∥Proceedings of the 19th National Conference on Artificial Intelligence. [S.l.]: AAAI, 2004: 124-130. 　　　 [12]　SELMAN B, KAUTZ H, COHEN B. Noise strategies for improving local search[C]∥Proceedings of the 12th National Conference on Artificial Intelligence. Seattle: AAAI, 1994: 337-343. 　　　　 [13]　MCALLESTER D, SELMAN B, KAUTZ H. Evidence for invariants in local search[C]∥Proceedings of the 14th National Conference on Artificial Intelligence and 9th Conference on Innovative Applications of Artificial Intelligence. [S.l.]: AAAI, 1997: 321-326. 　　　　 [14]　MOSKEWICZ M W, MADIGAN C F, ZHAO Y. Chaff: Engineering an efficient SAT solver[C]∥Proceedings of the 38th Annual Design Automation Conference. New York: ACM, 2001: 530-535. 　　　　 [15]　BRAUNSTEIN A, MEZARD M, ZECCHINA R. Survey propagation: an algorithm for satisfiability[J]. Random Structures and Algorithms, 2005, 27(2): 201-226. 　　 [16]　MANEVA E, MOSSEL E, WAINWRIGHT M. A new look at survey propagation and its generalizations[J]. Journal of the ACM, 2007, 54(4): 1089-1098. 　　　　 [17]　秦永彬,许道云. 警示传播算法的原理分析及算法改进[J]. 计算机工程与应用,2010,46(19): 1-6. 　　　　QIN Yongbin, XU Daoyun. Analysis and improvement of warning propagation algorithm[J]. Computer Engineering and Applications, 2010, 46(19): 1-6. 　　　　 [18]　邵明,李光辉,李晓维. 求解可满足问题的调查传播算法以及步长的影响规律[J]. 计算机学报,2005,28(5): 849-855. 　　　　SHAO Ming, LI Guanghui, LI Xiaowei. Survey propagation algorithm for SAT and its performance dominated by step length[J]. Chinese Journal of Computers, 2005, 28(5): 849-855. 　　　　 [19]　李韶华,张健. Survey propagation:一种求解SAT的高效算法[J]. 计算机科学,2005,32(1): 132-137. 　　　　LI Shaohua, ZHANG Jian. Survey propagation: an effective algorithm for solving SAT[J. Journal of Computer Sciense, 2005, 32(1): 132-137. 　　　　 [20]　KSCHISCHANG F, FREY B, LOELIGER H. Factor graph and the sum-product algorithm[J]. Information Theory, 2001, 47（1）: 498-519. 　　　　 [21]　FEIGE U, MOSSEL E, VILENCHIK D. Complete convergence of message passing algorithms for some satisfiability problems[J]. Lecture Notes in Computer Science, 2006, 4110（1）: 339-350. 　　　　 [22]　王晓峰,许道云. 求解公式关键文字集的信息传播算法[J]. 山东大学学报:工学版,2011,41(3): 1-6. 　　　　WANG Xiaofeng, XU Daoyun. A message propagation algorithm computing set of key literals of a formula[J]. Journal of Shandong University: Engineering Science, 2011, 41(3): 1-6.
    • 相关文章
    • 施引文献
  • 附加材料(0)
  • 加载中
WeChat 点击查看大图
计量
  • 文章访问数:  1275
  • HTML全文浏览量:  63
  • PDF下载量:  615
  • 被引次数: 0
出版历程
  • 收稿日期:  2011-03-11
  • 刊出日期:  2012-02-25

目录

    /

    返回文章
    返回

    Copyright © 2009 西南交通大学学报

    地址：四川省成都市郫都区犀安路999号西南交通大学犀浦校区《西南交通大学学报》编辑部

    电话：028-66367562传真：028-66366552Email：xbz@home.swjtu.edu.cn

    本系统由 北京仁和汇智信息技术有限公司 开发 技术支持： info@rhhz.net