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: |