Page 106 - 4495

няє таким вимогам:
- точність:   E : a#  a ;
a
- монотонність a  :(a ± a )  ((a # ) b ± (a# b )).

, ,a b E
З цих аксіом також можна зробити висновок, що елемент T є аб-
сорбуючим, тобто a  E :(a # T )  T .
Впорядкована множина E дозволяє описати різні рівні знехту-

вань обмежень. Комутативністю та асоціативністю гарантується те,
що оцінка присвоєння залежить тільки від множини оцінок обмежень,
якими знехтували, а не від їх сукупності. Монотонність гарантує те,

що оцінка присвоєння, яке задовольняє множину обмежень C, буде
такою ж, як і оцінка присвоєння, що задовольняє підмножину C.
Слід також додати дві додаткові властивості структури оціню-

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

вість, є строго монотонною.
Строга монотонність:

 a , ,b c E :((a  c ) ((b  T ))  ((a # ) b  (c# b )).

Друга властивість – це ідемпотентність операції # :

 a E : a# a  .
a
Така властивість гарантує, що обмеження, яке задовольняється

всіма розв’язками задачі CSP, може бути додане до цієї задачі без
змін.
Допоміжне твердження 4. Ідемпотентність та строга монотон-

ність несумісні, якщо множина E має більше, ніж два елементи.
ідентичкість строга_монотонність
 a E :  T  ( # ) a  (a # ) a  a  (a # ) a , що є несуміс-
a
ним із ідемпотентністю.
Опис задачі

Означення 25 (обмеження). Оцінене обмеження – це кортеж
, c  (c )), де c- класичне обмеження, а  - функція із множини обмежень
c на множину оцінок E , яку називають оцінкою обмеження.

Означення 26 (задача). Оцінна CSP P визначається класичною
E
задачею (V ,D ,C ) і структурою оцінювання S  ( , , , , )E #  T  , а також фун-
кцією оцінки такого обмеження  , тобто: P  (V , D ,C ,S , ).
E
Кожне присвоєння буде оціненим шляхом комбінування оцінок

всіх знехтуваних обмежень за допомогою операції # .

106