Page 126 - 4495

меження c0 та сильного c1 з більшою вагою). Кожне присвоєння, що
задовольняє сильні обмеження c1, c3, c4повинне нехтувати обмежен-
ням c5([c1 c3]   c5) та задовольняти c6(c3 c6) і c7(c4  c7).

Компаратор «краще за порядком»
Ще один підхід, в якому беруться до уваги помилки обмежень,
представлений компаратор, що використовує впорядкування (ваги)

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

порівнюються за допомогою ваг обмежень (означення 11): «краще за
порядком» ( , , )C   k   1 n таких, що

)
l   1 k  1 c C  : (e c ) e (c
i
)
 c C : (e c ) e (c
k
 d  C таких, що ( )w c  w ( ): (d e d ) e (d
)
k W
У цьому розділі роз’ясняються зв’язки між компараторами типу
«локально краще» та «краще за порядком».
Будемо позначати ІО як множину C { ,c  , }c з рівнями  n C та
1 m i 0 i
вагами W , і w .
W
Допоміжне твердження 1. Будь – який розв’язок  ієрархії C,
кращий за порядком, є локально кращим.

Припустимо, що краще за порядком присвоєння  є локально
кращим. Тоді, відповідно, існує присвоєння , локально краще, ніж
 . Нехай C - перший рівень, на якому присвоєння  та  мають різ-
k
ні значення функцій помилок деяких обмежень. Враховуючи те, що
присвоєння  локально краще, ніж  , запишемо

)
 d C : (e d ) e (d .
k
Рівень C - перший, де різняться функції помилок, тому наступ-
k
ний запис випливає з визначення (13) компаратора «краще на поряд-
ком» ( , , )C  :

)
 d  C : (e d ) e (d ,
k
що суперечить попередньому виразу. Отже, ми прийшли до супереч-
ності і можемо стверджувати, що не існує локального кращого при-

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

Існують локально кращі розв’язки, які не є кращими за порядком.
Наприклад, нехай маємо ієрархію C C  { , }c d , де справедлива нерів-
1

126