中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 数学与系统科学研究院
  3. 中国科学院数学与系统科学研究院
  4. 应用数学研究所
Performances of pure random walk algorithms on constraint satisfaction problems with growing domains

文献类型：期刊论文

作者Xu, Wei1; Gong, Fuzhou2
刊名JOURNAL OF COMBINATORIAL OPTIMIZATION
出版日期2016-07-01
卷号32期号:1页码:51-66
关键词Constraint satisfaction problems Model RB Random walk Local search algorithms
ISSN号1382-6905
DOI10.1007/s10878-015-9891-9
英文摘要The performances of two types of pure random walk (PRW) algorithms for a model of constraint satisfaction problem with growing domains (called Model RB) are investigated. Threshold phenomenons appear for both algorithms. In particular, when the constraint density is smaller than a threshold value , PRW algorithms can solve instances of Model RB efficiently, but when is bigger than the , they fail. Using a physical method, we find out the threshold values for both algorithms. When the number of variables is large, the threshold values tend to zero, so generally speaking PRW does not work on Model RB. By performing experiments, we show that PRW strategy cannot do better than other fundamental strategies.
WOS研究方向Computer Science ; Mathematics
语种英语
WOS记录号WOS:000379033200004
出版者SPRINGER
源URL[http://ir.amss.ac.cn/handle/2S8OKBNM/23091]  
专题应用数学研究所
通讯作者Xu, Wei
作者单位1.Beihang Univ, Sch Math & Syst Sci, Beijing 100191, Peoples R China
2.Chinese Acad Sci, Acad Math & Syst Sci, Inst Appl Math, Beijing 100190, Peoples R China
推荐引用方式
GB/T 7714		 Xu, Wei,Gong, Fuzhou. Performances of pure random walk algorithms on constraint satisfaction problems with growing domains[J]. JOURNAL OF COMBINATORIAL OPTIMIZATION,2016,32(1):51-66.
APA Xu, Wei,&Gong, Fuzhou.(2016).Performances of pure random walk algorithms on constraint satisfaction problems with growing domains.JOURNAL OF COMBINATORIAL OPTIMIZATION,32(1),51-66.
MLA Xu, Wei,et al."Performances of pure random walk algorithms on constraint satisfaction problems with growing domains".JOURNAL OF COMBINATORIAL OPTIMIZATION 32.1(2016):51-66.

入库方式： OAI收割

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

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

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