Page 150 - 4495

ac ( )c  a ( , ) 0.3c L  , ac ( )c  a ( , ) 0.3c P  .
2 2 3 3
В результаті отримуємо АІО C C  C  { } { , }c  c c . Глобальні
1 2 1 2 3
анотації змінних та обмежень мають ті ж значення, що і у прикладі 3.
Обмеження 1c може бути задоволеним, однак 2c та 3c разом – ні.
Зважаючи на меншу вагу 3c , отримуємо розв’язок   {[ ,4],[ ,5]}L P з

помилкою:
E (C ) [0,(acv ( )c  ( e c  ) acv ( )c  ( e c  ))] [0,(0.6 0 0.45 1)] [0,0.45]     .
0 2 2 3 3
Нехай було зроблено змінну в анотації змінної P в обмеженні 3c
до 0.6. Отримуємо три рівні ієрархії: C  [{ },{ },{ }]c c c . Також підви-
1 2 3
щуються значення av ( ) 0.6P  та acv ( ) 0.6c  .Кінцевий розв’язок
3
  {[ ,3],[ ,4]}L P має помилку (E C ) [0,0,0.6] . Це значення помилки ві-

дображає те, що ми нехтуємо більш важливим, ніж у попередньому
прикладі.
Можна також порівнювати індивідуальні помилки окремих об-

межень за допомогою глобальних анотацій обмежень acv. Так звана
локальна помилка задається кортежем пар (acv ( ), (c e c )):

E (C   ) [(acv ( ) (c e c )), ,(acv ( ), (c e c  ))] для C  { ,c  , }c  ,
C
1 1 k k 1 k
де обмеження в C впорядковані певним чином. Задамо порядок 
l
над локальними помилками множин обмежень, за допомогою якого
визначимо розв’язок P через локальні помилки (див. означення 14):
A H
[( , ), ,( , )]a e  a e k  l [(( , ), ,( , )] ( :a e  a e   i e  e i ) ( j a  : j  a  e  e j )


1
j
k
j
k
k
i
1
1
1
У множині обмежень C  { ,c  , }c з глобальними анотаціями об-
1 k
межень acv ( ),c  ,acv ( )c , мінімальний елемент впорядкування  від-
1 k l
повідає кортежу, в якому другий елемент кожної пари (acv ( ), (c e c є
))
i i
рівним 0, тобто всі обмеження з C задоволені присвоєнням  . Оскі-
льки значення глобальних анотацій обмежень не повторюються в
P , то існує один і тільки один найменший елемент для кожної мно-
A H
жини обмежень C.
Зв’язки з класичною ІО
Зв'язок ієрархічних анотацій та класичних ієрархій обмежень
аналогічний також для нечітких анотацій та нечіткої CSP.
Твердження 3 (ієрархії обмежень). Нехай P  ( , , ,V D C A , )a -
A 
система обмежень з ієрархічними анотаціями, а  n i 1 C - її АІО. Задамо

ієрархію обмежень P кортежем ( , ,V D  n , )C . Тоді   є розв’язком
ІО i 1 V
P з помилкою за сумарною вагою (або однією з наступних помилок
H
A

150