Введение. 
Программирование в ограничениях и недоопределенные модели

недоопределенный модель программирование ограничение В современном программировании можно выделить несколько основных парадигм: императивное или алгоритмическое программирование (C, Pascal), логическое программирование (Prolog), функциональное программирование (LISP, РЕФАЛ) и др. Важное место в этом ряду занимает программирование в ограничениях (constraint programming), которое за последние несколько лет развивается особенно активно и становится все более популярным.

Программирование в ограничениях является по своей сути максимально декларативным и основано на описании модели задачи, а не алгоритма ее решения [1, 2]. Модель специфицируется в виде неупорядоченной совокупности отношений, которые соответствуют связям, существующим между параметрами задачи. Эти отношения, называемые общим термином «ограничения» могут иметь вид уравнений, неравенств, логических выражений и т. п.

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

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

В самом общем виде постановка задачи в парадигме программирования в ограничениях формулируется следующим образом. Пусть на переменные x₁, x₂ …, x_n, областями значений которых являются множества X₁, X₂, …, X_n, заданы ограничения C_i (x₁, x₂, …, x_n), i =1, k. Требуется найти наборы значений 1, a₂, …, a_n> (a_i X_i), которые бы удовлетворяли всем ограничениям одновременно.

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

Реальное программирование в ограничениях особенно полезно там, где кончаются возможности обычной математики. Оно используется при решении задач планирования, проектирования, прогнозирования, в инженерных и экономических расчетах, при создании графических интерфейсов, в системах понимания естественного языка и др. Среди наиболее известных зарубежных систем, реализующих парадигму программирования в ограничениях, можно отметить Prolog III [3], CLP® [4], CLP (BNR) [5], clp (FD) [6], CHIP [7], ILOG Solver [8], Newton [9] и др.

Одним из наиболее развитых и практически значимых подходов, относящихся к программированию в ограничениях, являются недоопределенные модели.

Метод недоопределенных моделей (Н-моделей) был предложен в начале 80-x годов [10−12] для представления и обработки неполностью определенных знаний. Рассматриваемый вначале как оригинальный метод из области искусственного интеллекта, он трансформировался постепенно в прикладную технологию программирования в ограничениях. Технология Н-моделей выделяется среди других подходов вычислительной мощностью, универсальностью и эффективностью. Фактически она является единственной технологией, которая позволяет решать задачу удовлетворения ограничений в самой общей постановке.

К настоящему времени на базе Н-моделей создана многоуровневая технология программирования, позволяющая решать качественно новые классы задач в таких областях, как экономика, инженерные расчеты, календарное планирование, вычислительная математика, САПР, ГИС и др. Среди систем, реализованных на основе аппарата Н-моделей, можно отметить такие, как UniCalc [13], НеМо-ТеК [14], LogiCalc [15] и Time-Ex [16].

Наш Институт планирует в журнале «Информационные Технологии» серию публикаций о наиболее интересных разработках, базирующихся на технологии Н-моделей и задача данной статьи дать читателю общую информацию о специфике и возможностях как самого этого аппарата, так и в целом о программировании в ограничениях.

Статья организована следующим образом. В первой главе рассматриваются основные понятия, лежащие в основе аппарата Н-моделей и пример, поясняющий идеи алгоритма вычислений. Во второй главе вводится понятие недоопределенного расширения и рассматриваются примеры таких расширений. В третьей главе описываются недоопределенные модели и типы данных, используемые в Н-моделях, а также приводится алгоритм вычислений. В четвертой — показаны некоторые возможные применения аппарата Н-моделей.