Page 130 - 4495

щим за порядком, ніж  тому, що обмеження c знаходиться на най-
i
більш важливому рівні з найбільш важливою вагою.
Отже, кожне присвоєння   є кращим за порядком. Однак, іс-
S
нують кращі за порядком присвоєння, які не можуть бути включені в
жодне ієрархічне впорядкування та його множину впорядкування
розв’язків. Наступний приклад демонструє цей факт.

Приклад 3. Нехай маємо ієрархію обмежень з одним рівнянням
C C  { , } {c c  B  10,B  8}, де w ( )c  w ( )c  . Присвоєння {B  10}
1 1 2 1 2
отримуємо з ієрархічного впорядкування c ,c , а {B  8} - із c ,c .
1 2 2 1
Обидва присвоєння кращі за порядком, але, наприклад, присвоєння

{B  9} також краща за порядком.
Алгоритм розв'язку ієрархії з компаратором типу «краще за по-
рядком» базується на твердженні 4 та алгоритмі індиго [89] для лока-

льного розповсюдження. Основною ідеєю в алгоритмі індиго є розпо-
всюдження верхніх і нижніх меж обмежень (тобто, інтервалів),і обро-
бка обмежень від найсильнішого до найслабшого, звужуючи межі

змінних, використовуючи інтервальну арифметику[90] крок за кро-
ком.
Загалом, розв’язком ІО з компаратором «краще за порядком» по-

діляється на два кроки:
1. Сортування обмежень на кожному рівні C ієрархії
i
OC ,OC , ,OC з використанням ваг, заданих функцією w та їхнім
0 1 n
впорядкуванням  для одержання вихідної послідовності обмежень
W
OC .
i
2. Застосування алгоритму індиго з впорядкованими вхідними
обмеженнями по послідовності OC ,OC , ,OC .
0 1 n
Вхідні обмеження для алгоритму індиго мають ієрархічне впоря-

дкування SC з використанням OC ,OC , ,OC . Алгоритм індиго міні-
0 1 n
мізує функцію помилки у порядку, заданому SC . Це є вимогами твер-
дження 4, отже, отримуємо матрично кращий за порядком розв’язок.
Оцінимо складність алгоритму. Нехай m  C , K  V . Сортування

всіх m обмежень займає O ( log )m m кроків. Складність останнього

кроку (алгоритму індиго). Оцінюється як (O mk [89]. Отже, маємо за-
)
гальну складність ( (O m k  log ))m .

Зв’язки з напівкільцевою CSP
Цей виклад подає більшість компараторів як класи напівкільцевої
CSP. Оскільки напівкільцевої CSP описує задачі зі скінченними до-

130