Page 141 - 4495

L @strong  1#  P @medium % 1c .

Нехай також є два слабкі обмеження: лекція має відбутися в чет-
вер або п’ятницю, а практика – в будь-який день між понеділком і че-

твергом:

L @weak в 4..5 % 2c ,

P @weak в 1..4 % 3c .

Ці обмеження формують структуру, подібну до ієрархії:

обов’язково повинне бути задоволення обмежень 1c , що має найбі-
льші преференції, після чого можна спробувати задовольнити 2c та
3 c . Можливо задовольнити 1c , але не 2c і 3c одночасно. Обмеження
2 c впливає на змінну з вищими анотаціями (див. 1c ), отже, його та-

кож потрібно задовольнити.
Прагнучи мінімізувати загальне знехтування обмежень, знаходи-

4
мо оптимальний розвязок: L  , P  5. При використанні класичної
ієрархії, де обмеженню 1c надались би преференції strong або medium,
можливо є також і розвязок L  3, P  . Але цей розвязок не є опти-
4
мальним.
Різні вимоги щодо лекцій та практики повинні бути описані на-
данням різних преференцій обмеженням 2c та 3c , і таким чином ці

обмеження повинні бути впорядковані. Але якщо б задача була більш
складна (а в більшості задач кількість обмежень значно перевищує
кількість змінних), то навряд чи легко було б виділити два такі відпо-
відні обмеження. Отже, такі міркування є не завжди правильними.

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

змінних, ніж шукати обмеження, зміна преференцій в яких вела б до
покращення розв'язку.

Анотаційний триплет

Означення 1. Об’єднувальною функцією на множині  назива-
ється функція, задана на кожному скінченному кортежі значень із A,

така, що її значення для кортежу ( ,a  , )a не залежить від перестано-
1 n
вки змінних в цьому кортежі:

, i   ,i  {1, , }n таких, що
1 n
 , k l  {1, , }:n i  для
i
k l

141