Программирование в ограничениях (или программирование ограничениями) является парадигмой программирования, в которой отношения между переменными указаны в форме ограничений. Ограничения отличаются от общих примитивов языков императивного программирования тем, что они определяют не последовательность шагов для исполнения, а свойства искомого решения. Это делает программирование в ограничениях формой декларативного программирования. Ограничения, которые используются в программировании в ограничениях, бывают различных видов: те, которые используются в задачах удовлетворения ограничений (например, "А или В истинно"), те, которые решаются симплекс-алгоритмом (например, "x ≤ 5") и другие. Ограничения, как правило, встроены в язык программирования или осуществляются через отдельные программные библиотеки.

Программирование в ограничениях тесно связано с теорией удовлетворения ограничений, которая предлагает удобный аппарат и простую формальную схему для представления и решения комбинаторных задач искусственного интеллекта.

Программирование в ограничениях началась с логического программирования с ограничениями (ЛПО), которое является вкладыванием ограничений в логическое программирование. Появление этого варианта логического программирования связано с именами Jaffar и Lassez, которые расширили в 1987 году определенный класс ограничений, которые были введены в Prolog II. Первыми реализациями логического программирование в ограничениях были Пролог III, CLP (R) и CHIP. Некоторые интерпретаторы логического программирования в ограничениях существуют и сегодня, например GNU Prolog.

Помимо логического программирования, ограничения могут быть смешаны с функциональным программированием, переписыванием термов и императивным языком. Языки программирования с встроенной поддержкой ограничений включают Oz (функциональное программирование) и Kaleidoscope (императивное программирование). Главным образом, ограничения осуществляются в императивных языках через инструментальные средства для решения задач с ограничениями, которые являются отдельными библиотеками для существующих императивных языков.

Логическое программирование в ограничениях

Временные ограничения параллельного программирования (КТС) и недетерминированных временные ограничения параллельного программирования (NTCC) являются варианты программирование в ограничениях, которые могут иметь дело со временем.

Некоторые популярные языки программирования с ограничениями

CHIP был первым языком ЛПО, использующим распространение ограничений. Другими примерами систем ЛПО могут служить библиотеки поддержки ограничений ILOG и COSYTEC, а также языки логического программирования в ограничениях Prolog III, Prolog IV, CLP(R), ECLiPSe, CIAO, CLP(FD). Используя эти системы, многие сложные прикладные задачи были успешно решены с помощью технологий программирования в ограничениях. В числе примеров упомянем проверку электронных схем, календарное планирование, распределение ресурсов, составление расписаний, управляющие системы, графические интерфейсы, а также множество комбинаторных задач.

Литература

• Apt K. R. Principles of Constraint Programming. New York: Cambridge University Press, 2003. 407 p.
• Rossi F., van Beek P., Walsh T. (eds.) Handbook Of Constraint Programming. Elsevier, 2006. 978 p.
• Ушаков Д.М., Телерман В.В. Системы программирования в ограничениях (обзор) // Системная информатика: Сб. науч. тр. Новосибирск: Наука, 2000. Вып.7: Проблемы теории и методологии создания параллельных и распределенных систем. С. 275-310.
• Щербина О.А. Удовлетворение ограничений и программирование в ограничениях, препринт, 2012.

См.также

• Комбинаторная оптимизация
• Эвристический алгоритм
• Оптимизация (математика), (математическое программирование)

Внешние ссылки