D 2005

Limited Assignments: A New Cutoff Strategy for Incomplete Depth-First Search

BARTÁK, Roman a Hana RUDOVÁ

Základní údaje

Originální název

Limited Assignments: A New Cutoff Strategy for Incomplete Depth-First Search

Název česky

Limitovaná přiřazení: nová strategie přerušení pro neúplná prohledávání do hloubky

Autoři

BARTÁK, Roman (203 Česká republika) a Hana RUDOVÁ (203 Česká republika, garant)

Vydání

New York, NY, USA, Proceedings of the 2005 ACM symposium on Applied computing, od s. 288-292, 5 s. 2005

Nakladatel

ACM Press

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Odkazy

Kód RIV

RIV/00216224:14330/05:00014801

Organizační jednotka

Fakulta informatiky

ISBN

1-58113-964-0

Klíčová slova anglicky

search; constraint programming

Štítky

Změněno: 7. 2. 2006 22:45, doc. Mgr. Hana Rudová, Ph.D.

Anotace

ORIG CZ

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.

Česky

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,

Návaznosti

MSM0021622419, záměr
Název: Vysoce paralelní a distribuované výpočetní systémy
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy