Page 128 - 4495

дно до означення 14 та нерівності j l ). Обмеження c має найбільшу
вагу в C таку, що функція помилки на  і  різні. Як наслідок,
k
)
( e d ) e (d для d  C ;
k
в) справедлива також нерівність (e c ) e (c , оскільки c є пе-
)
ршим по рівню і вазі обмеженням з чіткими значеннями функцій по-
милок у  і  , а  краще за порядком, ніж  ;

г) ( e d ) e (d справедливо для кожного d  C тому, що 
)
kl
краще за порядком, ніж  , d  C , а ( )w c  w ( )d .
k W
Ми показали, що вираз ( e d ) e (d справедливий для
)
 d C ,(i k ) ((i  k ) ( j l  ), а також, що справедливо (e c ) e (c та
)
ij
)
 d C : (e d ) e (d . Це означає, що  локально краще, ніж  у C w.
/
kl
Це доведення аналогічне до протилежного. Нехай  локально
краще, ніж  у C w. Нехай спочатку функція помилки відрізняється
/
для c C . Отже, справедлива нерівність ( e c ) e (c . Вираз
)
kl
 i k d C   : (e d ) e (d отримуємо з означення компаратора «лока-
)
i
льно краще» ( i j  таких, що
)
(i k ) ((i k  ) ( j l  )) d C  : (e d ) e (d ). Так само справедливий ви-
ij
раз (e d ) e (d для d C  таких, що ( )w c  w ( )d .
)
k W
)
Вираз (e d ) e (d справедливий для  d C : ( )w d  w ( )c тому,
k W
що d  C , а функції помилок на  та  різні в C , і  локально кра-
kl kl
ще, ніж  в C . Отже, всі необхідні умови задоволені і  краще за
kl
порядком, ніж  в C.
Твердження 3. Присвоєння  є кращим за порядком розв’язком
ієрархії C з ваговою функцією w, якщо воно є локально кращим

розв’язком удосконалення ієрархії C w.
/
Це твердження дозволяє визначити помилку ієрархії ІО ( , , )V D C

для компаратора «краще за порядком» (і степеня задоволення ієрар-
хії) як помилки ІО C w для компаратора типу «локально краще».
/

Алгоритм розв'язку ієрархії

У цьому розділі описуються методи, які дозволяють створювати
алгоритм розв'язку ієрархії обмежень з компаратором «краще за по-
рядком».

Означення 15. Порядок SC  , c  ,c є ієрархічним впорядку-
1 m
ванням ієрархії C, що містить m обмежень у тому випадку, якщо всі

C
обмеження в SC впорядковані за рівнями ієрархії (c  C , c  ,
i k j l

128