Page 105 - 4495

P ( , PS , ),M ( , N , ) S складається з початкової задачі P , простору задачі
PS , що включає в себе також саму задачу P , метрики M на цьому
просторі, а також відстаней розв’язку необхідної N за достатньої S

(справедлива нерівність S  ). За допомогою розв’язків функції від-
N
стані можна визначити, скільки розв’язків було додано після послаб-
лення P. Також можна визначити кількість аргументацій у P, необ-

хідних для переходу від Р до P , та максимально можливу кількість
дозволених обмежень.
Означення 23 (розв’язок). Розв’язком задачі часткового задово-

лення обмежень P ( , PS , ),M ( , N , ) S є задача P із простору задач PS , ра-
зом зі своїми розв’язками, де метрика від P до Р менша за N , тобто


M ( P, P ) N . Розв’язок є достатнім (прийнятним) якщо метрика менша
або рівна S . Оптимальний розв’язок – це такий, де метрика від P до
Р мінімальна на просторі задач.

Ступенем задоволення часткової CSP може вважатися значення

метрики M (P ,P ). Значенню ступеня повноти відповідає значення сту-
)
пеня задоволення оптимального розв’язку: min M ( ,P P .
M
Всі підходи, описані вище в цьому розділі, метою якого є
розв’язок задачі задоволення обмежень з преференціями, можуть бу-

ти представленими як частка CSP.
Оцінне задоволення обмежень
В оціночному задоволенні обмежень [65, 66, 67] вводять оцінки

над обмеженнями, що є основними преференціями цієї мета-моделі.
Пропонується загальна структура, базована на впорядкованому моно-
їді оцінок. Моделі, описані вище у цьому розділі, можуть бути пред-

ставлені як класи оцінюючої CSP.
Структура оцінювання
Для опису того, що обмеженням можна знехтувати (тобто, що

обмеження може бути не задоволеним), кожному обмеженню нада-
ється так звана оцінка, що виражає преференцію обмеження. Оцінки
надаються за наступною структурою.
Означення 24 (структура). Структура оцінювання обмежень ви-

значається кортежем ( , , ,E #  T, )  , де
а) E - множина, елементи якої називається оцінками;

б)  - загальний порядок в E ;
в) T та  - максимальний та мінімальний елемент з E відповідно
до ;
г) # - комутативна, асоціативна бінарна операція, яка задоволь-

105