Název:
Filtrační algoritmy pro tabulární podmínky
Překlad názvu:
Filtering Algorithms for Tabular Constraints
Autoři:
Molnár, Martin ; Barták, Roman (vedoucí práce) ; Surynek, Pavel (oponent) Typ dokumentu: Diplomové práce
Rok:
2010
Jazyk:
eng
Abstrakt: [eng][cze] The thesis studies an implementation of arc-consistency filtering algorithms for constraints defined in extension. We propose a new concept of binarization for decomposing high-arity ad-hoc constraints into networks of binary constraints. A theory proving correctness of the binarization is developed. We study the existing algorithms from the perspective of our binarization concept and propose possible binarization schemes for ad-hoc constraints defined in some of the common forms. In the thesis we also propose the filtering algorithms for the elementary constraints. A compound propagator then uses the elementary constraint filtering algorithms to propagate over the high-arity constraint. Finally, we experimentally evaluate the proposed approaches on constraints generated when solving the planning problems.Předložená práce se zabývá implementací filtračních algoritmů hranové konzistence pro extenzivně definované podmínky. Zavádíme zde nový koncept binarizace pro rozkládání více-árních ad hoc podmínek na síť binárních podmínek. Je zde také rozpracována teorie pro dokázání správnosti této binarizace. V práci studujeme existující algoritmy z pohledu našeho konceptu binarizace a navrhujeme binarizace pro ad hoc podmínky definované vybranými běžnými způsoby. V práci také navrhujeme filtrační algoritmy pro dílčí podmínky. Složený propagátor pak používá tyto dílčí filtrační algoritmy pro propagaci přes více-ární podmínky. Konečně, navrhované postupy experimentálně ověřujeme na podmínkách generovaných plánovacími.