Page 139 - 4495

«лексикографічно краще» має такого ж відповідника і в звичайній ле-
ксикографічній CSP.
Локальна напівкільцева CSP
Локальна напівкільцева CSP може бути трасформована в задачу,

строго еквівалентну ваговій CSP при використанні поліноміального
часового удосконалення. Нехай { ,u  ,u }. Множина U непорівнюва-
1 m
них елементів в кожній напівкільцевій CSP з кількістю рівнів h. Не-
хай також n - максимальне число входжень пари ru для будь-якого r
i i
із мультимножини т A в будь-якому напівкільцевому значенні
 j j
A  ( ,A  , A .
)
1 h
Позначимо найбільше значення серед всіх чисел r будь -якої па-
ри ru і з мультимножинами т A будь – якого напівкільцевого зна-
i j j
 
)
)
чення A  ( ,A  , A змінною e. Тоді кожне значення A  ( ,A  , A мо-
1 h 1 h
же бути перетворене у a p (h 1)   a p a , де p   m n e, а
1 h 1 h i 1 i
i 
a  ru A i [r card ( , )]ru A . У даному випадку оптимальний кортеж ло-
i
кальної напівкільцевої CSP не тільки мінімізує функцію помилки
окремого обмеження на кожному рівні, але й сумарну вагу всіх неза-

доволених обмежень. Локальна напівкільцева CSP не може бути за-
дана як удосконалення лексикографічної напівкільцевої CSP тому, що
не порівнювані напівкільцеві елементи в локальній напівкільцевій

CSP повинні також бути непорівнюваними в напівкільцевій ваговій
CSP, де напівкільце повністю впорядковане.

Питання для самоконтролю

1. Що таке преференції в системах обмежень?

2. Чим визначаються сильні обмеження?
3. Чим визначаються слабкі обмеження?
4. Що таке посилення системи обмежень?
5. Що таке послаблення системи обмежень?

6. В чому полягає часткове впорядкування обмежень?
7. Що таке компаратор?
8. Що таке композиційна модель на основі обмежень?

9. Як оцінюється ефективність ієрархії обмежень?
10. Що таке розв’язок ієрархії обмежень?
11. Що таке рефлективність системи обмежень?
12. Як впорядковуються обмеження в системі та ієрархії?

139