Page 118 - 4495

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

Окремі основні моделі (вагова, ймовірнісна, імовірнісна, нечітка
та лексикографічна) були описані як класи оцінної та напівкільцевої
метамоделей. описує поняття еквіваленції, удосконалення та поліно-

міального часового удосконалення у напівкільцевій CSP. Використо-
вуючи ці поняття, можна коротко підсумувати зв’язки між конкрет-
ними класами, які ширше описані в працях [66, 73].
Всі класи напівкільцевої CSP можуть бути розділені у відповід-

ності до ідемпотентності напівкільцевого оператора  : класична
ймовірнісна та нечітка CSP з одного боку та вагова, імовірнісна і лек-
сикографічна з іншого. Таке розділення означає, що існують поліно-

міальні трансформації між об’єктами різних класів для задачі знахо-
дження оптимального кортежу (або відповідної задачі доведення мо-
жливост визначення напівкільцевого значення, більшого, ніж aA ).

Існує зв'язок між ідемпотентними та неідемпотентними класами, що
виражається в лексикографічній та ймовірнісній CSP як можливе по-
ліноміальне часове удосконалення з ймовірнісної в лексикографічну

CSP.
Також можна побачити зв'язок між ймовірнісною та ваговою за-
дачами: вони зв’язані простим ізоморфізмом, де у ваговій CSP при-
ймаються дійсні числа замість натуральних.

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

ли б у відповідність дійсні.

Питання для самоконтролю
1. Що таке ступінь задоволення обмеження?

2. Що таке система обмежень?
3. Що таке ієрархія обмежень?
4. Що таке ступінь зв’язаності системи обмежень?

5. Що таке декларативність обмежень?
6. Чим відрізняється обмеження і границя?
7. Що таке формальна структура обмежень?
8. Що таке метасруктура обмежень?

9. Що таке ваговий коефіцієнт обмеження?

118