Page 113 - 4495

ня кортежів у розв'язку Sol (P ) відповідає найкращому рівневі послідо-
вності. Множину цих кортежів називають множиною оптимальних
кортежів. Незважаючи на означення 37 (розв’язку), тільки оптимальні

кортежі підходять під класичне означення розв'язку, описане на поча-
тку ціього розділу.
Еквіваленція та удосконалення

Для початку наведемо означення еквівалентності для напівкіль-
цевого задоволення обмежень.
Означення 39 (впорядкування обмежень). Нехай задано два

)
,
)
обмеження c  (def con та c  (def con на кортежі (S ,D ,V ). Позначимо
,
1 1 2 2
впорядкування обмежень ф як наступне часткове впорядкування:
S
1 c ф S 2 c якщо def 1(t  S def 2( ))t дійсна для всіх кортежів значення із D. За-
c
значимо, що якщо 1 c ф S 2 c та 1 c х S 2 c , то c  .
2
1
Означення 40 (еквівалентність I). Нехай задано напівкільцеву
CSPs P  (C ,con )та P  (C ,con ). Позначимо попередній кортеж ф таким
1 1 2 2 P
чином: P ф P P якщо Sol ( )P ф S Sol ( )P .
1
2
2
1
Якщо P ф P P та P ф P P , то вони мають однакові розв’язки. Тоді
1
1
2
2
кажуть, що P та P - еквівалентні задачі та розписують: P  . Таке
P
1 2 1 2
визначення еквіваленції корисне для того, щоб показати тотожність
)
)
моделі напівкільцевої CSP (C  C ,con ф P (C  C ,con .
Інше визначення еквіваленції та удосконалення може бути задане
для порівняння задач з різними напівкільцевими структурами. Запро-
поноване нижче визначення базується на еквіваленції, визначеній у
моделі оцінюючого задоволення обмежень [66, 73]. Воно використо-
вується для порівняння задач із загальною впорядкованістю оцінок.
Воно також придатне для порівняння (зіставлення) всіх класів напів-
кільцевої CSP, включно з такими, які мають тільки часткове впоряд-

кування.
Нижче будемо використовувати дві системи обмежень CS  (S , D ,V )


та SC   (S , D ,V ), а також напівкільцеві CSP P  (C ,con ) та P  (C ,con ) відпо-
)
відні їм, що мають розвязки Sol (P )  (def ,con ) таSol ( ) (P  def  ,con .
Означення 41 (удосконалення). Напівкільцева CSP називається

удосконаленням задачі P якщо для кожної пари кортежів
D
t  (t ,...,t ), r  (r ,...,r ), t , r  , таких, що зберігається нерівність
1 con 1 con i i
def ( )t   ' def  , справедливе загальне впорядкування def ( )t  def ( )r .
( )r
S S
Напівкільцева CSP P є сильним удосконаленням P, якщо ця вла-
стивість справедлива для всіх def та def , визначених обмеженням
1 2

113