Performances of pure random walk algorithms on constraint satisfaction problems with growing domains

doi:10.1007/s10878-015-9891-9

CSpace > 应用数学研究所

	Performances of pure random walk algorithms on constraint satisfaction problems with growing domains
	Xu, Wei 1; Gong, Fuzhou2
	2016-07-01
发表期刊	JOURNAL OF COMBINATORIAL OPTIMIZATION
ISSN	1382-6905
卷号	32 期号:1 页码:51-66
摘要	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.
关键词	Constraint satisfaction problems Model RB Random walk Local search algorithms
DOI	10.1007/s10878-015-9891-9
语种	英语
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Interdisciplinary Applications ; Mathematics, Applied
WOS记录号	WOS:000379033200004
出版者	SPRINGER
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/23092
专题	应用数学研究所
通讯作者	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.