Page 97 - 4495

необхідній мірі. Навіть якщо такий розподіл ймовірності класифіку-
ється як розв'язок, то їх якісна характеристика виглядає недостатньо
обґрунтованою, оскільки ступінь SN ( ) становить 0,8.

Досліджування послідовності задачі на основі обмежень
Означення 9 (ступінь послідовності). Ступінь послідовності
ймовірнісної проблеми задоволення обмежень V, D, C  будемо озна-

чати як максимум для 1 SN ( )для кожного  що задовольняє С . Сту-
пенем непослідовності I вважатимемо його доповнення до 1.

Ступінь непослідовності ймовірнісної задачі CSP може бути оці-
нена шляхом ступеня преференцій обмеження, яке не задовольняєть-
ся в жодному з присвоєнь   . Можна показати, що ступінь непо-
v
слідовності дорівнює найменшому ступеню необхідності незадоволе-

ного обмеження c false для всіх ймовірнісних розподілів, що задово-

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

ності, що задовольняє множину обмеження C .
Твердження 1 (ступінь задоволення обмеження). Нехай

P  (V ,D ,C ) – ймовірнісна задача CSP, означимо максимальний ймо-

вірнісний розподіл p * P на  як:
v
" qОQ :p * ( )q = min (1 w ,1)-
v P i
((c w ) C) ( |qО Щ = Ш c )
i i i
Тоді для будь-якого ймовірнісного розподілу  на  ,  задово-
v
*
льняє P тоді і тільки тоді, якщо    .
 P
 ( , )c w  C : | ( , )c w   N ( )c  w  min (1  ( ),1) w 
i i i i  i i ( v ) ( |  ) c i
( c , w ) C   так як |   c : ( )  1  w
i i V i i
" ОQq V : ( )Јp q min ((c i w ) C) ( |О Щ = Шq c) (1 w ,1)- i Юp ( )Јq p * P ( )q
i
Наближений максимальний ймовірнісний розподіл оцінює, до

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

Приклад 3 Розглянемо ймовірнісну задачу на основі обмежень P
з прикладу 3. Будемо обчислювати ймовірнісний розподіл  для всіх
*
P
   v . Спочатку отримаємо  * (( 3 , 2 , 1 ))  6 . 0 відповідно із незадоволе-
P
ного обмеження С . Друге  P * ( )  4 . 0 отримаємо від всіх присвоєнь,
які задовольняють a і не задовольняють b, наприклад,   ) 2 , 2 , 1 ( . Всі

97