автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методы интеграции логического программирования и программирования в ограничениях

РОССИЙСКАЯ АКАДЕМИЯ НАУК Институт систем информатики им. А. П. Ершова

На правах рукописи

Петров Евгений Сергеевич

МЕТОДЫ ИНТЕГРАЦИИ ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ И ПРОГРАММИРОВАНИЯ В ОГРАНИЧЕНИЯХ

05.13.11 — математическое и программное обеспечение

вычислительных машин, комплексов и сетей Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Новосибирск 1999

Работа выполнена в Институте систем информатики имени А. П. Ершов Сибирского отделения Российской академии наук (ИСИ СО РАН).

Научный руководитель — Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук, доцент Яхпо Т. М.

доктор физико-математических наук, профессор Евстигнеев В. А.

доктор физико-математических наук, профессор Палъчунов Д. Е.

Иркутский государственный университет

Защита состоится 16 апреля 1999 в 14 час. 30 мин. на заседании диссертационного совета К0003.93.01 в Институте систем информатики Сибирского отделения РАН по адресу:

630090, Новосибирск, пр. акад. Лаврентьева, 6.

С диссертацией можно ознакомиться в читальном зале библиотеки ВЦ СО РАН (пр. акад. Лаврентьева, 6)

Автореферат разослан Л . С Ъ

Ученый секретарь диссертационного совета К0003.93.01 к.ф.-м.н.

М. А. Бульонков

РОССИЙСКАЯ ОСУДАРСТВЕННАЯ БИБЛИОТЕКА

Общая характеристика работы

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

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

Такая неполнота является частным видом "недоопределенности", изучаемой в рамках недоопределенных вычислительных моделей, предложенных А. С. Нариньяни в начале 80-х годов в качестве средства представления и обработки знаний. С начала 90-х годов недоопре-деленные вычислительные модели с успехом используются в программировании в ограничениях. Среди достоинств недоопределенных вычислительных моделей как метода программирования в ограничениях выделяются два: 1) применимость к решению задач со смесью данных различных типов и 2) возможность настройки на предметную область решаемой задачи.

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

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

задач и дальнейшее направление совершенствования.

В настоящее время методы программирования в ограничениях активно используются в рамках двух парадигм: объектно-ориентированной и логической. Более органичным сочетанием, в силу декларативности обеих его составляющих, представляется логическое программирование в ограничениях. Однако все известные системы логического программирования в ограничениях изначально ориентированы на строго определенные классы задач. Актуальным является создание систем логического программирования в ограничениях, настраиваемых на предметную область решаемой задачи, и разработка соответствующих методов.

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

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

Научная новизна работы состоит в следующем: • разработан метод интеграции недоопределенных вычислительных моделей н логического программирования, который повышает эффективность логических программ путем автоматического учета в логическом выводе неполной информации; для случая интервальной недоопреде-ленности установлено необходимое и достаточное условие сходимости вычислений в таких моделях при решении линейных уравнений, установлена связь со сходимостью классических методов Зейделя, Якоби;

• разработаны средства представления и обработки множеств в недо-определешшх вычислительных моделях, которые позволяют эффективно использовать интенсиональные и экстенсиональные спецификации множеств для решения комбинаторных задач; разработаны язык для описания таких задач и его интерпретатор Ьо^Са1с, использующий предложенные средства представления и обработки множеств;

• разработана Интервальная библиотека для системы логического про-граммировагам ЕСЬ'РБ®, предназначенная для автоматического учета в логическом выводе нелинейных ограничений над веществешшми значениями; библиотека включает средства для спецификации массовых ограничений, символьных преобразований, управления процессом вычислений; на основе Интервальной библиотеки разработаны приложения для решения задач автоматического проектирования и моделиро-

■ ■ ваши финансовых операций.

• /Практическая ценность работы состоит в разработке нового метода представления и обработки неполных (неточных) данных в логических программах, легко адаптируемого к данным различных типов и различным классам задач, в создании Интервальной библиотеки, позволяющей учитывать при логическом выводе нелинейные ограничения.

: Апробация работы и публикации.. Исследования по теме диссертации были поддержаны грантом 96-01-01608 Российского фонда фундаментальных исследований и грантом 98-06 Франко-русского центра по прикладной математике и информатике им. А. М. Ляпунова.

Результаты работы неоднократно докладывались на семинаре лаборатории Искусственного интеллекта, на 8-й Европейской летней школе "Логика, язык, информация" (Прага, Чехия, 1996), 3-й конференции "Перспективы системной информатики" (Новосибирск, 1997), 6-й Скандинавской конференции по искусственному интеллекту (Хельсинки, Финляндия, 1997), 3-м Сибирском конгрессе по индустриальной и прикладной математике (Новосибирск, 1998), 3-й Объединенной конференции по разработке систем, основанных на знаниях (Смоленице, Словакия, 1998), на объединенном семинаре лаборатории Системного программирования и лаборатории Искусственного интеллекта ИСИ СО РАН. -1

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 69 наименований. Объем работы составляет 122 страницы. Работа включает 4 таблицы и 9 рисунков.

Содержание работы

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

Глава 1 посвящена недоопределенным вычислительным моделям, их свойствам и рассмотрению таких моделей в контексте программирования в ограничениях.

В разделе 1.1 вводятся термины, используемые на протяжении всей работы, дается краткий обзор методов решения задач удовлетворения ограничениям (1.2), устанавливается связь между задачами удовлетворения ограничениям и недоопределенными вычислительными моделями (1.3), приводится общий алгоритм вычислений в таких моделях (1.4). В разделе 1.6 исследуется сходимость вычислений в моделях с интервальной недоопределенностью при решении линейных уравнений.

Принято считать, что основы программирования в ограничениях были заложены в середине 70-х годов А. Макверсом, У. Монтанари, Е. Фредером, хотя ключевые идеи высказывались еще Ю.И, Журавлевым, Э. Тыугу, Д. Уолцем с начала 60-х годов.

В программировании в ограничениях решаются так называемые задачи удовлетворения ограничениям (CSP, "Constraint Satisfaction Problem"), в которых по заданной системе ограничений (набору формул) некоторой сигнатуры и модели этой сигнатуры требуется отыскать набор значений, удовлетворяющий в этой модели одновременно всей системе. Сигнатура перечисляет средства, доступные, для описания предметной области, а ее модель фиксирует способ понимания этих средств, принятый в этой предметной области. Выберем некоторую сигнатуру и ее модель и будем ссылаться на эту модель как на "стандартную модель".

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

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

публикаций по данной тематике, начинающихся с 1980 г.

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

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

В н-расшпрении каждая система ограничений обладает таким решением 7т, что для каждого другого ее решения *у и каждой переменной х выполняется *~/(х) С 7т(х). Решение 7т называется недоопределен-ным решением системы ограничений.

Н-решение системы ограничений находится методом недоопределен-ных вычислений (н-вычислений). Метод работает с некоторым "текущим" означиванием, постепенно приближая его к н-решению. Как метод программирования в ограничениях н-вычнсления относятся к методам обеспечения локальной совместности. Н-вычисления складываются по принципу управления по данным из исполнения отдельных вычислительных функций. Целью этих действий является согласование текущего решения со всей системой ограничений.

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

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

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

В разделе 1.6 автор исследует сходимость в недоопределенных вычислительных моделях при решении линейных уравнений. Пусть дана система п линейных уравнений х = Ах + /. Будем рассматривать ее как систему п ограничений. Хотя исследуемая система ограничений содержит п2 вхождений переменных, для простоты будем считать, что н-значение переменной х,- доопределяется на основе лишь уравнения г, т.е. требуется не более п вычислительных функций.

Предположим, что х* — решение системы х = Ах + /. Будем говорить, что н-вычисления сходятся, если п-мерный интервал, даваемый н-вычислениями, при увеличении точности вычислений стремится к {а:*}. Сходимость н-вычислений влечет единственность решения системы х — Ах + /. Относительно сходимости н-вычислений при решении системы х — Ах + / в работе доказываются следующие теоремы.

Теорема 1.1 (необходимое условие сходимости). Пусть для системы линейных уравнений х = Ах + / сходятся н-вычисления.

Тогда найдется такой вектор-строка а > что

а(Е — |Л|) > 1т.

В комментарии к Т. 1.1 показано, что сформулированное условие является также и достаточным.

Теорема 1.2 (связь методов н-вычислений, Зейделя, Якоби). Пусть для системы линейных уравнений х — Ах+/ сходятся н-вычисле-ния. Тогда для системы линейных уравнений х = Ах+/сходятся метод Зейделя и метод Якоби.

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

Теорема 1.3 (связь методов н-вычислений, Якоби). Пусть элементы матрицы А неотрицательны.

Тогда (н-вычисления сходятся для системы х — Ах + /) (метод

Якоби сходится для системы х — Ах + /).

Глава 2 посвящена подходам к интеграции недоопределенных вычислительных моделей и системы логического программирования ЕСЬ'РБ6.

В разделе 2.1 кратко описаны способы формализации современного логического программирования посредством систем переписывания термов (2.1.1) и посредством сведения к семантическому програм-

мированию (2.1.2). Далее приводятся необходимые сведения о системе ECL'PSe (2.2) и описывается представление системы ограничений в виде вычислительной сети, предназначенное для организации н-вычис-лений в системе ECL'PS6 (2.4.1), и описывается организация управления (2.4.2),

Можно выделить три парадигмы в программировании, существенным образом использующие математическую логику в процессе решения задач: логическое программирование, логическое программирование в ограничениях и так называемое ^-программирование.

Основы собственно логического программирования были заложены Р. Ковальским (теоретические вопросы), А. Колмероэ (первая реализация), Д. Уорреном (эффективная реализация интерпретатора языка Prolog) в середине 70-х годов. На конец 70-х — начало 80-х годов пришелся первый пик в развитии систем логического программирования.

Второй этап развития связан с применением в логическом программировании методов программирования в ограничениях. Первой промышленной системой логического программирования в ограничениях считается система CHIP (Г. Симонис, П. ван Хентенрик и др., 1988). За ней последовали Prolog-Ill (А. Колмероэ, 1990), CLP(BNR) (У. Олдер, Ф. Бенаму., 1990), Флэнг (A.B. Манцивода, 1991), ECL'PSe (М. Майер, И. Шимф и др., 1992).

К началу 90-х годов Ж. Коэном были сформулированы следующие принципы логического программирования в ограничениях. Логическая программа с ограничениями представляет собой конечный набор предложений вида "д0 <— gi,..., дп, С", где — цели (атомарные формулы), не являющиеся ограничениями, С — множество ограничений. Вычисление логической программы с ограничениями моделируется работой недетерминированной машины. Состояние машины определяется цепочкой целей tj, накопленной системой ограничений S и подстановкой W, хранящей вычисленные значения переменных.

На каждом шаге машина заменяет в цепочке первую цель to на 9i > (.- • ,9п, расширяет систему ограничений до С U S U {.до = ¿о})- Если она совместна, то подстановка W меняется на W0, задающую значения переменных, которые полностью определены новой системой ограничений. Для вычисления W0 применяются методы программирования в ограничениях, математического программирования и т.п. Новым состоянием становится (We,[gi0,... ,дп9,... ,tj,.. ,],С U S U {до = ¿о})-Заключительным является любое состояние с пустой цепочкой целей.

Ответ на запрос пользователя совместно дают получившаяся подстановка и остаточная система ограничений.

Существенным недостатком созданных по такой схеме систем (Prolog-Ill, CLP(BNR)) является "замкнутость", отсутствие возможности дополнить готовую систему модулем для решения систем ограничений какого-либо нового класса; имеется лишь возможность создать полностью новую систему с более широкими возможностями.

Семантическое (Е-) программирование, предложенное в начале 80-х годов Ю.Л. Ершовым, С.С. Гончаровым, Д.И. Свириденко, синтезирует в себе большую часть логико-математических подходов в программировании: логическое, функциональное, трансформационное программирование, концепции "абстрактныхтипов данных", синтез программ.

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

Каждая Е-схема, по сути, является системой "уравнений" относительно предикатных (функциональных) переменных и базовых предикатов и констант. Отдельное такое "уравнение" выражается Е-фор-мулои, вид которой ограничивается так, чтобы каждая Е-программа определяла монотонный оператор. Денотационная семантика данной Е-программы определяется как наименьшая неподвижная точка такого оператора.

Одной из практических реализаций принципов Е-программирования является язык Флэнг, разработанный под руководством А.В. Манци-воды в начале 90-х г. и объединяющий парадигмы функционального и логического программирования. Флэнг предназначен для обработки символьной информации и решения сложных комбинаторных задач, специфицированных при помощи ограничений над переменными с конечными областями значений (конечными доменами).

Программы на Флэнге являются разновидностью Е-программ: их поведение и денотационная семантика хорошо описываются в рамках Е-программирования. Например, конечные домены во Флэнге моделируются переменными, связанными в Е-формулах ограниченными кванторами. 4

Система ECL'PS6 более тяготеет к схеме Ж. Коэна, однако новые типы данных "метатерм" и "отложенная цель", поддерживаемые этой системой, позволяют расширять возможности системы ее же средствами.

Метатерм состоит из обычного терма и термов, являющихся значениями его атрибутов. С точки зрения стандарта языка Пролог мета-термы являются термами. Метатерм, состоящий из обычного терма t и термов Vi, которые являются значениями атрибутов а,-, записывается в виде t{ai :vi,a2-V2, ■ ■ - }■ На уровне языка поддерживается создание метатермов и модификация значений их атрибутов. Способ унификации метатермов должен быть описан пользователем. Атрибуты увеличивают объем информации, участвующий в унификации, позволяют сделать эту операцию логически более сильной.

Отложенная цель состоит из прологовской цели и идентификатора, предохраняющего ее от унификации. Над отложенными целями определены три основных действия: создание, активация для исполнения и исполнение всех активных целей. В момент создания отложенная цель автоматически помещается в системный список отложенных целей. Прагматическим назначением отложенных целей является управление будущим поведением программы. Отложенная цель записывается в виде 'GOAL1 (G).

Пусть 1) каждое н-значение "а взаимно-однозначно кодируется некоторым константным термом 2) каждая из п вычислительных функций отношения р/п вычисляется (п+1)-местным предикатом ИЪ.рь. Первые п аргументов такого предиката соответствуют аргументам вычислительной функции, а (п + 1)-й — ее значению.

Для описания н-вычислений в терминах метатермов и отложенных целей вводится понятие направленного ограничения. Направленным ограничением называется пара (р, к), где р — с(хi,..., хп) — обычное ограничение, к — номер одного из аргументов р. Будем говорить, что направленное ограничение (р, к) "считывает" переменные х,- (г ф к) и "записывает" переменную Хк (точнее, соответствующие н-значешш).

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

Вычислительная сеть задается набором значений типов .метатерм и отложенная цель. Ниже Rep(r) и Rep((p, к)) обозначают представление переменной х и направленного ограничения (р,к).

Пусть переменная х с н-значением *х считывается направленными ограничениями (р,к), (<?,/), (г,т), .... Метатерм 11ер(з;) имеет один атрибут за. Первая компонента атрибута хранит представление их н-значения переменной х. Вторая компонента атрибута хранит список [Лер((р, &)), 11ср((д,/)), 11ер((г, гл)), ...] представлений направленных ограничений, считывающих переменную х.

Если направленное ограничение (р, к) считывает переменные аг,- (г ф к) и записывает переменную х^, то

Ыер((р,£)) = 'СОЛГ-ЧМ-Ря-Шер^), ... .Нер^.Нер^))).

Вычислительная сеть, таким образом, распределяется по переменным, фрагменты сети отождествляются с отложенными целями. При срабатывании отложенная цель разрушается и исчезает соответствующая часть вычислительной сети. Чтобы поддерживать неизменным вид вычислительной сети в течение всего времени вычислений, каждый предикат ИЬ-Рк добавляет в системный список новую отложенную цель, представляющую только что исчезнувший участок сети. Таким образом, вычислительная сеть сохраняет свой исходный вид. В заключение главы 2 разобран пример, иллюстрирующий основные положения предложенного метода.

В главе 3 описываются две инструментальные разработки соискателя: интерпретатор Ьо§Юа1с и Интервальная библиотека для системы логического программирования ЕСЬ'Р8е.

Разделы 3.1—3.6 посвящены средствам представления и обработки конечных множеств в интерпретаторе Ьо§Юа1с.

Средства представления и обработки множеств встраиваются в языки императивной и декларативной ориентации. Среди всех императивных языков наиболее существенным образом тип данных "множество" поддерживается в языке БЕТЬ (Дж. Шварц и др., начало 80-х). Язык БЕТЬ позволяет работать с произвольными конечными множествами (в том числе составных объектов). Конечное множество является полноправным членом иерархии типов данных языка БЕТЬ.

Язык БЕТЬ включает так называемые формирователи множеств. Стандартной математической записью этой конструкции является {х\С}, "множество всех таких х, что С". По правилам языка ЯЕТЬ формирователь множества записывается в виде {ж £ или {е : х (Е где х — переменная, е — выражение, универсум й — ранее построенное множество. Формирователи множеств являются очень выразительной конструкцией.

Интерпретатор языка SETL, исполняя формирователь множества, по очереди перебирает элементы универсума и включает в множество те из них, которые обладают выделяющим свойством. Такой подход "generate and test" теряет привлекательность, если широкий универсум сочетается с жестким выделяющим условием.

Попытки использования множеств неоднократно делались и в логическом программировании. В одном из подходов (А. Довьер, Дж. Росси и др., интерпретатор {log}, начало 90-х) язык Пролог расширяется интерпретированным функциональным символом (with/2), служащим для задания множеств. Поскольку множество определяется только своими элементами, а не порядком их перечисления и кратностью их повторов, одно множество может быть задано разными способами. Это обстоятельство создает вокруг унификации множеств проблемы: 1) определение унифицируемости двух множеств является NP-полной задачей; 2) если два множества унифицируемы, то их наиболее общий унификатор не отражает информации, полученной в ходе унификации.

Создатели системы {log} решили последнюю проблему, отказавшись от детерминированности унификации. Например, унификация {Х,У} и {0,1} дает два частных решения: Х=0, Y=1 и x=l, Y=0. Однако с расширением множества число таких частных решений может стремительно расти, что порождает другую проблему — увеличение дерева поиска.

Другая разработка — это основанная на распространении ограничений библиотека Conjunto в системе логического программирования в ограничениях ECL!PSe. В библиотеке Conjunto каждое множество задается своей верхней и нижней границей относительно теоретико-множественного включения. Вычисления организуются так, что различие между этими границами может только уменьшиться. Переменные, обозначающие искомые множества, связываются отношениями =,

С и т.п. Для задач на разбиение и упаковку имеются отношения для работы с целочисленными и вещественнозначными отображениями.

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

В разделах 3.2—3.6 описывается система LogiCalc: входной язык интерпретатора LogiCalc (3.2), основные механизмы этой системы и их улучшения (3.3, 3.4), средства обработки конечных интенсиональных

и экстенсиональных множеств на основе недооиределенных вычислительных моделей (3.5, 3.6).

Множеством значений переменных и констант в системе LogiCalc является наименьшее множество, содержащее отрезок целых чисел [—МАХ, МАХ], атомы и замкнутое относительно операций построения конечных кортежей и множеств. В системе LogiCalc задача записывается в виде системы уравнений, неравенств, теоретико-множественных отношений, связывающих какие-либо выражения. Выражения состоят из констант, переменных и операций (функциональных символов).

Основой системы является метод н-вычислений, адаптированный к классу задач удовлетворения ограничениям с конечными множествами. Запись задачи на языке системы LogiCalc переводится в систему ограничений и затем для этой системы ограничений отыскивается н-решение.

От интерпретатора языка SETL систему LogiCalc отличает использование принципа " test and generate", при котором универсум множества играет второстепенную роль, а на первом плане находятся условия, определяющие принадлежность элементов множеству. При формировании множеств с широким универсумом система LogiCalc более эффективна, чем интерпретатор языка SETL.

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

Далее в главе 3 описывается Интервальная библиотека для решения нелинейных ограничений в системе ECL'PS6 (3.7—3.11).

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

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

Helios, Numérica, разработанных под руководством 11. ван Хентен-рика во второй половипе 90-х годов.

Система CLP(BNR) также использует интервальный метод поиска решения, состоящий в нахождении интервального решения, являющегося неподвижной точкой для системы преобразований многомерных интервалов. Вычислительные модели с интервальной недоопределен-ностью, используемые в системе Unicalc (A.JI. Семенов, около 1990), также могут считаться интервальным методом поиска решения.

Разделы 3.8-3.11 описывают Интервальную библиотеку: способы спецификации различных типов ограничений (3.9), предоставляемые библиотекой средства символьных преобразований (3.10), специальные возможности, рекомендации по использованию, отличия от классического метода н-вычислений (3.11).

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

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

В отличие от систем Newton, NUMERICA Интервальная библиотека используется в рамках промышленной системы программирования, что позволяет создавать на базе системы ECL'PS6 с Интервальной библиотекой полноценные приложения. По сравнению с системой CLP(BNR) библиотека предоставляет более выразительный язык спецификации задач и более широкий набор операций, используемых в ограничениях.

В библиотеке использована одна из первых версий вычислительного ядра системы Unicalc в доработанном виде. Целью создания библиотеки были взаимное расширение возможностей системы ECL'PSe и недоопределенных вычислительных моделей и демонстрация практической применимости предложенного в главе 2 метода использования недоопределенных вычислительных моделей в логическом программировании.

В главе 4 рассказывается о результатах тестирования Интервальной библиотеки и созданных на ее основе приложениях.

Интервальная библиотека тестировалась на наборе задач для системы Neoton, более поздней версией которой является система NUMERICA. Разработчики системы Mentón приводят также результаты сравнения своей системы с традиционным интервальным методом, использующим для сжатия интервалов так называемый оператор Хансена-Сегупты и поиск в глубину с отсечением.

Набор задач включает тесты фиксированной размерности и масштабируемые задачи. Интервальная библиотека с успехом конкурирует с названным выше традиционным интервальным методом. На некоторых тестах фиксированной размерности Интервальная библиотека уступает системе Newton по быстродействию в 1.5-2.5, что можно объяснить особенностями реализации Интервальной библиотеки и системы Neoton. На ряде масштабируемых задач библиотека либо показывает меньшие темпы роста затрат времени с ростом размерности задачи, либо абсолютно превосходит систему Nenton.

Раздел 4.2 описывает разработанное на основе Интервальной библиотеки приложение для построения наборов оптимальных сетей (коммуникационных, электрических и т.п.). Построение набора из одной сети эквивалентно классической NP-полной задаче о кратчайшем штей-неровском дереве. Для наборов из нескольких сетей задача осложняется условиями несовместности сетей разных типов. Созданное приложение позволяет за приемлемое время доказывать оптимальность получаемых решений для задач с 40-50 вершинами. Для задач со 100-400 вершинами приложение позволяет получать несколько улучшающих друг друга приближений.

Раздел 4.5 описывает приложение для расчета инвестиционных портфелей с наименьшим риском. Исходя из статистических данных о доходности отдельных составляющих портфеля, приложение по известным методикам рассчитывает среднюю доходность, риск, коэффи-

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

Основные результаты

1) Разработан метод интеграции недоопределенных вычислительных моделей и логического программирования. Разработанный метод повышает эффективность логических программ путем автоматического учета в логическом выводе неполной информации. Для случая интервальной недоопределенности теоретически исследованы свойства недоопре-деленных вычислительных моделей. Установлено необходимое и достаточное условие сходимости вычислений в таких моделях при решении линейных уравнений, установлена связь со сходимостью классических методов Зейделя, Якоби.

2) Разработаны средства представления и обработки множеств в недо-определенных вычислительных моделях. Разработанные средства позволяют использовать интенсиональные и экстенсиональные спецификации множеств для эффективного решения комбинаторных задач. Разработаны язык для описания таких задач и его интерпретатор LogiCalc. Предложенные средства представления и обработки множеств использованы в интерпретаторе LogiCalc.

3) Разработана Интервальная библиотека для системы логического программирования ECL'PSe. Библиотека предназначена для автоматического учета при логическом выводе неполной информации о вещественных решениях нелинейных ограничений. Библиотека включает средства для спецификации массовых ограничений, символьных преобразовании, управления процессом вычислений. На основе Интервальной библиотеки разработаны приложения для решения задач автоматического проектирования и моделирования финансовых операций.

Публикации по теме диссертации

1. Petrov Е. S. LogiCalc: integrating constraint programming and subdefinite models // Proc. 2nd Workshop on Non-Standard Logics and Logical Aspects of Computer Science. — Irkutsk: Irkutsk State Univ., 1996. — P.97-98.

2. Yakhno T. M., Petrov E. S. Application of subdefinite models for constraint satisfaction problems // Proc. 2nd Int. Conf. "Perspective of System Informatics". — Berlin: Springer, 1996. — P.27-34.— (Lect. Notes Comput. Sei.; Vol. 1181).

3. Yakhno Т. M., Petrov В. S. LogiCalc: integrating constraint programming and subdefinite models // Proc. 2nd Int. Conf. "Practical Application of Constraint Technology". — London, 1996. — P.357-372.

4. Яхно Т. M., Петров Е. С. LogiCalc: интеграция методов программирования в ограничениях и недоопределенных моделей // Программирование.— 1996. — N.3. — С.70-79.

5. Петров Е. С. Сходимость метода недоопределенных вычислений при решении линейных уравнений // Проблемы представления и обработки неполностью определенных знаний. — Москва-Новосибирск: Рос. НИИ Искусственного интеллекта, 1996. — С.41—51.

6. Petrov Е. S. LogiCalc: solving set constraints by subdefinite models // Proc. 8th European Summer School in Logic, Language and Information (student session). —- Prague: Czech Tech. Univ., 1996.

7. Yakhno Т. M., Zilberfaine V. Z., Petrov E. S. Application of ECL'PSC: Interval Domain library // Proc. 3rd Int. Conf. "Practical Application of Constraint Technology". — London, 1997. — P.339-358.

8. Petrov E. S. Applications of Interval Domain library: expressing connectivity via non-linear constraints // Proc. 6th Scandinavian Conf. on Artificial Intelligence (Helsinki, Finland). — Amsterdam: IOSPress, 1997. — P.143-150.

9. Yakhno Т. M., Zilberfaine V. Z., Petrov E. S. Interval Domain library for ECL'PSe and its applications // ICL Systems J. — 1997. — November. — P.35-50.

10. Петров E. С. Интервальная библиотека: опыт интеграции логического программирования и программирования в ограничениях // Программирование.

— 1998. — N.3. — С.40-49.

11. Yakhno Т. М., Petrov Е. S. Constraint programming for knowledge representation // Proc. 3rd Joint Conf. on Knowledge-Based Software Engineering (Smolenice, Slovakia). — Amsterdam: IOSPress, 1998. — P.116-123.

12. Петров E.C. Интеграция недоопределенных моделей в систему ECL'PSe // Тр. 6—и национальной конф. по искусственному интеллекту с междунар. участием.

— Пущшго,1998. — Т.1. — С.355—360.

Як

У*"4 /

/Ч "••''

РОССИЙСКАЯ АКАДЕМИЯ НАУК Институт систем информатики им. А. П. Ершова

На правах рукописи

Петров Евгений Сергеевич

МЕТОДЫ ИНТЕГРАЦИИ ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ И ПРОГРАММИРОВАНИЯ В ОГРАНИЧЕНИЯХ

05.13.11 — математическое и программное обеспечение вычислительных машин, комплексов и сетей

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель доктор физико-математических наук, старший научный сотрудник Т. М. Яхно

Новосибирск—1999

Содержание

Введение и структура работы 5

1 Сходимость в нёдоопределенных вычислительных моделях 7

1.1 Определения ...............,......................7

1.2 Локальная совместность .....................9

1.3 Недоопределенные модели........................................12

1.4 Недоопределенные вычисления....................14

1.5 Иллюстративный пример........................................17

1.6 Сходимость вычислений в моделях с интервальной недо-определенностью .............................................20

1.6.1 Дополнительные обозначения ..........................21

1.6.2 Линейные уравнения с точки зрения НЗ .......22

1.6.3 Технические леммы......................................23

1.6.4 Исследование сходимости................................24

1.6.5 Связь с классическими методами......................27

2 Интеграция логического программирования и недоопре-деленных вычислительных моделей 32

2.1 Математическая логика и программирование.........32

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

2.1.2 ^-программирование ....................................37

2.2 Система ЕСУРБ6 ................................................38

2.2.1 Мета-термы ..............................................38

2.2.2 Отложенные цели........................................40

2.3 Модельный пример ..............................................41

2.4 Интеграция недоопределенных вычислений в систему ЕСГ/РБ6 43

2.4.1 Вычислительная сеть....................................44

2.4.2 Организация управления................................45

3 Инструментальные системы 49

Ьо^Сак 49

3.1 Программирование с множествами ............................50

3.1.1 Язык ЯЕТЬ................................................50

3.1.2 Логическое программирование..........................51

3.2 Система Ьо^Са1с ........................53

3.2.1 Множество значений переменных и констант .... 53

3.2.2 Язык системы Ьо^Са1с..................................54

3.2.3 Примеры записи задач .................55

3.3 Механизм работы системы Ьо^Са1с..............58

3.3.1 Множество недоопределенных значений........59

3.3.2 Порождение системы ограничений......................59

3.3.3 Вычислительные функции..............................61

3.4 Оптимизации НЗ в системе Ьо^Са1с..............62

3.5 Интенсиональные описания множеств..........................65

3.5.1 Вычисление параметров ...............................65

3.5.2 Вычисление множества..................................67

3.6 Экстенсиональные описания множеств........................69

Интервальная библиотека 71

3.7 Обзор методов решения нелинейных ограничений............71

3.8 Общая характеристика Интервальной библиотеки .....73

3.9 Спецификация ограничений для Интервальной библиотеки 73

3.9.1 Вещественные ограничения ............................73

3.9.2 Целочисленные и смешанные ограничения......76

3.10 Символьные преобразования.........................78

3.10.1 Символьное дифференцирование........................78

3.10.2 Массивы и массовые ограничения......................79

3.10.3 Определение функций пользователем.........81

3.11 Специальные возможности......................................82

3.11.1 Основные нематематические предикаты.......82

3.11.2 Технические особенности................86

3.11.3 Оптимизации Ж в Интервальной библиотеке .... 89

4 Приложения 91

4.1 Сравнение с системой Newton..................91

4.1.1 Тесты на интервальную арифметику.........92

4.1.2 Локтевой манипулятор................. 93

4.1.3 Расчет горения......................95

4.1.4 Расчет химического равновесия............95

4.1.5 Функции Бройдена....................96

4.1.6 Экономическое моделирование............. 96

4.1.7 Дискретизация интегрального уравнения.......96

4.2 Построение кратчайших сетей................. 97

4.2.1 Математическая модель......................97

4.2.2 Интервальные ограничения............... 98

4.2.3 Анализ, эксперименты и комментарии........100

4.2.4 Интервальная vs. Дискретная библиотека......101

4.3 Евклидовы штейнеровские деревья заданной топологии . . 106

4.4 Финансовое планирование....................108

4.5 Инвестиционные портфели ...................111

Заключение 114

Библиография 116

Введение и структура работы

Настоящая диссертация посвящена исследованию и развитию аппарата недоопределенных вычислительных моделей и его интеграции с логическим программированием. Недоопределенные вычислительные модели были предложены А. С. Нариньяни в начале 80-х годов в качестве средства представления и обработки знаний, и в настоящее время развиваются коллективом Российского института искусственного интеллекта и лабораторией Искусственного интеллекта Института систем информатики им. А. П. Ершова СО РАН. С начала 90-х годов недоопределенные вычислительные модели с успехом используются в программировании в ограничениях (CP от «Constraint Programming»). Отличительной чертой недоопределенных вычислительных моделей как метода CP является применимость к решению задач со смесью данных различных типов.

За последние двадцать лет в рамках CP разработан ряд специальных методов и на их основе создано большое число систем для решения прикладных задач в области автоматического проектирования, ресурсного планирования, задач моделирования в различных естественно-научных дисциплинах [40, 21, 33, 14, 54, 16, 61, 62, 63].

Для решения задач численного моделирования, возникающих в химии, роботике, механике, финансовой математике и, как правило, содержащих неточные или неполные данные, в CP и недоопределенных моделях широко используется интервальное представление неизвестных значений в сочетании с потоковым принципом управления [21, 33, 14, 54, 16]. Несмотря на популярность такого метода, число работ, в которых исследуется его сходимость и другие теоретические свойства невелико [2, 59].

В главе 1 автор исследует сходимость в недоопределенных вычислительных моделях при решении линейных уравнений.

Глава 2 посвящена подходам к интеграции CP и логического про-

граммирования. Необходимость в такой интеграции возникает при создании на основе методов СР полноценных приложений. Известные системы логического программирования в ограничениях изначально ориентированы на определенные (иногда весьма экзотические) классы задач [19, 15, 29, 25]. Интеграция логического программирования и недо-определенных вычислительных моделей позволяет разрабатывать системы логического программирования в ограничениях, настраиваемые на предметную область решаемой задачи.

В главе 3 описываются две инструментальные разработки автора: интерпретатор Ьо^Са1с и Интервальная библиотека для системы логического программирования ЕСЬгР8е.

Богатый класс задач из области программирования в ограничениях образуют так называемые задачи с конечными областями значений переменных — хорошо формализованные фрагменты задач распределения ресурсов и планирования. Важными объектами в таких задачах являются конечные множества и их отображения (графы). Задачи с конечными областями значений переменных принято сводить к задаче целочисленного программирования, в результате чего, как правило, увеличивается размерность задачи и на второй план отходит ее комбинаторная сущность. Перспективным является создание средств для представления и обработки непосредственно множеств [24, 29].

Третья глава диссертации начинается с описания средств представления и обработки конечных множеств в недоопределенных вычислительных моделях.

Далее в главе 3 описывается Интервальная библиотека для решения нелинейных ограничений в системе ЕС1/Р8е. В библиотеке использована одна из первых версий вычислительного ядра системы 11шса1с [14] в доработанном виде. Целью создания библиотеки было обоюдное расширение возможностей системы ЕСГ/РБ6 и недоопределенных вычислительных моделей и, кроме того, демонстрация практической применимости предложенного в главе 2 метода использования недоопределенных вычислительных моделей в логическом программировании.

Четвертая глава описывает результаты тестирования Интервальной библиотеки и разработанные на ее основе приложения для решения задач автоматического проектирования и финансового моделирования.

В заключение формулируются основные результаты диссертации, выносимые на защиту.

Глава 1

Сходимость в недоопределенных вычислительных моделях

Настоящая глава посвящена исследованию сходимости вычислений в моделях с интервальной недоопределенностью при решении линейных уравнений. Автором получено необходимое и достаточное условие сходимости (раздел 1.6.4), установлена взаимосвязь с классическими методами Якоби и Зейделя (раздел 1.6.5). Основная часть материала опубликована работе в [4]. Кроме того, вводятся термины, используемые на протяжении всей работы, дается краткий обзор методов решения задач удовлетворения ограничениям, устанавливается связь между задачами удовлетворения ограничениям и недоопределенными вычислительными моделями.

1.1 Определения

Набор из трех конечных множеств £ = (С, Р, Р) называется сигнатурой. Элементы множества С называются константами, Р — предикатами (отношениями), Г — функциями. Элементы счетного множества V называются переменными. Предполагается, что эти четыре множества попарно не пересекаются, и что двуместное отношение равенства (= /2) содержится в Р.

Модель сигнатуры Е задается двумя компонентами: множеством «значений переменных и констант» А и отображением I, которое каждую константу переводит в элемент множества А, каждую п-местную функцию — в отображение Ап —> А, и каждый n-местный предикат — в подмножество А™. Множество А называется носителем модели, I — интерпретацией сигнатуры Е, сама модель обозначается (А, I).

Сигнатура Е перечисляет средства, доступные для описания предметной области, а модель (А, I) фиксирует способ понимания этих средств, принятый в этой предметной области. Выберем некоторую сигнатуру Е и ее модель. Будем ссылаться на эту модель как на «стандартную модель» сигнатуры Е.

Если символ и его стандартная интерпретация встречаются в одной формуле, то символ набирается жирным курсивом, его стандартная интерпретация — простым курсивом. Например, если с £ С, (р/п) £ Р, (f/n) е F, то 1(c) = с е А, I(р/п) - р С An, I(f/n) = / : Ап А.

Отображение V —> А называется означиванием переменных, а образ переменной под действием означивания — значением этой переменной.

Любая (стандартная) модель и означивание переменных V естественным способом определяют означивание термов и истинность (атомарных) формул от переменных V.

Атомарная формула, не содержащая функций, называется ограничением. Конечное множество ограничений называется системой ограничений. Параллельно с термином «система ограничений» используется синоним «задача удовлетворения ограничениям» и сокращение CSP от «Constraint Satisfaction Problem».

Набор п значений a¿ (г £ [1,и]) удовлетворяет ограничению р, наложенному на переменные x¿ (i £ [1, ?"*<]), если формула р истинна в стандартной модели при означивании переменных x¿ н-> a¿ (г £ [1,п]).

Если в (стандартной) модели означивание переменных 7 делает каждое ограничение из системы CSP истинным, то 7 называется (стандартным) решением системы ограничений CSP.

Система ограничений называется несовместной, если она не имеет стандартных решений. Система ограничений называется совместной, если она имеет хотя бы одно стандартное решение.

1.2 Локальная совместность

В рамках программирования в ограничениях для решения задач удовлетворения ограничениям разработано и исследовано большое число методов обеспечения так называемой локальной совместности: алгоритмы «совместность по дугам» [40] и «синтез ограничений» [27] для дискретных областей значений, «вычисления с метками» [21], «box-consistency» [61] для интервальных областей значений и др.

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

Шаг работы алгоритма состоит в доопределении множества решений (например, стягивании одного из интервалов без потери решений). Такие алгоритмы объединяет использование управления по данным и принцип монотонного изменения значений переменных [8]. Названные алгоритмы встраивают в программное обеспечение общего назначения (электронные таблицы и т.п.), в прикладные системы (календарного планирования, CAD/CAM и т.п.). Такие гибридные системы не требуют увеличения затрат на свою разработку и вместе с тем предоставляют более широкие возможности своим пользователям.

По-видимому, идеи, аналогичные идее локальной совместности, впервые были выдвинуты Ю. И. Журавлевым [10] в 1963 г. Им рассматривалась в обобщенном виде задача сокращения дизъюнктивных нормальных форм (д. н. ф.) и построения минимальной д. н. ф.

Ю. И. Журавлев рассматривал исходную д. н. ф. т как множество элементарных конъюнкций и для подходящего набора 2-местных предикатов pi оценивал значениями 0 (ложно), 1 (истинно), Д (неизвестно) истинность формул Pi(a, т) для каждой конъюнкции а 6 т. Мы будем называть такой набор значений из множества {0,1, А} оценкой конъюнкции а.

Для вычисления этих оценок исходная д. н. ф. т определенным образом разбивалась на окрестности s(a,m) (а (Е т). Оценка каждой конъюнкции а вычислялась локально, т.е. на основании оценок (других) конъюнкций, бравшихся только из ее окрестности s(a,m). Вычисления

продолжались до стабилизации всех оценок. Ю. И. Журавлевым было доказано, что результат таких вычислений не зависит от порядка рассмотрения отдельных конъюнкций.

Для решения задач удовлетворения 1- и 2-местным ограничениям с конечными областями значений переменных А. Макверс в 1977 г. предложил алгоритм обеспечения совместности по дугам [40]. А. Макверс рассматривал задачи, в которых каждая пара переменных (одиночная переменная) связана не более, чем одним 2-местным (соответственно 1-местным) ограничением. Ограничения, наложенные на переменные х, у, обозначаются рх, рху

Система CSP ограничений такого типа определяет ориентированный граф с вершинами-переменными и дугами-ограничениями. Ограничению рху соответствуют дуги (ж,у), (у,х). Каждой переменной х из V сопоставляется так называемый домен Dx, список возможных значений х. А. Макверс ввел термин «сеть ограничений» для обозначения графового представления системы ограничений.

Значение а переменной х называется продолжаемым до решения CSP, если найдется такое решение CSP, в котором значение х есть а.

Вершина х называется совместной, если (1) Dx содержит все значения х, продолжаемые до решения CSP, (2) каждое значение из домена Dx удовлетворяет ограничению рх.

Дуга (х, у) ((у, х)) называется совместной, если для каждого значения b £ Dy (g £ Dx) найдется такое значение а £ Dx (b £ Dy), что пара (a, b) удовлетворяет ограничению рху.

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

Для обеспечения совместности по дугам А. Макверс предложил алгоритм Arc Consistency (АС), итеративно (до прекращения изменений) удаляющий из доменов значения, которые нарушают совместность вершин и дуг. Трудоемкость АС в худшем случае есть 0(с3п2), где с — размер самого широкого домена, п — количество переменных.

Таким образом, алгоритм АС является эффективным приближенным алгоритмом удовлетворения ограничениям. Его принципиальным недостатком является неэкономное представление доменов и интерпретации отношений: полное перечисление отдельных значений и их пар делает алгоритм весьма трудоемким при широких начальных доменах.

Для решения задач удовлетворения ограничениям с вещественными значениями переменных Е. Дейвис в 1987 г. предложил вычисления с метками («Label Inference») [21]. Им рассматривались системы арифметических ограничений вида х *у = z (*£{-,+})•

Система ограничений в работе Е. Дейвиса также представляется сетью ограничений. Вершинами сети являются переменные и ограничения. Данные переменная и ограничение соединяются ребром тогда и только тогда, когда переменная входит в ограничение. Ограничению х * у = z соответствует 3-лучевая звезда, центром которой является оно само, а лучи расходятся к переменным х, у, г. Таким образом, сеть ограничений является двудольным неориентированным графом.

Каждой переменной х сопоставляется метка-интервал 1Х, ограничивающий диапазон возможных значений данной переменной. Использование интервалов вместо полного перечисления устранило проблему с представлением бесконечных доменов, которая пр�