Page 152 - 4495

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

ливим змінним задаються більш важливі значення (з більшою «ці-
ною»).
Такі преференції (анотації) змінних можуть виражати вимоги ко-

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

хування для розв’язування задачі, і раннє присвоєння їм значень мо-
же суттєво звузити простір розв'язку та допомогти уникнути помилок
як на початку, так і під час розв’язування.

Приклад 6. Нехай маємо звичайне обмеження, яке виражає, що
місце 1T повинно бути відвідане швидше, ніж 2T . Агент, що є відпо-
відальним за багато місць, повинен відвідати місця 1T , тоді як 2T по-

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

T 1@strong T 2@weak .
Анотація strong (сильний) відображає те, що змінна 1T повинна

бути задіяна першочергово. В такому випадку обмеження стає задо-
воленим,а звужене домену змінної 2T менш критичне, ніж би було
звуження домену змінної 1T .

Місце 1T може бути зайняте більш важливим клієнтом, ніж 2T .
Такий рівень важливості виражають анотації вищеописаних обме-
жень. Вони стають цікавими у поєднанні із обмеженнями з преферен-
ціями для впорядкування значень (наприклад, кожен клієнт хоче, щоб

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

шої), але суттєво підвищує складність задачі.
Розрахунок впорядкування змінних
Статичне впорядкування змінних. У системі обмежень з анотаці-

ями змінних P  ( , , ,( , ,V D C A °  ), )a , впорядкування змінних (ВЗ) роз-
A
раховується за допомогою глобальних анотацій змінних av. Це ВЗ
належить до класу статичних ВЗ. Кінцевий розрахунок ВЗ залежить

152