Publication details
Limited Assignments: A New Cutoff Strategy for Incomplete Depth
-First Search
| Basic information | |
|---|---|
| Original title: | Limited Assignments: A New Cutoff Strategy for Incomplete Depth-First Search |
| Authors: | Roman Barták, Hana Rudová |
| Further information | |
|---|---|
| Citation: | BARTÁK, Roman - RUDOVÁ, Hana. Limited Assignments: A New Cutoff Strategy for Incomplete Depth-First Search. In Proceedings of the 2005 ACM symposium on Applied computing. New York, NY, USA : ACM Press, 2005. ISBN 1-58113-964-0, pp. 288-292. |
| Original language: | English |
| Field: | Informatika |
| WWW: |  PDF |
| Type: | Article in Proceedings |
| Keywords: | search; constraint programming |
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:
