Dynamické problémy s podmínkami
Dynamic Constraint Satisfaction Problems
rigorous thesis (DEFENDED)
View/ Open
Permanent link
http://hdl.handle.net/20.500.11956/6172Identifiers
Study Information System: 44369
Collections
- Kvalifikační práce [11214]
Author
Referee
Rudová, Hana
Faculty / Institute
Faculty of Mathematics and Physics
Discipline
Theoretical computer science
Department
Department of Theoretical Computer Science and Mathematical Logic
Date of defense
29. 6. 2006
Publisher
Univerzita Karlova, Matematicko-fyzikální fakultaLanguage
Czech
Grade
Pass
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...