Limited Assignments: A New Cutoff Strategy for Incomplete Depth-First Search

Warning

This publication doesn't include Faculty of Sports Studies. It includes Faculty of Informatics. Official publication website can be found on muni.cz.

Authors	BARTÁK Roman RUDOVÁ Hana
Year of publication	2005
Type	Article in Proceedings
Conference	Proceedings of the 2005 ACM symposium on Applied computing
MU Faculty or unit	Faculty of Informatics
Citation
Web	PDF
Field	Informatics
Keywords	search; constraint programming
Description	In this paper, we propose an extension of three incomplete depth-first search techniques, namely depth-bounded backtrack search, credit search, and iterative broadening, towards producing incomplete solutions. We also propose a new cutoff strategy for incomplete depth-first search motivated by a human style of problem solving. This technique, called limited assignment number (LAN) search, is based on limiting the number of attempts tried to assign a value to the variable. A linear worstcase time complexity of LAN Search leads to promising stable time behavior in all accomplished experiments. The techniques are studied in the context of constraint satisfaction problems.
Related projects:	Highly Parallel and Distributed Computing Systems