ITP OpenIR  > 理论物理所科研产出  > SCI论文
Zhao, CY; Zhou, HJ; Zheng, ZM; Xu, K; Xu, K (reprint author), Beihang Univ, State Key Lab Software Dev Environm, Beijing 100191, Peoples R China.
A message-passing approach to random constraint satisfaction problems with growing domains
发表期刊JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT
语种英语
关键词Exact Phase-transitions Random K-sat Satisfiability Threshold Algorithm
摘要Message-passing algorithms based on belief propagation (BP) are implemented on a random constraint satisfaction problem (CSP) referred to as model RB, which is a prototype of hard random CSPs with growing domain size. In model RB, the number of candidate discrete values (the domain size) of each variable increases polynomially with the variable number N of the problem formula. Although the satisfiability threshold of model RB is exactly known, finding solutions for a single problem formula is quite challenging and attempts have been limited to cases of N similar to 10(2). In this paper, we propose two different kinds of message-passing algorithms guided by BP for this problem. Numerical simulations demonstrate that these algorithms allow us to find a solution for random formulas of model RB with constraint tightness slightly less than p(cr), the threshold value for the satisfiability phase transition. To evaluate the performance of these algorithms, we also provide a local search algorithm (random walk) as a comparison. Besides this, the simulated time dependence of the problem size N and the entropy of the variables for growing domain size are discussed.
2011
ISSN1742-5468
期号*页码:P02019
学科领域Physics
收录类别SCI
项目资助者National Key Basic Research Project of China [200532CB1092]; NSFC [60473109, 60973033] ; National Key Basic Research Project of China [200532CB1092]; NSFC [60473109, 60973033] ; National Key Basic Research Project of China [200532CB1092]; NSFC [60473109, 60973033] ; National Key Basic Research Project of China [200532CB1092]; NSFC [60473109, 60973033]
引用统计
被引频次:3[WOS]   [WOS记录]     [WOS相关记录]
文献类型期刊论文
条目标识符http://ir.itp.ac.cn/handle/311006/14422
专题理论物理所科研产出_SCI论文
通讯作者Xu, K (reprint author), Beihang Univ, State Key Lab Software Dev Environm, Beijing 100191, Peoples R China.
推荐引用方式
GB/T 7714
Zhao, CY,Zhou, HJ,Zheng, ZM,et al. A message-passing approach to random constraint satisfaction problems with growing domains[J]. JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT,2011(*):P02019.
APA Zhao, CY,Zhou, HJ,Zheng, ZM,Xu, K,&Xu, K .(2011).A message-passing approach to random constraint satisfaction problems with growing domains.JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT(*),P02019.
MLA Zhao, CY,et al."A message-passing approach to random constraint satisfaction problems with growing domains".JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT .*(2011):P02019.
条目包含的文件
文件名称/大小 文献类型 版本类型 开放类型 使用许可
A message-passing ap(810KB) 开放获取使用许可请求全文
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[Zhao, CY]的文章
[Zhou, HJ]的文章
[Zheng, ZM]的文章
百度学术
百度学术中相似的文章
[Zhao, CY]的文章
[Zhou, HJ]的文章
[Zheng, ZM]的文章
必应学术
必应学术中相似的文章
[Zhao, CY]的文章
[Zhou, HJ]的文章
[Zheng, ZM]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。