Publication details
Limited Assignments: A New Cutoff Strategy for Incomplete Depth-First Search
Authors | |
---|---|
Year of publication | 2005 |
Type | Article in Proceedings |
Conference | Proceedings of the 2005 ACM symposium on Applied computing |
MU Faculty or unit | |
Citation | |
Web | |
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: |