Page 134 - 4495

мо протилежне впорядкування (c разом із c більш важливі, ніж саме
3 2
c ). Це суперечить монотонності мультиплікативної операції.
2
Компаратор «лексикографічно краще». Метою цього компара-
тора є уникнення «ефекту утоплення» компаратора «краще в найгір-
шому випадку» та його не інтуїтивної поведінки (див. приклад 2). Та-

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

вище тим, що в ньому елементами A h-арного кортежу ( ,A  , A є
)
i 1 h
мультимножина. Найкраще напівкільцеве значення відповідає поро-

жній множині  (кортежу порожніх множин ), а найгіршим є еле-
мент. Напівкільцеве обмеження в даному компараторі відрізняється
від такого ж в компараторі «краще в сумарній вазі» функцією def , яка

для компаратора «лексикографічно краще» має вигляд:

   [v  d , ,v  d ]:def ( ,d  d ) ( ,   , ,{ ( )w c  ( e c )}, ,  , ) ,
1 1 k k 1 k
1 l 1  l l 1 h
де { ( )w c  ( e c )} - мультимножина. Напівкільцева множина задається

l
h- арним кортежем мультимножин. Адитивна операція т задається
об’єднанням множин т застосованим до кожного елемента h - арного

кортежу:
   
Aт B  ( ,A  , A ) ( ,B т ,B ) (A т B , , A т B ).
1 h 1  1 1 h h
h
Мультиплікативна операція minlex є лексикографічним розши-
ренням операції мінімуму min
     lex
A  min ( , ) min (( ,A B  lex A  , A h ),( , ,B  B h )) 
lex
1
1
[(A  B ) (A  min ( , ))]A B 
1 1 1 lex 1 1

[(A  B ) ((A , , A ) min ((A , , A ),((B , ,B )))]
1 1 2 h lex 2 h 2 h
Локальні компаратори
Компаратори цього типу дещо складніші, ніж глобальні, оскільки
вони порівнюють помилки кожного обмеження окремо, а не сортують
їх за рівнями. Це відображається мультимножинами, заданими над
непорівнюваними елементами, кожна з яких відповідає одному об-

меженню. Для ІО, що містить m обмежень, множина попарно непорі-
внюваних елементів позначається як U  { ,u  ,u }. Причина застосу-
1 m
вання мультимножин замість звичайних множин у цьому випадку по-
лягає в необхідності мультиплікативної операції. При включенні му-
льтимножин потрібно зробити деякі зміни в параметрах: максималь-

134