Page 124 - 4495

Новітні компаратори

Компаратор «лексикографічно краще»
У компаратора «краще в найгіршому випадку» є недолік т. зв.
«ефект утоплення»: якщо обмеження c з вагою w (c) повинно бути

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

Приклад 2. Нехай потрібно організувати дві зустрічі протягом

будніх днів в одному тижні (змінні A, B, долями mon..fri ). Кожна
зустріч повинна бути організована в окремий день (якщо A є пер-
шою, то справедлива нерівність A  ). Деякі строгі вимоги задані ор-
B
ганізаторами та гостями зустрічей. Організатори хочуть, щоб між зу-

стрічами було хоча б вільних днів (B-A 3@strong,w  20). Двоє з за-
прошених гостей хотіли б, щоб зустріч відбулась у середу

(A,B wed@strong,w 10  , де вираз А, B wed означає
(A  wed) (B wed)  ). Інший гість хоче, щоб зустріч відбулась в поне-

ділок (A,B mon@strong,w 5  ). І ще один гість віддає перевагу четвер-

гу (A,B thu@strong,w 5  ). Вимоги інших учасників не такі важливі,
але вони можуть бути взяті до уваги як другорядні обмеження і деякі
люди хотіли б, щоб зустріч була у вівторок (A,B tue@weak,w 10  ), а

дехто інший – понеділок та четвер (A,B mon@weak,w  5 та

A,B mon@weak,w  5).
Ієрархія обмежень для даної задачі має вигляд:
required: c0: A B

strong: c1: B  A  3 w  20
c2: A,B wed w 10
c3: A,B mon w 5

c4: A,B thu w 5
weak: c5: A,B tue w 10
c6: A,B mon w 5

c7: A,B thu w 5
Компаратор «найкраще в найгіршому випадку предикатно» ви-
бирає розв’язок присвоєння   (tue,fri), яке задовольняє тільки обме-

ження c0,c1 та c5, де E (C, ) [10,5]  . Це означає, що вимоги всіх за-
прошених гостей упущені, незважаючи на те, що існують присвоєння,

які частково їх задовольняють. Така небажана поведінка цього ком-
паратора пояснюється високою вагою обмеження c2, яким потрібно

124