Page 120 - 4495

підвищення ефективності ієрархій.

Опис задачі

Означення 1 (обмеження). Позначене обмеження - це пара @c l ,
де c - класичне обмеження, яке позначене міткою l , що визначає рі-
вень обмеження в ієрархії. Рівні є загально впорядкованими і окре-

мим рівням можуть бути присвоєні імена. Імена позначаються цілими
числами 0 . Рівень 0 з символьним іменем required (обовязковий)
n
завжди резервується для обмежень, які повинні бути задоволені.

Означення 2 (задача). Ієрархією обмежень є скінченна множина
C позначених обмежень над змінними з множини V , домени яких

знаходяться в множині D . Підмножина C містить обов’язкові обме-
0
ження з множини C рівні яких опускаються. Підмножина C містить
1
обмеження з найвищими необов’язковими рівнями, і так далі, аж до
підмножини C , де n - число необов’язкових рівнів ієрархії обмежень
n
(надалі ІО). Всі множини C , де k  - порожні.
n
k
Таку ІО будемо позначати як P  ( , ,V D  n C ). Часто буде гово-
ІО i 0 i
ритися про ІО тільки як про множину обмежень C.
Означення 3 (розв’язок) Розв’язком ІО є таке присвоєння 
змінних із множини V , яке задовольняє хоча б обов’язкові обмеження

хоча б так, як і інше присвоєння, що задовольняє обов’язкові, тобто
множина розв’язків C відповідає:
S    c C c holds 
0 0
S      S     better  , ,C   ,
S

0 0 0
де оператор «краще» є т. зв. компаратором, що є нерефлексивним та
транзитивним двох присвоєнь ієрархії.
Також зазначимо, що розв’язок  є кращим для ІО, якщо не існує
кращого присвоєння, ніж воно.

Однак, оператор «краще» не задає загальний порядок над присво-
єнням і може існувати два присвоєння  та  , що  не краще за  , а
 не краще за  .
Для порівняння присвоєнь потрібна пара, настільки конкретне

присвоєння задовольняє задане обмеження. Означимо т. зв. функцію
помилки, що характеризує задоволення обмежень присвоєння   .
V
Означення 4. Функцією помилок є функція е:C× з властивіс-
v
тю:
    c C : (e c ) 0   | c .
V

120