Page 96 - 4495

)
(c ) є більш значне, ніж задоволення обмеження (c .
1 2
Означення 7 (обмеження, проблема). Розглянемо як необхідні
значеня обмежень пару ( , )c w , де с є класичним обмеженням і w 1 , 0

- ступінь преференції.
Задача задоволення ймовірнісних обмежень P складається з

множини доменів змінних V , множини доменів D і множини необ-

хідних значень обмежень для.
Необхідні значення обмеження ( , )c w , у випадку якщо N ( c ) w ,

означає, що задоволення обмеження c є як мінімум w - необхідним і
обмеження (c повинне бути абсолютно задоволеним поки обмежен-
) 1 ,
ня ( ,0)c є повністю надлишковим, так як воно відображає, що необхід-
на міра c має бути як найменшою 0 , що є завжди істиною.

Означення 8 (розв’язок). Обмеження з необхідним значенням
(c , ) w задовольняє ймовірнісному розподілу  (позначається як

 | ( , )c w ) тоді і тільки тоді коли міра необхідності N , утворена 

над C , підтверджується для N ( c ) w .

Розв’язком ймовірнісної задачі на основі CSP V, D, C  є кожний
ймовірнісний розподіл  , такий що всі обмеження з необхідними

значеннями задовольняються. Будемо вважати, що в такому випадку
 задовольняє С.
У порівнянні з розв’язком класичної задачі на основі обмежень


CSP, ймовірні , ,A B C сний CSP не має множини послідовних присво-
єнь над V , але має множину p, яка дорівнює 1 для всіх   . Такий
v
ймовірнісний розподіл має мінімальний ступінь суб – нормалізації,

але він не задовольняє жодному з обмежень, тому що N ( c ) w є

правильним для всіх ,( wc ) . Це випливає з того факту, що присвоєння

 міститься в кожному обмеженні з властивістю   |  c , тобто

N (c)= min (1 p- ( ),1)q = 0
c)
p (qОQ v ) ( |qЩ = Ш
Оскільки ступінь необхідності всіх обмежень є вищим за 0 , цей
тривіальний ймовірнісний розподіл можна класифікувати як неуспі-

шний розв’язок.
Тепер ми розглянемо розподіл ймовірності  , який рівний 0,2
для всіх   . Тоді всі обмеження задовольняються, тому що всі
v
ступені необхідності рівні 0,8 і тому що це значення є достатнім щодо

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

96