Page 87 - 4495

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

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

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

стосування процедури декомпозиції. Застосування генетичних алго-
ритмів дозволяє використовувати клас локальних методів, що дозво-
ляють перехід від однієї повної ініціалізації до іншої.

Оптимізаційні проблеми часто розв’язується з допомогою алго-
ритму метода віток і границь (branch-and-bound algorithm). Даний ал-
горитм використовує евристичну функцію, що виконує зв’язування

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

вного значення, обчислюється значення евристичної функції даного
присвоєння (наприклад, часткова оцінка значення цільової функції).
Якщо це значення перевищує границю (наприклад, поточне найкраще
обчислюване значення цільової функції), тоді не виконується обхід

піддерева нижче часткового присвоєння.

Програмування в обмеженнях

Найбільш природною парадигмою програмування для інтеграції
обмежень в програму користувача представляє логічне програмуван-
ня [15, 16, 17]. Логічне програмування забезпечує ефективний спосіб
розділення логічно-декларативної частини програми і частини, що

відповідає за контроль процесу пошуку. Ефективною реалізацією да-
ного класу є мова логічного програмування Пролог (наприклад,
SICStus Prolog [36, 37], ECLіPSе [38], CHIP [39]). Логічне програму-

вання в обмеженнях (Constraint logic programming - CLP) – розширює
стандартну процедуру уніфікації логічного програмування через до-
давання концепції задоволення обмежень. Проте, логічне програму-
вання не є єдино можливою основою для побудови концепції CLP,

оскільки така парадигма була успішно інтегрована в інші мови про-

87