A message-passing approach to random constraint satisfaction problems with growing domains
文献类型：期刊论文
| 作者 | Zhou, HJ
|
| 刊名 | JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT
 |
| 出版日期 | 2011 |
| 期号 | *页码:P02019 |
| 关键词 | EXACT PHASE-TRANSITIONS RANDOM K-SAT SATISFIABILITY THRESHOLD ALGORITHM |
| ISSN号 | 1742-5468 |
| 通讯作者 | Xu, K (reprint author), Beihang Univ, State Key Lab Software Dev Environm, Beijing 100191, Peoples R China. |
| 英文摘要 | 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. |
| 学科主题 | Physics |
| 收录类别 | SCI |
| 资助信息 | National Key Basic Research Project of China [200532CB1092]; NSFC [60473109, 60973033] |
| 原文出处 | http://dx.doi.org/10.1088/1742-5468/2011/02/P02019 |
| 语种 | 英语 |
| WOS记录号 | WOS:000287802800023 |
| 公开日期 | 2013-05-17 |
| 源URL | [http://ir.itp.ac.cn/handle/311006/14422]  |
| 专题 | 理论物理研究所_理论物理所1978-2010年知识产出 |
| 推荐引用方式 GB/T 7714 | Zhou, HJ. A message-passing approach to random constraint satisfaction problems with growing domains[J]. JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT,2011(*):P02019. |
| APA | Zhou, HJ.(2011).A message-passing approach to random constraint satisfaction problems with growing domains.JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT(*),P02019. |
| MLA | Zhou, HJ."A message-passing approach to random constraint satisfaction problems with growing domains".JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT .*(2011):P02019. |
入库方式： OAI收割
来源：理论物理研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。