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

Varování

Publikace nespadá pod Pedagogickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

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 RUDOVÁ Hana
Rok publikování	2005
Druh	Článek ve sborníku
Konference	Proceedings of the 2005 ACM symposium on Applied computing
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
www	PDF
Obor	Informatika
Klíčová slova	search; constraint programming
Popis	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,
Související projekty:	Vysoce paralelní a distribuované výpočetní systémy