Page 112 - 4495

def ( )t  def (t  con ) def (t  con ).
1 con 2 con
1 2
З огляду на комутативність та асоціативність мультиплікативної
C
операції, можемо позначити комбінацію c  c ...  c як  n c 
1 2 n i 1 i
для C  c ,..., c .
1 n
Інакше кажучи, комбінування двох обмежень означає побудову
нового обмеження, в якому б були задіяні всі змінні з двох початко-

вих і призначених кожному кортежу значень на цих змінних певного
елемента на півкільця. Цей елемент береться шляхом множення еле-
ментів, які були призначені в початкових обмеженнях на відповідні

підкортежі.
Означення 36 (проекція). У заданому обмеженні C  (def ,con )і
підмножині I  , проекцією C на I (позначається C  ), називається
V
I
n
обмеження ( fde  ,co n ), де co  , а
I
def ( )t     def ( )t .
/ t t con t  
I con
Простіше, проекція означає виключення певних змінних. Це ро-
биться шляхом асоціювання кожному кортежу над змінними, які тре-

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

помогою мультиплікативної операції в напівкільці, а проектування –
за допомогою адитивної.
Розв’язок

Означення 37 (ступінь задоволення, розв’язок). Розв’язком на-
півкільцевої SCSP P  (C ,con ) є обмеження

Sol ( ) (P   C )  con.
Тобто, всі обмеження комбінуються і потім проектуються на
змінні множини con. Таким чином, отримуємо обмеження на множині
con, «викликане» цілою задачею напівкільцевої CSP. Також це обме-

ження виражає своєю функцією def оцінку кожного кортежу (присво-
єня), тобто воно водночас може вважатися ступенем задоволення за-

дачі.
Означення 38 (ступінь послідовності). Напівкільцеве значення
оптимальних розв’язків називається початковим рівнем послідовності
напівкільцевої SCSP і позначається:

blevel ( )P  Sol ( )P  .

Простіше, максимальне (відповідно до  ) напівкільцеве значен-
S

112