Page 129 - 4495

i
j
k    ) та по ваговому впорядкуванню  (для ,c c  C таких, що
l
W i j k
w ( )c  w ( )c   ). Порядок c ,c  ,c позначається як SC для
j
i
j W i 1 2 i i
i m .
Означення 16. Нехай SC - ієрархічне впорядкування ієрархії
C : SC  , c c  ,c . Рекурсивно визначена множина S  S називається
1 2 m m
множиною впорядкування розв’язків ієрархічного впорядкування SC
для S  {  є присвоєння SC }, S  {   S  ( e c ) min e  (c ) } для
0 i i 1 i i
 S i 1
i 1 m .
Твердження 4. Нехай SC - ієрархічне впорядкування в C, а мно-
жина S - множина впорядкування розв’язків SC . Тоді S є множиною
кращих за порядком розв’язків.

Доведемо індукцією по числу обмежень m. Для m  1: нехай існує
ієрархія C  { }c , тоді існує тільки одна SC  c . Отримуємо
1 1
S
S  S  {   : (e c ) e  (c 1 )} і, відповідно, кожне присвоєння   є
1
1
розв’язком, кращим за порядком.
Припустимо, що твердження справедливе для ієрархії з m обме-
жень і дослідимо його для ієрархії з кількістю обмежень m  1. Нехай

  S . Покажемо, що для будь-якого присвоєння  або  є кращим
m 1
за порядком, ніж  для SC , або  не краще за порядком для SC
m 1 m 1
( і  не порівнювані для SC ).
m 1
а)   S    S : Функція помилки для кожного (c i 1 m ) різ-
m 1 m i
на, що випливає із припущення   S та означення множини впоряд-
m
кування розв’язків. Із припущення   S та мінімального значення
m 1
для функції помилки обмеження c випливає нерівність
m 1
)
( e c  ) e (c  . Разом ці дві властивості вказують на те, що  краще
m 1 m 1
за порядком, ніж  .
б)   S : Функція помилки для кожного обмеження однакова,
m 1
отже не існує такого обмеження (c i 1 m  1) такого, що (e c ) e (c
)
i
(або <) і ні  , ні  не є кращими за порядком, ніж інші присвоєння в
SC .
m 1
в)   S :  S , отже  не може бути кращим за порядком, ніж 
m m
у SC відповідно до припущень індукції. Покажемо, що додавання
m
обмежень c не змінює нічого для SC . Значення функції помилки
m 1 m 1
для деяких i 1 m різне для  і  (  S . Нехай i - перше таке число.
m
Тоді справедливо, що (e c ) e  (c ). Присвоєння  не може бути кра-
i i

129