Page 154 - 4495

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

Нагадаємо чим відрізняються множини C , V від C, V для де-
якого часткового присвоєння   , W  . Множина V є підмно-
V
V
жиною V і містить тільки ті змінні, яким не було присвоєно значення
присвоєнням  . Для множини C справедливий вираз C  {c c C  }.

Деякі обмеження c стають порожніми відношеннями як тільки їх
множина V стає порожньою. Для інших обмежень c множина
c
змінних звужується на ті змінні, яким вже присвоєні значення:
V  V  (W  V ) . Відповідно до пропагації обмежень, певні відно-
c c c
шення для обмежень c містять ймовірно меншу кількість елементів,

аніж відповідні обмеження c після застосування проекції кортежу на
змінні, що залишились у c , тобто маємо c   V c .
c
V c
Означення 15 Нехай маємо систему P  ( , , ,( , ,V D C A °  ), )a та де-
A
яке часткове присвоєння   , W  . Динамічна глобальна анотація
V
W
змінної dav об’єднує анотації у всіх обмеженнях C , де зустрічаєть-
W
ся змінна із множини V  V W :

dav :[V W ]   A , dav ( , )v    a ( , )c v .
W W
(c C ) (v V  )
c
Така динамічна глобальна анотація змінної дозволяє впорядкува-
ти змінні, яким ще не були присвоєні значення. Наступна змінна, якій

повинно бути присвоєне значення – це така, глобальна динамічна
анотація якої найбільш важлива (точніше, така, що не існує змінної з
( , )v  .

більш важливою dav): v V : dav ( , )v  ° dav 

Питання для самоконтролю.
1. Для чого виконується нотування змінних?

2. Що таке переобмежена задача?
3. Що таке преференція обмеження?
4. Що таке середовище розв’язку задач на основі обмежень?

5. Що таке простір рішень?
6. Що таке перестановка змінних у кортежі?
7. Що таке преференційована анотація?

8. Як розраховують характеристики системи обмежень?
9. Що таке анотаційний триплет?

154