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

7. Библиотеки программирования в ограничениях содержат высокоэффективные алгоритмы вывода для обработки, так называемых, глобальных ограничений. Знания подобных ограничений позволяет конструировать, как из кирпичиков, модель решаемой задачи. Программирование в ограничениях особенно полезно там, где нет возможности получить удовлетворительное/адекватное решение средствами «обычной» математики. Оно используется при решении задач планирования, проектирования, прогнозирования, в инженерных и экономических расчетах, при создании графических интерфейсов, в системах понимания естественного языка и др. Процесс решения задач удовлетворения ограничений строится на применении алгоритмов трех основных типов [1]: • Алгоритмы фильтрации - алгоритмы, сокращающие домены переменных, участвующих в одном ограничении. • Алгоритмы распространения - алгоритмы передающие (распространяющие) изменения доменов переменных, произошедшие в рамках одного ограничения, на другие ограничения задачи. • Алгоритмы поиска - алгоритмы, находящие конкретные решения задачи путем присваивания конкретных значений переменным с последующим распространением внесенных изменений. Иногда алгоритмы первых двух типов называют алгоритмами- распространителями или алгоритмами-пропагаторами. Архитектура систем программирования в ограничениях напоминает архитектуру вычислительных машин (рис. 1). В качестве своеобразной шины данных в системах программирования в ограничениях выступает так называемое хранилище ограничений, представляющее собой, список пар «переменная - перечень значений переменной, которые она может принимать на текущем этапе вывода». Аналогом центрального процессора выступает алгоритм - дирижер (управляющая подпрограмма), реализующий базовую стратегию поиска. В случае систематического поиска данный алгоритм выбирает переменную и присваиваемое значение переменной. Далее начинается работа алгоритмов распространения, которые должны установить порядок вызова тех или иных процедур фильтрации. Как правило, априорно задаются приоритеты обработки тех или иных ограничений. В качестве сопрограмм выступают подпрограммы, реализующие вывод на ограничениях, - алгоритмы фильтрации ограничений. Для различных типов ограничений и типов областей определения переменных разрабатываются различные алгоритмы фильтрации. Продолжая аналогию с архитектурой вычислительных машин, процедуры-фильтрации соотносятся с дополнительными устройствами (оперативная память, жесткий диск и т.п.), достаточно гибко подключаемыми через шину данных. Кроме стандартных типов ограничений и алгоритмов- распространителей, в рамках библиотек программирования в ограничениях существует возможность создания пользовательских типов ограничений и соответствующих процедур распространения. Основное внимание в настоящей статье сосредоточено на обзоре глобальных ограничений, которые реализованы в рамках наиболее популярных библиотек Constraint Programming: Choco, GeCode, JaCoP, MiniZinc. 69