中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 数学与系统科学研究院
  3. 中国科学院数学与系统科学研究院
  4. 应用数学研究所
Clustering phase of a general constraint satisfaction problem model d-k-CSP

文献类型：期刊论文

作者Xu, Wei1; Gong, Fuzhou2; Zhou, Guangyan3
刊名PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS
出版日期2020
卷号537页码:15
ISSN号0378-4371
关键词Constraint satisfaction problem Solution space structure Clustering phase transition Problem hardness Belief propagation
DOI10.1016/j.physa.2019.122708
英文摘要Relation between problem hardness and solution space structure is an important research aspect. Model d-k-CSP is a random model of constraint satisfaction problem, which generates very hard instances when r = 1 or r is near 1, where r represents normalized constraint density. We study the clustering phase of the model, and find that if r is below and close to 1, the solution space contains many widely distributed and well-separated small frozen clusters, which should be the reason why the generated instances are hard to solve. (C) 2019 Elsevier B.V. All rights reserved.
资助项目Fundamental Research Funds for the Central Universities[FRF-TP-16-065A1] ; National Natural Science Foundation of China[11801028] ; National Natural Science Foundation of China[61702019]
WOS研究方向Physics
语种英语
出版者ELSEVIER
WOS记录号WOS:000501641200067
源URL[http://ir.amss.ac.cn/handle/2S8OKBNM/50421]  
专题应用数学研究所
通讯作者Zhou, Guangyan
作者单位1.Univ Sci & Technol Beijing, Sch Math & Phys, Beijing 100083, Peoples R China
2.Chinese Acad Sci, Acad Math & Syst Sci, Inst Appl Math, Beijing 100190, Peoples R China
3.Beijing Technol & Business Univ, Dept Math, Beijing 100048, Peoples R China
推荐引用方式
GB/T 7714		 Xu, Wei,Gong, Fuzhou,Zhou, Guangyan. Clustering phase of a general constraint satisfaction problem model d-k-CSP[J]. PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS,2020,537:15.
APA Xu, Wei,Gong, Fuzhou,&Zhou, Guangyan.(2020).Clustering phase of a general constraint satisfaction problem model d-k-CSP.PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS,537,15.
MLA Xu, Wei,et al."Clustering phase of a general constraint satisfaction problem model d-k-CSP".PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS 537(2020):15.

入库方式： OAI收割

来源：数学与系统科学研究院

浏览0
下载0
收藏0
其他版本

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