Page 94 - 4495

вольняє першу і третю вимогу разом з другою подією. Хоча ми маємо
переключені другу і третю події і порушені два обмеження кожне з
ваговим коефіцієнтом 2. Це буде результатом присвоєння з ваговим
коефіцієнтом 4. Буть-які інші присвоєння можуть порушити також

першу чи другу вимогу, які є результатом нижчого ступеня задово-
лення присвоєння (найменший рівний 5), тобто ми отримали
розв’язок зі зв’язністю 4.

Імовірнісне задоволення обмежень

У попередньому підході основна увага приділялася необхідності
задоволення накладених обмежень в формі їх вагових коефіцієнтів,

імовірнісний підхід [57] має на меті розгляд невизначеності щодо ре-
левантності певних обмежень в досліджуваній проблемі. Класичним
прикладом є переміщення робота в недостатньо відомому середови-

щі, коли він знає, що він може натрапити на перешкоду в точці
( , )x y .Тоді мова йтиме про вираження ступеня імовірності, релевант-

ності обмеження щодо простору переміщення робота.

Означення проблеми

Означення 4 (обмеження, проблема). Імовірнісна проблема за-

доволення обмежень P складається з множини змінних V , їх доме-
pr
нів D , і множини імовірнісних обмежень C  {( ,c p ),...,( ,c p )} де
pr 1 1 m m
C   c є множиною класичних обмежень і p - імовірність, що об-
i
i
i
меження c є обмеженням інтерпретації CSP, де P  ( , , )C V D маємо
i
C
C  тобто Pr(c  C )  p , Pr(c  C ) 1 p  .
i i i i
Припускають, що кожен p є більшим за 0 (не релевантні обме-
i
ження не розглядаються взагалі) і релевантність двох відмінних об-

межень розглядають як дві незалежні імовірнісні події. Строгість ко-
жного з таких обмежень може бути послаблена незалежно від інших
обмежень, тобто, імовірность, що c та c з C є:
i j
Pr((c  C ) (c  C )) Pr(c  C ) Pr(c  C )  p  p .
i j i j i j
Імовірнісна інтерпретація проблеми задоволення обмежень поля-
гає в виділенні певних CSP – задач разом з множиною присвоєнь які є
прийнятними для даних формулювань пошукових задач. Проте, важ-

ливим у даному випадку стає саме питання отримання послідовних
пошукових проблем .

94