Труды КНЦ вып.124 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ вып. 5/2014(24))

Ограничение С - отношение, определённое на подмножестве значений всех переменных, т.е. С, с Dj х ... х Dn. Заданная (частичная или полная) подстановка значений переменных удовлетворяет ограничению Сг, если каждая переменная получила такое значение, что соответствующий кортеж значений принадлежит Сг . Множество всевозможных подстановок для всех переменных является пространством, содержащим решение CSP-задачи. Решением CSP-задачи является такая подстановка для всех переменных, при которой все ограничения удовлетворены. Если для некоторой задачи имеется, по крайней мере, одно решение, то задача является разрешимой, иначе - неразрешимой (противоречивой, переограниченной). В некоторых случаях необходимо получить все решения. Иногда может быть сформулирована задача ограниченной оптимизации, а именно: найти такое решение, в котором значения переменных оптимизировали бы некоторый заданный функционал. Зачастую необходимо просто выяснить, разрешима ли задача. В любом случае, CSP-задачи принадлежат классу NP-полных задач [1]. В качестве известных примеров задачи удовлетворения ограничений можно привести [ 2 ]: • задача о раскраске карты; • задача о назначениях; • задача составления расписаний; • задачи транспортного планирования; • задачи комбинаторной оптимизации. Существует два основных подхода к решению задач удовлетворения ограничений. Первый подход основан на методах систематического перебора решений. При этом перебор можно представить как обход дерева поиска, а путь до каждого листьевого узла описывается одним кортежем значений переменных. Следует отметить две отличительные черты такого подхода: 1. При существовании решений задачи они будут гарантированно найдены, в противном случае будет установлена неразрешимость задачи. 2. Процедуры обхода дерева поиска обладают экспоненциальной сложностью, что делает задачу практически не решаемой без применения специализированных методов ускорения перебора. Существуют также модификации методов обхода дерева в глубину, позволяющие сузить область поиска: 1. Методы распространения ограничений, которые отсекают некоторые ветви дерева поиска, заведомо не удовлетворяющие условиям задачи. Это позволяет значительно сократить количество перебираемых вариантов. Однако сам способ отсечения ветвей сильно зависит от конкретной задачи и не гарантирует увеличения эффективности перебора в общем случае. 2. Методы декомпозиции, осуществляющие разбиение задачи на несколько подзадач при условии, что комбинация их решений является решением исходной задачи. Как и в случае с распространением ограничений, есть сильная зависимость от специфики задачи. Альтернативный подход основан на методах локального поиска - вместо систематического перебора всех возможных вариантов, выбор преемника текущего состояния задачи поиска зависит только от самого этого состояния. В 159