Page 116 - 4495

Модель A +  0 1

Класична CSP 0  1 ,   0 1

Вагова CSP {+∞} min    0

Ймовірнісна CSP 1 , 0 max  0 1

Імовірнісна CSP 1 , 0 min max 1 0

Нечітка CSP 1 , 0 max min 0 1

Лексикографічна
{┴} max т  
lex
CSP

Лексикографічна CSP
Лексикографічні CSP [62] були запропоновані як розширення до

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

Напівкільцеві значення для лексикографічної CSP відповідають
мультимножинам. Елемент напівкільце є або елементом , або муль-
тимножиною елементів над інтервалом 0 . Елемент  використову-
1 ,
ється в строго заборонених обмеженнях, а пуста мультимножина 

описує найкраще значення. Для комбінування обмежень використо-
вується об’єднання мультимножин т , розширення щоб задовольняти
 як абсорбуючий елемент. Проекція обмежень здійснюється за до-
помогою лексикографічного максимуму max над мультимножинами.
lex
Зв’язки між моделями

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

преференцію до кожного обмеження, тобто обмеження задається па-
рою ( wc , ), що складається з класичного обмеження с та певного типу
преференції w, що залежить від типу моделі. Нечітка, лексикографіч-

на та напівкільцева CSP подають обмеження як функцію, визначену
на кортежі значень, результатом обчислення якої є певний рівень
преференцій, тобто:

c : D ...  D  W ,
1 k
де D ,..., – домени відповідних змінних в обмеженні c, а W – множи-
D
1 k

116