Page 108 - 4495

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

ших послідовностях.
Вивід 1. Нехай задано оціночну CSP P  (V , D ,C ,S , )та два її по-
E
 

слаблення P  (V ,D ,C ) та P  (V , D ,C )   . Тоді справедливе твердження:
   
)
C Ц C   ( , ,V D C ) ± ( , ,V D C .
P
E P E
У випадку строгої монотонності операції # нерівність набуває
строгого характеру, якщо оцінка P  T .
E
Позначимо a  #  ( )c . Із монотонності робимо висновок, що
c (C C  ) 
))
(± ) a  (( #  (P ± (a # (P )). Із цього означення 30 випливає, що
P P
E E
 (P ) ± ( )P .
P P
E E
Цей вивід показує, що строга монотонність є дійсно вельми ба-
жаною властивістю. Її наявність гарантує, що при видаленні знехту-
ваного обмеження із множини C оцінка одержаного послаблення бу-

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

Твердження 5. Присвоєння   є розв’язком оцінної задачі CSP
V
P , якщо воно є розв’язком послідовного послаблення Pз мінімаль-
E
ною оцінкою. Рівність  ( )  (P ) зберігається.
E P E P
Розв’язком P є присвоєння з мінімальною комбінацією оцінок
E
обмежень, які мають бути видалені з множини обмежень для досяг-
нення послідовного розв'язку. Послаблення з найменшою оцінкою
має поєднати оцінки «тих самих» обмежень. Символ лапок в даному

випадку застосований для відображення обмежень з однаковими оці-
нками у випадку ідемпотентності операції # . Тоді оцінки цих обме-

жень не впливають ні на  ( ), ні на  (P ).
P E P
E
Класи оцінної CSP
Визначивши структуру оцінки обмежень, отримуємо специфічні

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

оцінюючою за допомогою їх прямих зв’язків з напівкільцевою CSP.

108