Page 107 - 4495

Означення 27 (ступінь задоволення). Задача оцінна CSP та при-
V
своєння   , де X  . Оцінка присвоєння  визначається як:
X
 ( )  #  ( )c .
P
E
(c C ) ( c V  X ) ( |  ) c
Зазначимо, що таке визначення структури оцінювання веде до
ідемпотентності операції # . Як тільки у присвоєнні нехтують обме-
женням з оцінкою w, не має значення скільки обмежень з оцінкоюw

знехтувано – оцінка присвоєння залишається незмінною.
 використовується для надання оцінок присвоєнням, що є зру-
P
E
чним у виборі потенційного розв’язку, тобто воно надає ступінь задо-
волення кожному присвоєнню. Використання цього робить можли-
вим визначення розв’язку оцінюючої CSP.

Означення 28 (розв’язок, ступінь задоволення). Розв’язок оці-
*
нної CSP P  (V , D ,C ,S , )- це присвоєння  з мінімальною оцінкою
E
відповідно до порядку . Таку мінімальну оцінку будемо називати
оцінкою задачі P .
E
Оцінка задачі P відповідає її ступеню задоволення.
E
Оскільки потрібно шукати присвоєння з нейтральною оцінкою
шляхом комбінування знехтуваних обмежень за допомогою операції

# , можна зазначити, що елемент T відповідає неприпустимому зне-
хтуванню і використовується для опису жорстких обмежень, а еле-
мент  відповідає повному задоволенню.

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

Означення 29. Нехай P  (V , D ,C ,S , )- оцінна CSP. Послаблення
E

оціночної CSP називається класичним CSP (V ,D ,C ), де (C  C ).
Послаблення впорядковані включенням множин обмежень. Бу-

демо вважати послідовним те послаблення, в якому множина C най-
більша. Таке послаблення – задача, що має розв’язок, воно найменш
віддалене від початкової задачі P . Також можна впорядкувати посла-
E
блене задоволення оцінок певних послаблень.

Означення 30. У заданій оцінній CSP P  (V , D ,C ,S , ) та її послаб-
E
ленні (V ,D ,C ) є:
)
 ( , ,V D C  #  ( )c .
P E
c (C C  )
Очевидно, вершиною сітки послаблень самої задачі CSP, буде

елемент (V ,D ,C ), буде елемент . Оцінки інших послаблень можна

107