Труды КНЦ вып.9 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ) вып. 9/2019(10)

переменных {Х\, Х 2 , Х„) . D — множество доменов {D\, / К /)„). где Д является доменом (областью определения) переменной X,. С — множество ограничений {С і, Сг, Ст}, которые предписывают допустимые комбинации значений переменных. Каждый домен Д описывает множество допустимых значений {ѵі, ..., ѵ*} для переменной X,. Под ограничением понимается любое соотношение между переменными предметной области. В качестве ограничений могут выступать арифметические выражения; логические формулы; таблицы; выражения, формулируемые на языке специализированных теорий. Решением задачи CSP является полное присваивание, которое удовлетворяет всем ограничениям. В некоторых случаях необходимо получить все решения. Иногда требуется найти такое решение, в котором значения переменных оптимизировали бы некоторый заданный функционал. CSP-задачи принадлежат классу NP-полных задач. Технология программирования в ограничениях предоставляет мощные и гибкие методы, алгоритмы решения задач комбинаторного поиска. Особенности технологии: 1. С точки зрения конечного пользователя задача CSP формулируется в декларативном виде, на языке близком к языку математики. Порядок задания ограничений несущественен. 2. Любой алгоритм удовлетворения ограничений должен содержать две обязательных компоненты: а) компоненту, реализующую вывод (распространение); б) компоненту, реализующую поиск. 3. Вывод (распространение) реализуется как целенаправленное сужение изначально заданных областей определения переменных. 4. Эвристики, используемые в процедурах поиска, разрабатываются не под конкретную задачу, а являются универсальными. 5. Благодаря архитектуре систем программирования в ограничениях, появляется возможность совместно обрабатывать количественные и качественные ограничения. 6. Обеспечивается возможность сопровождать модели, отрытые для оперативных модификаций. При добавлении/удалении из модели ограничений нет необходимости писать новые методы решения задачи. Программирование в ограничениях особенно полезно там, где нет возможности получить удовлетворительное/адекватное решение средствами «обычной» математики. Оно используется при решении задач планирования, проектирования, прогнозирования, в инженерных и экономических расчетах, при создании графических интерфейсов, в системах понимания естественного языка и др. [6, 7]. Весь процесс рассуждений на ограничениях сводится к поэтапному усечению изначально заданных областей определения переменных. Любой метод удовлетворения ограничений должен проектироваться особым образом и состоять из двух основных частей: части, реализующей поиск и части, реализующей вывод на ограничениях. Начнем с описания части, отвечающей за вывод. Как правило, под выводом на ограничениях понимается процесс сокращения размерности пространства поиска, обеспечивающий “сужение” доменов переменных, упрощение ограничений и т.п. и, при этом, имеющий низкую вычислительную сложность (оценивается полиномом низкой степени). Алгоритмы, реализующие вывод на ограничениях, называются алгоритмами- 128