Page 95 - 4495
P. 95
Структура проблеми
Розглянемо імовірнісну CSP – проблему P ( , ,V D C ) з
pr pr
C {( ,c p ),...,( ,c p )} і позначимо P ( , , )V D C де C { ,..., }c c . Мно-
pr 1 1 m m 1 m
жина можливих обмежень C визначає структуру можливих CSP – за-
дач у класичному формулюванні, в яких тільки одна є задачею класу
. Маючи опис цієї структури, можемо описати підпроблему та супе-
рпроблему, що випливає з відношень у даній структурі.
P
Означення 5. Імовірність розподілу pr на 2 означимо наступ-
P
ним чином: P 2 є проблемою класу тоді і тільки тоді, якщо кож-
j
не обмеження P є важливим, а решта – ні.
j
Це означення разом з незалежними припущеннями дає:
|
}
Pr( ) Pr(P P ) P {p c C j {1 p c | (C C )},
j j j j j j j
де C і C є множинами обмежень в P та P відповідно.
j j
Приклад 2. Розглянемо імовірнісну CSP - проблему з двома змін-
ними A та B з доменами D {1,2} та D {1,2,3}. Імовірність обме-
A B
жень є:
( 1,0.5):( , ) {(1,2),(1,3),(2,1)}c A B
( 2,0.6):c A 1
( 3,0.7):(c A 2) (B 1)
Для прикладу, обчислення імовірності розподілу для проблеми
представленої { 2, 3}c c здійснюється таким чином:
Pr(( , ,{ 2, 3})V D c c P ) (1 p ) p p (1 0.5) 0.6 0.7 0.21 .
1 2 3
Занотуємо, що множина { 2, 3}c c є суперечливою. Приклад суміс-
ної проблеми може бути поданий множиною обмежень { 1, 2}c c . Отже,
як видно з прикладу, деякі проблеми в структурі проблеми можуть
бути суперечливими, тоді як інші – сумісними.
Означення 6. Сумісна підпроблема проблеми P, така, що кожна
її повна супер-проблема є суперечливою називається максимальною
сумісністю в P. Навпаки, реальна проблема може бути несумісною то
ймовірність того, що P є сумісною рівна:
P
)
Pr(Pconsistent {pr ( )|P j P 2 ,P consistent }. Нагадаємо, що
j
j
Pr(Pconsistent ) 1 , за властивістю імовірнісного розподілу.
Приклад 2 (продовження). Множина обмежень { , , }c c c , { , }c c
1 2 3 1 3
та { , }c c представляють типові проблеми, що є не сумісними. Двома
2 3
максимально сумісними під-пвиражає, що задоволення обмеження
95
