ITP OpenIR  > 理论物理所2011年知识产出
A message-passing approach to random constraint satisfaction problems with growing domains
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.
2011
发表期刊JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT
ISSN1742-5468
期号*页码:P02019
摘要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.
部门归属[Xu, Ke] Beihang Univ, State Key Lab Software Dev Environm, Beijing 100191, Peoples R China; [Zhao, Chunyan; Zheng, Zhiming] Beihang Univ, Sch Math & Syst Sci, Beijing 100191, Peoples R China; [Zhou, Haijun] Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China; [Zhao, Chunyan; Zheng, Zhiming] Beihang Univ, LMIB, Beijing 100191, Peoples R China
关键词Exact Phase-transitions Random K-sat Satisfiability Threshold Algorithm
学科领域Physics
资助者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]
URL查看原文
收录类别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]
WOS记录号WOS:000287802800023
引用统计
被引频次:3[WOS]   [WOS记录]     [WOS相关记录]
文献类型期刊论文
条目标识符http://ir.itp.ac.cn/handle/311006/14422
专题理论物理所2011年知识产出
通讯作者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)
暂无评论
 

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