Page 88 - 4495

грамування, такі як C++ бібліотеки – ILOG [40, 41] чи об’єктно-
орієнтованою мовою Oz [42].
Базова структура концепції CLP для розв’язання проблеми задо-
волення обмежень є однаковою в більшості реалізацій і складається з

кількох частин. Перша частина містить визначення всіх змінних про-
блеми з їхніми доменами. Домени змінних зменшуються завдяки об-
меженням, які встановлюються на наступному кроці. Метод пошуку в

просторі рішень описується через маркування (labeling) або через пе-
речислення (enumeration) – процес генерації значень для окремих
змінних домену. Описана структура може бути переписана наступ-
ним CLP кодом:

solve(Variables) :-
define_variables(Variables),
state_constraints(Variables),

labelling(Variables).
Дерево пошуку може бути описано через наступний код, де еври-
стика впорядкування значень та змінних затосовується до початку

присвоєння значень викликаючи процедуру поширення обмежень.
labelling(Variables) :-
select_variable(Variables, Variable, Rest),

select_value(Variable, Value),
Variable #= Value,
labelling(Rest).

Символ # використовується для розділення операторів логічного
програмування і логічного програмування в обмеженнях.
Процедура маркування може також бути використана для пошуку

розв’язку оптимізаційної проблеми з деякою цільовою функцією F ,
тобто:
state_constraints(Variables,F),

labelling([minimize(F)], Variables), де цільова функція F
над змінними в домені Variables є описаною на першому кроці і її
значення мінімізоване на другому.

Глобальні обмеження
Бінарізація обмежень може бути причиною різкого збільшення
простору рішень, тому розв’язок може бути і не знайдений за виділе-
ний проміжок часу. Для усунення цього недоліку використовують

спеціальні алгоритми поширення обмежень для розв’язання виділе-
них підпроблем описаних на певній підмножині змінних за допомо-

гою так званих глобальних обмежень. Моделювання проблеми через

88