Page 82 - 4495

ЗМІСТОВИЙ МОДУЛЬ 2

ОСОБЛИВОСТІ ВИКОРИСТАННЯ ТЕОРІЇ
ОБМЕЖЕНЬ ДЛЯ НАФТОГАЗОВОЇ ПРЕДМЕТНОЇ

ОБЛАСТІ

ЛЕКЦІЯ 13-14

ФОРМАЛЬНА ПОСТАНОВКА ПРОБЛЕМИ

ЗАДОВОЛЕННЯ ОБМЕЖЕНЬ

Проблема задоволення обмежень

Проблема задоволення обмежень полягає в накладенні певних
вимог на скінченну множину змінних у формі обмежень. Множина
можливих значень (доменів) для кожної змінної є скінченною. Кожне
обмеження вказує які кортежі значень є дозволеними для кожної під-

множини базових змінних. Обмеження може бути задано в явній фо-
рмі, через перелічення дозволених кортежів або не явно через алгеб-
раїчні вирази.

Означення 1 (проблема обмежень). Проблемою задоволення
обмежень (CSP) є кортеж ( , , )V D C , де:

V  { ,..., }v v - множина змінних, що називаються доменними змін-
1 n
ними;

D  { ,...,D D } - є множиною доменів. Кожен домен є скінченною
1 n
множиною, що містить можливі значення для відповідних змінних;

C  { ,..., }c c .. - множина обмежень. Обмеження c є відношення
1 n i
означене на підмножині { ,...,v v } всіх змінних, таких що
i 1 i k i
c
{D ,...,D }  .
i 1 i k i i
Множина змінних обмеження c позначається V . Якщо вона міс-
c
тить тільки один чи два елемента, то їх називають унарні (unary) та
бінарні (binary) обмеження відповідно. Всі інші обмеження називати-
мемо не-бінарними (not-binary). CSP називається бінарною CSP якщо

всі її обмеження є унарними та бінарними. Бінарні обмеження віді-
грають особливу роль, оскільки будь-яке обмеження може бути пред-

82