Other formats:
BibTeX
LaTeX
RIS
@inproceedings{621787,
author = {Barták, Roman and Rudová, Hana},
address = {New York, NY, USA},
booktitle = {Proceedings of the 2005 ACM symposium on Applied computing},
keywords = {search; constraint programming},
language = {eng},
location = {New York, NY, USA},
isbn = {1-58113-964-0},
pages = {288-292},
publisher = {ACM Press},
title = {Limited Assignments: A New Cutoff Strategy for Incomplete Depth-First Search},
url = {http://www.fi.muni.cz/~hanka/publ/sac05.pdf},
year = {2005}
}
TY - JOUR
ID - 621787
AU - Barták, Roman - Rudová, Hana
PY - 2005
TI - Limited Assignments: A New Cutoff Strategy for Incomplete Depth-First Search
PB - ACM Press
CY - New York, NY, USA
SN - 1581139640
KW - search
KW - constraint programming
UR - http://www.fi.muni.cz/~hanka/publ/sac05.pdf
N2 - 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.
ER -
BARTÁK, Roman and Hana RUDOVÁ. Limited Assignments: A New Cutoff Strategy for Incomplete Depth-First Search. In \textit{Proceedings of the 2005 ACM symposium on Applied computing}. New York, NY, USA: ACM Press, 2005, p.~288-292. ISBN~1-58113-964-0.
|
