Page 140 - 4495

ЛЕКЦІЯ 19-20

МЕТОДИ АНОТУВАННЯ ЗМІННИХ У CSP

Перебмежені задачі зазвичай розв’язують заданням певного рівня

преференцій кожному обмеженню окремо [56, 75, 73] або кожній
комбінації значень для кожного обмеження [61, 70] з подальшим
розв’язуванням з використанням цих преференцій. Існує також і ін-
ший підхід, слабо досліджений на даний момент – надання преферен-

цій власне змінним, що повинно бути цікаво для необмежених задач
або задач оптимізації із частковим чи повним впорядкуванням змін-
них. Обмеження з анотаціями змінних – це середовище розв'язку за-

дач задоволеня обмежень, де преференції задаються окремо змінним
замість того, щоб задаватись обмеженням. [88, 91, 92, 93]. Більше то-
го, кожна змінна може мати різні анотації в різних обмеженнях (в де-

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

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

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

ту літака в різні часові проміжки. У випадку, якщо задача пере обме-
жена, єдина можлива дія – це видалення певного літака із черги на
виліт з певних міркувань. Можна надати преференції індивідуальним
змінним (літакам) і задати такий компаратор, який переносить від-

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

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

обмеженням покажемо, що час лекції (яку веде професор) більш важ-
ливий, ніж час практики (веде асистент):

140