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

Označené pro přenos do RIV

Ne

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.