Page 127 - 4495

ність w ( )d  w ( )c . Нехай також існують розв’язки  і  такі, що
W
)
( e c ) e (c , (e dw ) e (c . Обидва можуть бути локально кращими, але
)
тільки  може бути кращим за порядком.
Наведемо власне опис взаємозв’язків між компараторами «лока-
льно краще» та «краще за порядком».

n
Означення 14. Нехай маємо ієрархію C   C та функцію ваги
i
i 0
w :C  W . Удосконаленням ієрархії називається ієрархія
n i n
 C i / w   C , така, що справедлива рівність C 0 / w C 0 , а значення C
ij
ij
i 0 j 1
задається i  1 n , j  1 n формулою:
i i
( c C d C    :(c C d C ,  ,l 1 n j l , )  ( ( )w d  w ( )))c .
i i ij il i W
Оскільки ваги не мають жодного значення на обов’язковому рівні
C , то можемо вважати, що ваги однакові для кожного c C . Відпові-
0 0
дно, C / w C  C . Рівень C є обов’язковим, і всі обмеження, які є в
0 0 01 0
ньому, повинні бути задоволені в кожному розв'язку. Отже, при порі-
внянні потенційних оцінок розв'язків, можемо обмежитись рівнями

1 n .
Удосконалення ієрархії можна вважати як ієрархію, де рівень C
ij
більш важливий, ніж C (i k ) ((i  k ) (i l  ).Зазначимо також, що об-
kl
меження ,c d C мають однакову вагу, відповідно до загально впоря-
ij
дкованої множини ваг W .

Допоміжне твердження 2. Для даної ієрархії C, вагової функції
w та присвоєння  і  справедливий вираз: «краще за порядком»

( , , )C   «локально краще» ( , ,C  / )w .
Нехай  і  - присвоєння з ієрархії Cі  краще за порядком. Не-
хай k перший рівень, на якому різняться функції помилок у  та  , а

)
c C - обмеження з найбільшою вагою ( )w c такою, що (e c ) e (c .
k
Також нехай c C є справедливим для певного l  1 n з ієрархії
kl k
/
C / w. Покажемо, що  локально краще, ніж  в ієрархії C w.
а) ( e d ) e (d є справедливим для кожного d C ij ,
)
i 1 (k  1), j  1 n , тому що те саме є справедливим і для кожного
i
C
d  , i 1 (k  1) (функції помилки в  та  вперше різняться на рів-
i
ні k );
б) ( e d ) e (d є справедливим для кожного d C ,
)
kj
j  1 (l  1). Спочатку зазначимо, що d  C і що ( )w c  w ( )d (відпові-
k W

127