Page 85 - 4495

Методи розв’язку

Базовим пошуковим алгоритмом, варіації якого часто застосову-

ються для пошуку рішення CSP є бектрекінг (backtracking). Спершу
він присвоює значення частині змінних, а потім поширює часткове
присвоєння крок за кроком. Кожен раз коли значення присвоєне, тес-

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

одержаний класичними методами.
Інші базові методи називаються технікою сумісності (consistency
techniques) (або поширенням обмежень (constraint propagation)) яка

полягає в виключенні тих значень з доменів змінних, які є несуміс-
ними з будь-якими обмеженнями. Найпростіша техніка сумісності –
це сумісність вузлів, яка використовується для унарних обмежень.
Дугова сумісність розглядається в бінарних обмеженнях. k - суміс-

ність – усуває не сумісність значень у будь-якій системі з k змінними.
Проте, концепція k - сумісністі в чистому вигляді призводить до не

ефективного пошуку в усьому просторі рішень.
Найбільш загальний спосіб розв’язання CSP – задач – це поєд-
нання обох технік. Техніка сумісності може використовуватися спі-
льно з кроками базових пошукових алгоритмів для одержання біль-

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

Для всіх алгоритмів, що базуються на дереві пошуку, важливим є
які змінні і значення присвоюються в першу чергу, для уникнення
глибокого бектрекінгу. Це означає, що велика частина виконаних
присвоєнь повинна бути відмінена, часто така відміна виконується

багаторазово і представляється процедурою, яка називається trashing.

85