Page 109 - 4495

Таблиця 1 – Специфічні класи оцінної CSP

Модель E  # T 
CSP 0  1 ,   0 1
Вагова CSP {+∞}     0

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

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

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

ставлена тривіальною булевою сіткою. E  0,1 ,1 0  T, #   (або
min ). Всі обмеження мають оцінки T , тобто функція  дійсна для
E P
кожного присвоєння з хоча б одним знехтуваним обмеженням T як
максимальним елементом. Оцінка CSP відповідає  (повне задово-

лення) тільки в тому випадку, якщо хоча б одне присвоєння, в якому
задоволене кожне обмеження. Операція  ідемпотентна та строго мо-
нотонна водночас – множина оцінок містить тільки два елементи 0 та

1.
Вагова CSP
Специфікація структури оцінювання відповідає (     , , ,   ,0).

Для MAX – CSP оцінки всіх обмежень дорівнюють 1. Ваги знехтува-
них обмежень додаються для кожного присвоєння, а оцінка всієї за-

дачі дається за присвоєнням, в якого ця сума найменша. Операціями
 строго монотонна.
Імовірнісна CSP
У цій моделі кожному обмеженню надається ймовірність його іс-

нування в реальній задачі. Оцінка  повинна бути сформована шля-
P
E
хом додавання ймовірностей, що обмеження, знехтувані в даному
присвоєнні, не існують у реальній задачі. Оскільки всі обмеження не-
)
залежні, то:  ( )   (1 p , де p - ймовірність існування об-
E P (c C ) ( |  ) c
меження cв реальній задачі. Кожне обмеження має оцінку ( c 1)  p .
Оцінки комбінуються операцією . Обмеження з ймовірністю 1 не
можуть бути знехтувані, тобто T  0. Результуючий порядок  у

E  0 , 1 повинен відповідати операції . Серед всіх оцінювань присво-
єнь, вибирають те, в якого ймовірність є найбільшою. Загальна струк-

тура оцінювання задається 1( 0 , , ) 1 , 0 , , . Операціями  строго монотон-

109