Detailed Information on Publication Record
2005
Limited Assignments: A New Cutoff Strategy for Incomplete Depth-First Search
BARTÁK, Roman and Hana RUDOVÁBasic information
Original name
Limited Assignments: A New Cutoff Strategy for Incomplete Depth-First Search
Name in Czech
Limitovaná přiřazení: nová strategie přerušení pro neúplná prohledávání do hloubky
Authors
BARTÁK, Roman (203 Czech Republic) and Hana RUDOVÁ (203 Czech Republic, guarantor)
Edition
New York, NY, USA, Proceedings of the 2005 ACM symposium on Applied computing, p. 288-292, 5 pp. 2005
Publisher
ACM Press
Other information
Language
English
Type of outcome
Stať ve sborníku
Field of Study
10201 Computer sciences, information science, bioinformatics
Country of publisher
United States of America
Confidentiality degree
není předmětem státního či obchodního tajemství
References:
RIV identification code
RIV/00216224:14330/05:00014801
Organization unit
Faculty of Informatics
ISBN
1-58113-964-0
Keywords in English
search; constraint programming
Tags
Změněno: 7/2/2006 22:45, doc. Mgr. Hana Rudová, Ph.D.
V originále
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.
In Czech
Práce navrhuje rozšíření tří neúplných prohledávacích technik, a to hloubkou omezeného backtrackingu, kreditního prohledávání a iterativního rozšiřování tak, aby počítaly neúplná řešení. Dále je navržena nová strategie neúplného prohledávání do hloubky. Tato technika, nazývaná prohledávání s limitovaným počtem přiřazení je založena na omezení počtu zkoušených hodnot při přiřazování proměnné. Navržený algoritmus má lineární časovou složitost, což vede ke stabilnímu chování u všech experimentu prezentovaných v práci. Algoritmus je studován v kontextu problému splňování podmínek,
Links
| MSM0021622419, plan (intention) |
|