Page 119 - 4495

10. Як впливає ступінь зв’язаності на процедуру пошуку рішен-
ня?
11. У чому сутність імовірнісної теорії обмежень?
12. Як вводиться імовірнісний розподіл для системи обмежень?

ЛЕКЦІЯ 17-18

ТЕХНОЛОГІЯ ПОБУДОВИ ІЄРАРХІЙ ОБМЕЖЕНЬ

Ієрархії обмежень [75, 76] належать до найперших і найуспішні-
ших підходів, в яких описуються і використовуються преференції в

системах обмежень. У багатьох випадках потрібно мати можливість
задати обов’язкові (міцні) та необов’язкові (слабкі) обмеження.
Обов’язкові обмеження повинні бути задоволені. Оскільки інші об-

меження необов’язкові, система повинна намагатися задовольнити їх,
однак розв’язок знаходиться навіть у випадку неможливості їх задо-
волення.
Приклад 1 Нехай в заданій системі обмежень є дві змінні A і B і

два рівні преференції – сильний (strong ) і слабкий (weak ):
requiredA B  0

strongA  1

weakB  0
Початкове, обов’язкове обмеження, повинно бути задоволеним.

Друге обмеження із рівнем преференційованості "strong " також може

бути задоволеним у розв'язку {A  1,B   1}. Третім обмеженням, із рі-
внем преференційованості "weak доведеться знехтувати відповідно
"
до існування сильніших обмежень.

Теорію ієрархії обмежень вивчались в університеті Вашингтона
Борнінгом [77, 75, 76, 78, 79]. Логічні визначення «м’яких» обмежень,
базовані на вторинному (і пізніше первинному) порядку, були описа-

ні в [80, 81]. Пізніші теоретичні вивчення включають пов’язання не-
чіткої логіки з ієрархіями обмежень [82], часткове впорядкування об-
межень [83] для підвищення виразності моделі, а також пере визна-
чення компараторів [84] та композиційних моделей [85, 86, 87] для

119