主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公English
2020-2021年专刊出版计划 微信服务介绍 最新一期:2020年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
王晓峰,许道云,韦立.随机可满足实例集上警示传播算法的收敛性.软件学报,2013,24(1):1-11
随机可满足实例集上警示传播算法的收敛性
Convergence of Warning Propagation Algorithms for Random Satisfiable Instances
投稿时间:2011-11-26  修订日期:2012-03-27
DOI:10.3724/SP.J.1001.2013.04213
中文关键词:  警示传播算法  收敛性分析  相变  可满足性问题
英文关键词:warning propagation algorithm  convergence analysis  phase transition  satisfiability problem
基金项目:国家自然科学基金(60863005, 61111130186); 贵州大学研究生创新基金(2011033)
作者单位E-mail
王晓峰 贵州大学 计算机科学系,贵州 贵阳 550025  
许道云 贵州大学 计算机科学系,贵州 贵阳 550025 dyxu@gzu.edu.cn 
韦立 贵州大学 计算机科学系,贵州 贵阳 550025  
摘要点击次数: 4882
全文下载次数: 4537
中文摘要:
      信息传播算法在求解随机kSAT问题时有惊人的效果,难解区域变窄.对于这种现象,至今缺少系统的理论解释.警示传播(warning propagation,简称WP)算法是一种基础的信息传播算法,为有效分析WP算法在随机kCNF公式上的收敛性,给出了随机kCNF公式因子图上圈存在的相变点.在随机kCNF公式产生模型G(n,k,p)中,取k=3,p=d/n2,因子图中圈存在的相变点为p=1/8n2.当d<1/8时,因子图中开始出现圈,且每个连通分支至多有一个圈,因子图中含圈的连通分支的数目以及圈的长度均与n无关.因此,因子图是由森林和一些含有唯一圈的连通分支构成.证明了WP算法在这些实例集上高概率收敛,并且给出了算法的迭代步数为O(logn+s),其中,s为连通分支的大小.
英文摘要:
      Message propagation algorithms are very effective in finding satisfying assignments for random kSAT instances and hard regions become more narrow. Unfortunately, this phenomenon is still lacks rigorous theoretical proofs. The Warning Propagation (WP) algorithm is the most basic message propagation algorithm. In order to analysis the WP algorithm convergence for random kCNF formulas, the study gives the sharp threshold point for the existence of cycles in the factor graph of random kCNF formulas, the threshold for the existence of cycles in model G(n,k,p) of random kCNF formulas is p=1/8n2 for k=3, p=d/n2. When d becomes asymptotically equal to 1/8, cycles begin to appear, but each component contains at most one cycle, the number of the components containing a single cycle and the length of cycle are a constant independent of n. Thus, the factor graph consists of a forest of trees plus a few components that have a single cycle. Then WHP (with high probability) after at most O(logn+s) iterations, WP converges on these instances. Here s is the size of the connected component.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利