Page 86 - 4495

Технологія задоволення обмежень

Структуризація межень Управління задоволенням об-
межень

Перетин обмежень Основане на коефіцієнті не-
сумісності по дузі виконання обмежень

Стягування обмежень Контекстний вибір обме-
(логічне вираження) жень

Побудова інтегрованих об- Впорядкування
межень змінних в обмеженнях

Побудова ієрархій обме- Послаблення задачі
жень задоволення обмежень

Зважування обмежень Розширення області
застосування

Розширення області
обмеження

Видалення змінної

Видалення обме-
ження

Рисунок 1 – Методи підвищення ефективності задоволення обмежень

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

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

у даному домені і на вже задоволених та залишкових незадоволених
обмеженнях. Прикладом даної концепції є «стратегія пошуку до пер-
шої невдачі», яка присвоює виділеним змінним найменші можливі
значення. Спосіб впорядкування змінних може бути обчислено апріо-

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

кування змінних (наприклад стратегія пошуку до першої невдачі).

86