Page 93 - 4495

дкування  W такого, що менші вагові коефіцієнти представляють
значення менш важливих обмежень.
Проблема задоволення обмежень з ваговими коефіцієнтами P

складається з множини обмежень C з ваговими коефіцієнтами, що
обмежують можливі значення змінних з множини V , з введеним ран-
жуванням в домені D .

Вагові коефіцієнти обмежень як правило є натуральними числа-
ми. Зокрема задача MAX – CSP може бути представлена через обме-
ження потужності множини вагових коефіцієнтів W значенням оди-
ниця.

Означення 2 (ступінь задоволення (satisfaction degree)) Розгля-
немо задачу CSP з ваговими коефіцієнтами P  ( , , )V D C . Ступінь за-

доволення  присвоєння   задається як сума вагових коефіцієн-
V
тів всіх обмежень, що не задовольняються даним присвоєнням  ,

тобто,   : ( )    w ( )c .
V
  c
Означення 3 (розв’язок, ступінь зв’язності). Розв’язком CSP

задачі з ваговими коефіцієнтами проблеми P є таке присвоєння  ,

що його ступінь задоволення ( )  є мінімальною по відношенні до
 W .
Ступінь задоволення рішення дає нам ступінь зв’язності для CSP –

проблеми з ваговими коефіцієнтами.
Приклад 1. Розглянемо тривіальний приклад з тимчасового пла-
нування. Ми маємо скласти графік трьох подійу три різні періоди ча-

су. Перша з них повинна бути спланована перед другою з ваговим ко-
ефіцієнтом 10. Третя подія повинна початися зразу після першої з
меншим ваговим коефіцієнтом рівним 5. І якщо це можливо ми б хо-
тіли планувати всі наші події в наступному порядку: перша подія як

перша з них з ваговим коефіцієнтом 2, друга – як друга з них ваговим
коефіцієнтом 2 і остання подія – як остання з них з ваговим коефіціє-
нтом 2 також.

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

і його ваговий коефіцієнт не буде додано до вагового коефіцієнта
розвязку. Друге обмеження вимагає розміщення третьої події між

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

93