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

Warning

This publication doesn't include Faculty of Arts. 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:

You are running an old browser version. We recommend updating your browser to its latest version.