Краткий обзор технологий программирования в ограничениях
Программирование в ограничениях как самостоятельное научное направление сложилось в конце 60-х – начале 70-х годов прошлого века. Примечательно, что первыми приложениями были задачи обработки изображений и параметрического моделирования пространственно-двумерных сцен. С тех пор направление существенно эволюционировало, охватывая новые классы задач и выдвигая новые подходы к их решению.
Тем не менее, по-видимому, не претерпели серьезных изменений четыре фундаментальных принципа, а именно: декларативное моделирование ограничений, локальное распространение результатов, эффективный глобальный поиск решений и специализация языковых и математических средств. Начиная со Sketchpad , ALICE , ThingLab , эти принципы успешно эксплуатируются и в современных реализациях.
Принцип декларативности нашел конструктивное воплощение во многих языках функционального и логического программирования ( включая Lisp и Prolog), допускающих описание и решение некоторых задач в ограничениях. Со временем понимание того, что функциональная рекурсия и логический вывод являются лишь отдельными элементами более общей стратегии разрешения ограничений для сложно структурированных неизвестных переменных, привело к появлению CostraintLisp, Prolog III и CHIP .
Язык реляционных баз данных SQL , предусматривающий развитые декларативные конструкции для описания запросов и ограничений целостности, также несет в себе черты языка программирования в ограничениях. Связь с технологиями управления базами данных становится еще более очевидной при анализе относительно новой концепции Constraint Database (CDВ) , которая, расширяя реляционную, дедуктивную и объектно-ориентированную модели, устанавливает непосредственную связь между типами данных и ограничениями, которые их предопределяют.
Принцип локального распространения (в англоязычной литературе соответствующий терминам constraint propagation или consistency inference) имеет долгую историю и многочисленные приложения, в частности, в области интеллектуализации графических интерфейсов пользователя.
Спекулятивные попытки предвосхитить результаты поиска путем локальных и циклических уточнений частных решений оказались довольно плодотворными при решении больших систем уравнений и неравенств.
Многочисленные “радужные” воплощения принципа привели к созданию целой палитры методов: Red (красный), Orange (оранжевый), Yellow (желтый), Green (зеленый), Blue (синий), DeltaBlue (инкрементально-синий), SkyBlue (небесно-синий), UltraViolet (ультрафиолет), Purple (фиолетовый), DeepPurple (пурпурный), Indigo (темно-синий) . Некоторые из них обеспечивают как полный, так и инкрементальный поиск решений применительно к простым и иерархическим системам ограничений.
Принцип эффективного глобального поиска решений довольно естественен для прикладных задач в ограничениях, большая часть из которых является NP-полными. В отличие от методов распространения, направленных на пропозициональный вывод и локальное улучшение частных решений, методы глобального поиска обеспечивают систематический или стохастический поиск общих решений, удовлетворяющих всем заданным ограничениям. Заметим, что поиск с возвратом (backtracking) в сочетании с локальным распространением нашел применение практически во всех реализациях систем программирования в ограничениях, включая упомянутые выше диалекты языков Lisp и Prolog.
В случаях редукции исходной задачи в ограничениях к типовой математической постановке появляется возможность применения известных и апробированных методов решения. Например, симплекс-метод используется в качестве стандартного математического средства в системе 2LP , а метод комбинаторного поиска на конечных доменах — в успешном коммерческом продукте ILOG Solver .
В некоторых случаях для усиления выразительности языковых средств, а также для упрощения идентификации математических постановок выделяются специальные типы ограничений, и для них предусматриваются особые математические методики. В частности, в CHIP и ILOG Schedule поддерживаются некоторые типовые ограничения, возникающие в задачах планирования и составления расписаний.Специализация языковых и математических средств является общей чертой для всех известных реализаций систем программирования в ограничениях, каждая из которых охватывает лишь некоторые типы ограничений и порождаемые ими классы задач.
Например, Prolog III обеспечивает решение систем линейных ограничений, условий на логических переменных и списках, CHIP — линейных ограничений, условий на логических переменных и конечных доменах, CHARME — условий на конечных доменах, 2LP — только линейных ограничений, ILOG Solver — линейных ограничений и условий на конечных доменах и интервалах, HELIOS — условий на интервалах, NEWTON — нелинейных уравнений. Схожая ситуация сложилась и в области систем конкурентного программирования в ограничениях CCP, к ярким представителям которых следует отнести AKL , Oz , CIAO , TAO . Для краткости в настоящей работе мы не рассматриваем CCP-технологии, адресуя заинтересованного читателя к обзорам .
