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

doi:10.1007/s10878-015-9891-9

CORC > 数学与系统科学研究院 > 中国科学院数学与系统科学研究院 > 应用数学研究所

	Performances of pure random walk algorithms on constraint satisfaction problems with growing domains
	Xu, Wei 1; 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
DOI	10.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
语种	英语
出版者	SPRINGER
WOS记录号	WOS:000379033200004
内容类型	期刊论文
源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.