Iterative Forward Search: Combining Local Search with Maintaining Arc Consistency and a Conflict-based Statistics

MÜLLER, Tomáš; Roman BARTÁK a Hana RUDOVÁ. Iterative Forward Search: Combining Local Search with Maintaining Arc Consistency and a Conflict-based Statistics. In Local Search Techniques in Constraint Satisfaction. Toronto, Kanada, 2004, s. 1-16.

Základní údaje

Originální název

Iterative Forward Search: Combining Local Search with Maintaining Arc Consistency and a Conflict-based Statistics

Název česky

Iterativní dopředné prohledávání: kombinace lokálního prohledávání s udržováním hranové konzistence a konfliktní statistika

Autoři

MÜLLER, Tomáš; Roman BARTÁK a Hana RUDOVÁ

Vydání

Toronto, Kanada, Local Search Techniques in Constraint Satisfaction, od s. 1-16, 16 s. 2004

---

Další údaje

Typ výsledku

Stať ve sborníku

Utajení

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

Odkazy

URL

Organizační jednotka

Fakulta informatiky

Klíčová slova anglicky

search algorithms; constraint satisfaction; timetabling

Štítky

constraint satisfaction, search algorithms, timetabling

---

Anotace

V originále

The paper presents an iterative forward search framework for solving constraint satisfaction and optimization problems. This framework combines ideas of local search, namely improving a solution by local steps, with principles of depth-first search, in particular extending a partial feasible assignment towards a solution. Within this framework, we also propose and study a conflict-based statistics and explanationbased arc consistency maintenance. To show the versatility of the proposed framework, the dynamic backtracking algorithm with maintaining arc consistency is presented as a special instance of the iterative forward search framework. The presented techniques are compared on random constraint satisfaction problems and a real-life lecture timetabling problem.

Česky

Práce prezentuje přístupy iterativního dopředného prohledávání pro řešení problémů splňování podmínek a optimalizačních problémů. Tato metoda kombinuje myšlenky lokálního prohledávání (zlepšování řešení lokálními kroky) s principy prohledávání do hloubky (rozšiřování částečného konzistentního přiřazení). V rámci tohoto přístupu také navrhujeme a studujeme konflitní statistiku a udržování hranové konzistence založené na vysvětlivkách. Jako ukázka všestrannosti přístupu je prezentován dynamický backtracking s udržováním hranové konzistence jako speciální instance iterativního dopředného prohledávání. Prezentované techniky jsou experimentálně prověřeny na náhodných problémech splňování podmínek a na reálném rozvrhovacím problému.