Original title:
Dynamické problémy s podmínkami
Translated title:
Dynamic Constraint Satisfaction Problems
Authors:
Surynek, Pavel ; Rudová, Hana (referee) Document type: Rigorous theses
Year:
2006
Language:
cze Abstract:
[cze][eng] Problémy splňování podmínek (CSP) jsou s vzhledem k možnostem praktického použití velmi zkoumanou oblastí kombinatorického prohledávání (optimalizace). CSP je definován množinou proměnných, kterým mají být přiřazeny hodnoty, a množinou podmínek, jež omezují tato přiřazení. Jelikož mnoho praktických problémů vyžaduje dynamické prostředí, byl koncept CSP rozšířen na dynamický CSP (DCSP), kde se množina proměnných a/nebo podmínek může měnit během řešícího procesu. S ohledem na prohledávací algoritmy jsou problémy splňování podmínek obvykle nejprve zjednodušovány pomocí konzistenčních (filtračních) technik, jako je například hranová konzistence. V této práci jsme se zaměřili na studium otázky udržování hranové konzistence v DCSP. Navrhli jsme několik nových algoritmů pro dynamickou hranovou konzistenci, které představují lepší kompromis mezi paměťovými a časovými požadavky v porovnání s podobnými existujícími algoritmy, jako jsou DNAC-4, DNAC-6 a AC|DC. Hlavním výsledkem práce je pak nový algoritmus, který překonává i dosud nejrychlejší existující algoritmus pro udržování hranové konzistence v dynamických problémech DNAC-6. Aby bylo možné provádět výkonnostní testy, vyvinuli jsme knihovnu SPlan napsanou v C++. Knihovna je určena pro řešení DCSP a nové algoritmy jakož i srovnatelné existující jsou implementovány...Constraint satisfaction problems (CSPs) are a type of combinatorial (optimization) problems that invite much interest in many practical applications. CSP is defined by a set of variables, to which values must be assigned, and a set of constraints that restrict these assignments. Since many problems of practical interest require a dynamic environment, the model of CSP was extended to a dynamic CSP (DCSP), in which the set of variables and/or constraints can be modified during the constraint resolution process. To simplify the constraint satisfaction problem for search algorithms, consistency (filtering) techniques like arc-consistency are usually applied. In this thesis, we study the problem of maintaining arc-consistency in DCSPs. We propose several new dynamic arc-consistency algorithms that yield a better compromise between time and space in comparison to similar existing algorithms like DNAC-4, DNAC-6 and AC|DC. The highlight of the work is a new algorithm that outperforms so far fastest algorithm for maintaining arc consistency in dynamic problems DNAC-6. In order to do performance experiments we have developed a library SPlan written in C++. This library solves DCSPs and the new algorithms as like as the comparable existing ones are implemented as a part of the library. Experimental results on randomly...
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/6172