Page 151 - 4495

і в найгіршому випадку, по найменших квадратах, локально), тоді і
тільки тоді, коли  є розв’язком також і P з компаратором «краще
ІО
по сумарній вазі» або «краще в найгіршому випадку», «краще по най-

менших квадратах», «впорядковано краще» відповідно, де acv ( )c ви-
ражає вагу кожного обмеження c.

Нехай відповідність справджується для глобальних компараторів
в ІО. Будь-який розв’язок P повинен задовольняти всі обмеження з
A H
C та мінімізувати помилку E (C ) шляхом порівняння помилок
0
)
E (C з найменшого до найбільшого індексу i (див. означення 14).
i
Аналогічну мінімізацію виконує компаратор «глобально краще» з ІО,
порівнюючи по порядку значення (Cg ). Оскільки значення (E C та
)
i i
g (C задаються конкретними помилками з P та компараторами з
)
i A H
P однаковими виразами, то отримуємо однакову множину
ІО
розв’язків для обох задач - P та P .
A H ІО
Компаратор «краще за порядком» працює з почерговими рівнями
ІО P подібним чином до того, як помилки E з P порівнюються
ІО A H
від найменшого до найбільшого значення індексу кортежу. Якщо
)
значення (e c ) та (e c однакові для всіх c C , то ні помилки P , ні
i A H
компаратор «краще за порядком» не визначають, яке з присвоєнь 
чи  є кращим. Нехай на першому рівні j функція помилки є різна

для присвоєнь  і  . Тоді  краще за порядком за  якщо існує таке
c C , для якого справедлива нерівність (e c ) e (c , а якщо існує де-
)
i
яка d C , то випливає, що (e d ) e (d . Це порівняння відповідає
)
j
впорядкуванню  . Отже, вибір кращого присвоєння є однаковим для
l
АІО, заданого P та ІО P , тобто множина розв’язків у них однако-
A H ІО
ва.

Впорядкування змінних

Метою евристики впорядкування змінних в задачах CSP є вибір
найбільш «критичних» змінних, з якими потрібно працювати в першу
чергу. Ідеєю цього розділу є доведення того, що найбільш «критич-

ними» потрібно вважати змінні з найбільшими преференціями.
Шляхом першочергового опрацювання більш важливих змінних
можна добитися наданням їм більш прийнятних значень, як показано

в наступному прикладі.
Приклад 5. Нехай маємо бінарну CSP з унарними обмеженнями

151