Page 121 - 4495

Позначимо (e c ) як помилку обмеження c в присвоєнні  . Триві-
альна (предикатна) функція помилки може бути застосована до всіх
)
доменів D . Така функція присвоює (e c значення "1" для значень
функції, які ще не були визначені, тобто (e c ) 1 . Для знехтуваного

обмеження c в присвоєнні  . У тому випадку, якщо домен D є мат-
ричним простором з метрикою dist , можна задати матричну функцію
помилки таким чином:

 d ,d  D : (e d  d ) dist ( ,d d .
)
1 2 1 2 1 2
Наступне визначення дозволяє описати ступінь задоволення кож-
ного присвоєння з ІО.
Означення 5. Нехай маємо множину обмежень C, де обмеження
розташовані за певним встановленим порядком ( ,c  , )c .
1 k
Помилкою множини обмежень C  ( ,c  , )c в присвоєнні  
1 k V
буде кортеж (E C ) [ (e c ), , (e c  .
)]
1 k
Класичні компаратори
Було запропоновано велику кількість компараторів, кожен з яких

по-різному задає множину розв’язків в ІО. Всі типи компараторів
можна класифікувати на локальні, глобальні та регіональні. В лока-
льних компараторах береться до уваги кожне обмеження окремо.

Глобальні компаратори сумують помилки всіх обмежень певного рів-
ня. У регіональних компараторах, як і в локальних, обмеження бе-
реться до уваги окремо, але на відміну від локальних, два розв’язки,

не порівнювані на інших рівнях, можуть бути на нижчих.
Локальні компаратори
Означення 6. Нехай маємо два присвоєння  та  . Для того, щоб

бути локально кращим за присвоєння  , присвоєння  повинно бути
таким самим, як і  для всіх обмежень на рівнях 1 k  1, а на рівні k -
хоча б таким самим, як  , але строго кращим хоча б для одного: ло-

кально краще ( , , )C   k   1 n таких, що
i   1 k  1 c C  : (e c ) e (c ;
)
i
)
 c C : (e c ) e (c ;
k
)
 d  C : (e d ) e (d .
k
«Локально предикатно краще» - це компаратор типу «локально
краще», що використовує тривіальну функцію помилки. «Локально
метрично краще» - компаратор типу «локально краще», що викорис-

товує метрики в доменах для розрахунку помилок обмежень.
Для досягнення порівняння з рівнем задоволення інших підходів

121