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

1. Парадигма программирования в ограничениях В общем виде задача удовлетворения ограничений задается тремя множествами[1]: X - множество переменных задачи; D - множество областей определения переменных задачи; С - множество ограничений над переменными задачи. Под ограничением понимается любое соотношение между переменными предметной области. В качестве ограничений могут выступать арифметические выражения; логические формулы; таблицы; выражения, формулируемые на языке специализированных теорий. Решением задачи CSP является полное присваивание, которое удовлетворяет всем ограничениям, и в некоторых случаях необходимо получить все решения. Иногда требуется найти такое решение, в котором значения переменных оптимизировали бы некоторый заданный функционал. CSP-задачи принадлежат классу NP-полных задач. Технология программирования в ограничениях предоставляет мощные и гибкие методы, алгоритмы решения задач комбинаторного поиска. Особенности технологии: • С точки зрения конечного пользователя задача CSP формулируется в декларативном виде, на языке близком к языку математики. Порядок задания ограничений несущественен. • Любой алгоритм удовлетворения ограничений должен содержать две обязательных компоненты: а) компоненту, реализующую вывод (распространение); Ь) компоненту, реализующую поиск. • Вывод (распространение) реализуется как целенаправленное сужение изначально заданных областей определения переменных. • Эвристики, используемые в процедурах поиска, разрабатываются не под конкретную задачу, а являются универсальными. • Благодаря архитектуре систем программирования в ограничениях, появляется возможность совместно обрабатывать количественные и качественные ограничения. • Обеспечивается возможность сопровождать модели, отрытые для оперативных модификаций. При добавлении/удалении из модели ограничений нет необходимости писать новые методы решения задачи. В CSP условия задачи описываются декларативно, а алгоритмы поиска решений (распространение и ветвление) остаются скрыты от пользователя, аналогично в РБД декларативно описывается структура и наполнение базы данных, а алгоритмы поддержания согласованности и целостности данных скрыты в используемой СУБД. Очевидно, для реализации такого подхода, средства описания как РБД, так и CSP должны быть типизированы, а сами типы переменных (данных) и отношений над ними должны быть достаточно примитивны для их успешной автоматической интерпретации и обработки. Так, достаточно популярная библиотека программирования в ограничениях Choco[2] позволяет создавать переменные всего 4 различных типов: целый, логический, вещественный и множество целых, причем поддержка вещественного типа до сих пор неполная. Поскольку примитивность типов является существенным ограничением для описания баз со сложными данными и отношениями над ними, был предпринят ряд шагов для расширения функционала РБД, часть из которых будет 110