Page 83 - 4495

ставлено еквівалентними бінарними. Процес цього перетворення на-
зивається бінарізацією обмежень (constraint binarization). На практиці,
тим не менше, ця трансформація приводить до появи надто великої
кількості додаткових змінних з великими доменами, що значно

ускладнює розв’язок нової проблеми.
Структура CSP задачі може бути представлена графом обмежень.
Найбільш простий граф обмежень, що ідентифікує бінарне CSP є та-

ким, що його вершини відповідають змінним, які з’єднані дугами,
якщо обмеження містить обидві змінні.
Означення 2. Присвоєння (assignment) – це є відображення  з
множини доменів змінних Y  в їхні відповідні домени, тобто
V
 ( )v  для. Множина всіх присвоєнь для Y позначається. .
D
i i Y
Нехай змінні в Y містяться в певному фіксованому порядку
( ,...,v v ). Присвоєння  , що відповідає {( ,v d ),...,( ,v d )} записується
1 m 1 1 v m m v
як   (d ,...,d ). Іноді кажуть, що (value )tuple (d ,...,d ).
1 v m v 1 v m v
Присвоєння, означенеv  на множині доменних змінних V є
Y
i
повним, в іншому випадку його називають частковим. Множина всіх
можливих повних присвоєнь   D  ... D – називається простором
V 1 n
розв’язків, в тому розумінні, що розвязок можна знайти в цьому про-
сторі.

Означення 3. Обмеження c задовольняється в присвоєнні  (по-
значимо це   ), якщо всі його змінні отримують значення такі, що
c
відповідні значення кортежів належать c. У протилежному випадку
обмеження називається незадоволеним.

Для будь-якого заданого обмеження c ( ,...,v v ), введемо
i 1 i m i
 c ( ,...,v v ) яке оночасно незадовольняється в випадку, коли c задо-
i 1 i m i i
вольняється.
Означення 4 (розв’язок). Часткове присвоєння  є послідовним
(consistent), якщо всі обмеження, що відносяться тільки до змінних

присвоєних  є задоволеними.
Розв’язком CSP V, D, C  є послідовне повне присвоєння, тобто,
всі обмеження з множини C повинні бути задоволені.

Якщо CSP задача немає ніякого розв’язку, то проблема назива-
ється над-обмеженою (over-constrained) або несумісною (inconsistent)
і CSP задача з більше як одним розв’язком вважатимемо не достат-

ньо-обмеженою (under-constrained). Обмеження є послабленим
(relaxed) якщо до відношення додатково додано елементи. Якщо такі

83