Informace o publikaci
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 | |
| Rok publikování | 2004 |
| Druh | Článek ve sborníku |
| Konference | Local Search Techniques in Constraint Satisfaction |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | http://www.fi.muni.cz/~hanka/publ/lscs04.pdf |
| Klíčová slova | search algorithms; constraint satisfaction; timetabling |
| Popis | 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. |