Программирование в ограничениях

Constraint-пролог: операционная семантика

Лекция №14

Программирование в ограничениях (constraint programming) – достаточно новое направление в декларативном программировании. Появилось оно во многом в результате развития систем символьных вычислений, искусственного интеллекта и исследования операций.

Программирвание в ограничениях – это программирование в терминах "постановок задач".

Постановка задачи – это конечный набор переменных V = {v[1],..., v[n]}, соответствующих им конечных (перечислимых) множеств значений D = {D[1],...,D[n]}, и набор ограничений С = {C[1],...,C[m]}. Ограничения представлены как утверждения, в которые входят в качетсве "параметров" переменные из некоторого подмножества V[j],j=1..m набора V. Решение такой задачи – набор значений переменных, удовлетворяющий всем ограничениям C[j].

Синтаксически такую постановку задачи пожно записать как "правило" для "типизированного" Пролога:

problem(V1:D1,..., Vn:Dn):- С1,... Cm.

Семантически, однако, программирование в ограничениях отличается от традиционного логического программирования в первую очередь тем, что исполнение программы рассматривается не как доказательство утверждения, а нахождение значений переменных. При этом порядок "удовлетворения" отдельных ограничений не имеет значения, и система программирования в ограничениях, как правило, стремится оптимизировать порядок "доказательства" утверждений с целью минимизации отката в случае неуспеха. С этой целью набор ограничений может быть соответствующим образом преобразован – по правилам, аналогичным правилам Пролога. Любую задачу можно рассматривать как ограничение: "значения переменных должны быть решением этой задачи". Часто о программировании в ограничениях говорят исключительно как о "дополнительной" ветви логического программирования.

В качестве примера, мы можем задать системе программирования в ограничениях следующий запрос:

? (X: integer) X>1, member(X, [1,2,3]).

Типичная Пролог-система на таком запросе выдаст ошибку: Х является неинициализированной переменной, и его нельзя сравнивать с числом 1. Система, поддерживающая программирование в ограничениях, воспримет эти "утверждения" как ограничения (а не как цели, которые требуется доказать), и выдаст нам требуемые решения: Х=2 и Х=3.

Это может быть реализовано, например, следующим образом: при "прологовском" доказательстве утверждения Х>1 будет выведено ограничение на переменную Х (естественно, Х>1). Результаты доказательства следующей подцели (member(...)) будут проверяться на удовлетворение этому ограничению (фактически, будет передоказываться утверждение X>1 для конкретных значений Х). Первый вариант (Х=1) не пройдет эту проверку, остальные будут приняты как удовлетворяющие выведенному ограничению.

Задачу в ограничениях можно рассматривать и как задачу о минимальном необходимом наборе ограничений, что позволяет в некоторых случаях описать в явном виде бесконечные множества решений. Так, минимальным необходимым набором ограничений для задачи X:integer, X>2, X<4 будет Х=3; для задачи X,Y:integer, X*2=Y таким набором будет X:integer, Y mod 2 = 0.

Системы символьных вычислений нередко позволяют использовать "допущения" – по сути, те же ограничения. И на следующий (простой) запрос:

assume X>0.

when X+1<10?

выдавать ответ:

X in (0..9).

Как правило, такие системы могут доказывать достаточно нетривиальные матичематические утверждения, выводя "минимальными необходимыми ограничениями", и проверяя эти ограничения на совместность.

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

Кроме этого, программирование в ограничениях естественным образом приложимо к задаче автоматического вывода типов: выведенные ограничения на переменные, соответствующие типам подвыражений, будут задавать "минимальный набор требований на типы". Так, удовлетворение ограничения type_correct("lambda x -> x+1") потребует выполнения набора ограничений {number(x.type_of)}, что, буквально, обозначает, что для того, чтобы прибавить к х единицу, х должно быть числом.

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

Программирование в ограничениях – это удобный подход к формулировке и решению задач, которые могут быть естественным образом представлены в терминах ограничений, заданных в множестве переменных. Решение подобных задач заключается в поиске таких комбинаций значений переменных, которые соответствуют ограничениям. Этот процесс называется удовлетворением ограничений. Логическое программирование в ограничениях (Constraint Logic Programming – CLP) представляет собой сочетание подхода к решению задач в ограничениях с логическим программированием. При использовании метода CLP средства удовлетворения ограничений встраиваются в логический язык программирования, такой как Prolog.

Дата добавления: 2014-01-07