Page 132 - 4495

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

графічно краще».
Компаратор «краще за сумарною вагою». Нехай маємо обме-

ження @c l з ІО C, з вагою ( )w c , і визначена на змінних ( ,v  , )v . Тоді
1 k
воно відповідає напівкільцевому обмеженню (def ,con ), такому, в яко-

му con  ( ,v  , )v , і:
1 k
   [v  d , ,v  d ]:def ( ,d  d ) (0,  , 0, ( )w c  ( e c ), 0, ,0) .
1 1 k k 1 k

1 l 1  l l 1 h
Операція  еквівалентна векторній сумі, що позначається , тоб-
то
   
a b  ( , , ) ( , , ) (a  a  b  b  a  b , ,a  b ).
1 h 1 h 1 1 h h
Напівкільцева множина відповідає множині h - кортежів, розши-
рених елементом . Адитивна операція задається лексикографічним
мінімумом над h-кортежем, тобто:
   
[min( , )a b  a ] [ (i a   b ) ( j i a   :  b )].
i i i i 
Мінімальний елемент 1 відповідає h - кортежу нулів 0, що являє
собою повне задоволення.
c- напівкільце для компаратора «краще по сумарній вазі» відпо-
   
відає структурі S  ( h   ,min, , ,0)   .

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

льцевої CSP, що створюється даним компаратором, спрощується ви-
значення напівкільцевого обмеження до
def ( ,d  d ) (0,  ,0, (e c ),0, ,0), де (e c ) {0,1} на l -тій позиції для
1 k
c @l .
Компаратор «краще за найменшими квадратами». Різниця

між цим компаратором і компаратором «краще за сумарною вагою»
полягає у зміні напівкільцевого обмеження шляхом заміни функції
2
помилки її квадратом def ( ,d  d ) (0,  ,0, ( )w c  ( e c ) ,0, ,0) з ненульо-
1 k
вим значенням на l - тій для обмеження @c l .
Компаратор «краще в найгіршому випадку». Початкова ідея

визначення класу напівкільцевої CSP, яку задає цей компаратор поля-
гає у заміні мультиплікативної операції для кожного рівня ІО прово-

диться пошук найменш задоволеного обмеження:

132