Page 103 - 4495

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

тежу (d ,...,d ) в задачі P рівний ступеневі задоволення обмеження,
1 n 
яке задовольняється цим кортежем найменше. Серед всіх цих корте-
жів (повних кортежів) потрібно шукати ті, в яких ступінь задоволення
є найбільшим.

Означення 19 (розв’язок). Розв’язком нечіткої задачі CSP P є

таке присвоєння, в якого степінь задоволення найбільший, тобто

max  ( ,...,d d )
C 1 n
( ,..., n d ) D  ... D n
d
1
1
Обмеження у нечіткій CSP P не вимагають нормалізації, що

означає, що вся задача P не мусить бути нормалізована і не повинно

існувати кортежу зі ступенем задоволення, рівним одиниці. Маючи
степені задоволення для всіх присвоєнь у P можна визначити ступінь

її послідовності (повноти).
Означення 20 (степінь послідовності) Нехай задана нечітка за-

дача CSP P  з множиною обмеження C , змінних V  v ,..., v n  та їх до-
1
менів D  D ...  D . Ступінь послідовності C для нечіткої CSP P ви-
1 n 
значається за формулою:
C (P  max  C ( ,...,d 1 d n ).
)

d
( ,..., n d ) D  ... D
1 1 n
Ступенем послідовності (PI )є доповнення C до 1:

)
I (P ) 1  C (P .
 
Як бачимо, ступінь послідовності дорівнює ступеневі задоволен-
ня розв’язку нечіткої ймовірнісної задачі CSP. Ступінь послідовності
може також бути визначений за допомогою проекцій на пусту мно-

жину змінних:
C ( )P  C  .
 
Така проекція оцінює, в якій мірі пустий кортеж може бути роз-
ширений до повного присвоєння, яке задовольняє комбінацію всіх
обмежень. Це обчислюється ступенем послідовності.

Приклад 5 (продовження). Розв’яжемо задачу P: По-перше, не-
обхідно знати ступені задоволення всіх кортежів: (3, 3) має ступінь
0,6, кортеж: (2, 3) та (3, 2) мають ступінь задоволення 0,5, кортеж (2,
2) – 0,4, для всіх інших кортежів ступінь задоволення дорівнює 0.3,

103