Page 110 - 4495

на.
Ймовірнісна CSP
Обмеження з оцінкою необхідності у ймовірнісній CSP відпові-
дає обмеженню з оцінкою в оцінній CSP. Структура оцінювання зада-

ється кортежем 1( 0 , , ,  max, ) 0 , 1 , який є зіставним з очікуваною семанти-

кою ймовірнісного задоволення обмежень і оптимальне присвоєння –
присвоєння з мінімальним ступенем преференції найбільш важливого
знехтуваного обмеження.
Змінне оцінювання задоволення обмежень

Змінне VCSP – єдина модель, яка враховує преференції над змін-
ними, що показує можливий вплив таких преференцій. Цей підхід був
оглядово описаний у працях [68, 69] і застосований для щоденного

керуванням супутником, який спостерігав за планетою Земля. У да-
ному підході кожна змінна має деяку вагу, що відображає її важли-
вість. Ціль – утворити часткове присвоєння змінних задачі, яке б за-

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

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

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

Задоволення обмежень, засноване на півкільцях [70, 66, 71, 72]
належить до мета-моделей розв'язку задач задоволення обмежень з
преференціями. Модель має в своїй основі напівкільцеву структуру,
де в напівкільці визначається значення, які повинні бути асоційовані з

кожним кортежем значень домену змінної, а також дві операції в на-
півкільці (  і ), що застосовуються для моделювання проекцій та
комбінацій обмежень відповідно.

Напівкільця та напівкільцеві CSP
Означення 31 (структура). Напівкільце – це кортеж A , , ,0,1  , де

а) A – множина напівкільця;
б) 0,1A

в)  – комутативна, асоціативна операція і 0 – її базовий еле-
мент;
г)  – асоціативна та дистрибутивна відносно  операція та, 1 –

110