Методы внешнего оценивания множества решений задачи удовлетворения ограничений тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Лоенко, Михаил Юрьевич

• Лоенко, Михаил Юрьевич
• кандидат физико-математических наук
• 2003

Оглавление диссертации кандидат физико-математических наук Лоенко, Михаил Юрьевич

Введение

1. Вычисление элементарных функций с гарантированной точностью

1.1. Соглашения.

1.2. Оценка синуса на интервале [0,

1.3. Оценка синуса на интервале [0, оо]

1.4. Оценка косинуса.

1.5. Оценка тангенса.

1.6. Обратные тригонометрические функции.

1.6.1. Оценка арксинуса.

1.6.2. Оценка арккосинуса.

1.6.3. Оценка арктангенса.

1.7. Оценка экспоненты

1.8. Оценка логарифма.

1.9. Результаты.

2. Алгоритм коррекции решения

2.1. Базовые определения

2.2. Алгоритм М2В.

2.3. Применение алгоритма М2В.

2.4. Алгоритм МЗВ.

2.5. Алгоритм коррекции решения.

2.6. Настроечные параметры алгоритма.

2.7. Результаты экспериментов.

2.8. Управление алгоритмами сужения.

3. Ньтоновские корректоры

3.1. Граф задачи.

3.2. Функции-характеристики.

3.3. Граф истории.

3.3.1. Вершины графа истории. w 3.3.2. Создание заготовки графа истории.

3.3.3. Эволюция графа истории.

3.3.4. Свойства графа истории.

3.4. Граф-индикатор несовместности.

3.4.1. Вершины-числа.

3.4.2. Вершины-функции.

3.4.3. Корректность графа-индикатора.

3.4.4. Предельное значение графа-индикатора.

3.4.5. Теорема о предельном значении графа-индикатора

3.5. Алгоритм ньютоновской коррекции.

3.5.1. Теорема о корректности алгоритма.

3.6. Сравнение алгоритмов NSC и М2В на примере конкретной задачи.

3.6.1. Решение задачи М алгоритмом М2В.

3.6.2. Решение задачи М алгоритмом NSC.

3.7. Результаты экспериментов.

Введение диссертации (часть автореферата) на тему «Методы внешнего оценивания множества решений задачи удовлетворения ограничений»

Большинство задач, возникающих при моделировании, составлении расписаний, оптимизации распределения ресурсов, могут рассматриваться как задачи удовлетворения ограничений (CSP - Constraint Satisfaction Problem).

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

Задача удовлетворения ограничений впервые была формализована Хаффманом (Huffman) в 1971 г. [43].

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

Рассмотрим другой пример. Пусть множество переменных задачи удовлетворения ограничений состоит из единственной переменной х, множество ее возможных значений - множество вещественных чисел, а множество ограничений состоит из ограничения х2 — 2х + 1 = 0. Таким образом, обычное математическое уравнение может быть представлено как задача удовлетворения ограничений. Различные системы уравнений, в том числе и с не полностью определенными коэффициентами, также могут быть рассмотрены как задачи удовлетворения ограничений.

Задачи, в которых множества возможных значений всех переменных являются подмножествами множества вещественных чисел, называют численными (numeric CSP, NCSP). Задачи, в которых множества возможных значений переменных конечны, называют конечными (finite CSP). Задачи, в которых множества возможных значений переменных являются вещественными интервалами, называют непрерывными. Задачи, все ограничения которых унарные либо бинарные, называют бинарными.

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

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

2. Поиск. Различные методы поиска решения.

3. Синтез. Методы синтеза решения.

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

Преобразование задачи - это уменьшение областей возможных значений переменных и/или изменение множества ограничений.

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

Многие методы решения CSP применимы только к задачам специального вида, например к задачам, все ограничения которых унарные либо бинарные. Поэтому разработано множество алгоритмов приведения произвольных CSP к тому или иному специальному виду. Выполнение различных линейных подстановок, раскрытие скобок, применение формул тригонометрических преобразований, построение базисов Гребнера [18, 41, 57, 64] для систем полиномиальных уравнений также относится к этому классу методов.

Уменьшение областей значений состоит в удалении так называемых избыточных значений, т. е. таких значений, удаление которых не изменяет множества решений CSP. Методы, удаляющие избыточные значения, называются методами сужения. Среди последних выделяют методы достижения совместности, заключающиеся в удалении тех значений, которые нарушают некоторое свойство, называемое свойством совместности.

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

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

Стандартный алгоритм достижения совместности в узлах называется NC (node consistency) [75] и состоит в последовательном переборе всех возможных значений каждой переменной и проверке всех унарных ограничений над этой переменной.

Бинарная CSP называется совместной по дугам, если для любой пары переменных (х,у), для каждого значения а переменной ж, удовлетворяющего всем унарным ограничениям над х, существует значение Ъ переменной у такое, что все бинарные ограничения над х и у выполняются.

Для достижения совместности по дугам было создано несколько алгоритмов [28], наиболее распространенный из них - АС-3 [53]. Алгоритм применяется к задаче, совместной в узлах. Сначала он строит очередь Q ограничений, в которую изначально ставит все ограничения решаемой задачи; далее алгоритм удаляет по очереди все ограничения из Q, выполняя следующие действия:

• если с(х, у) - удаляемое ограничение, то удаляет значения а из области значений переменной х, для которых не существует такого значения Ъ в области значений у, что с(а, Ь) выполняется;

• удаляет значения d из области значений у, для которых не существует такого значения е в области значений ж, что с(е, d) выполняется;

• если область возможных значений переменной х изменилась, ставит в очередь Q все ограничения, в которых фигурирует переменная х, кроме тех, что уже стоят в очереди Q, и кроме ограничения с(х,у);

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

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

Бинарная CSP называется совместной по путям, если для любой такой последовательности переменных (х\,., хп), что значения ai,an переменных х\, хп удовлетворяют всем ограничениям над xi, хп, существуют значения аг,.,ап-1 переменных X2,.,xn-i такие, что для всех г = 1,., п — 1 значения аг, Oj+i переменных жг, 1 удовлетворяют всем ограничениям над переменными X{,Xi+1.

Для достижения совместности по путям также создано несколько алгоритмов [75], однако все они практически не используются, поскольку уступают в эффективности различным суперпозициям алгоритмов поиска и достижения совместности по дугам.

Для непрерывных задач также существуют понятия локальной совместности: совместности по границам (2В-, ЗВ-, .), Ьох-совместность и другие [25, 49]. Методы достижения перечисленных и некоторых других видов совместностей называют также методами распространения ограничений [21, 24, 27, 46, 67]. Такие методы могут оказаться единственным подходом к решению реальных задач, когда применение классических вычислительных методов или методов компьютерной алгебры затруднено наличием неточных данных или частично определенных параметров.

Второй класс методов решения CSP содержит различные методы поиска решения. Большинство существующих методов решения конечных CSP принадлежит этому классу.

Основным алгоритмом поиска для конечных CSP является бэктрэкинг (backtracking) [33, 65], известный также как хронологический бэктрэкинг (chronological backtracking). Этот алгоритм состоит в последовательном фиксировании переменных, т. е. присваивании им некоторых значений. Изначально все переменные незафиксированны. На каждом шаге выбирается некоторая незафиксированная переменная, после чего ищется "совместное" значение из области ее возможных значений, т. е. такое значение переменной, которое вместе со значениями фиксированных переменных не нарушает ни одного ограничения над этими переменными. Если область значений выбранной переменной не содержит совместных значений, то значение, присвоенное при фиксировании предыдущей переменной, признается несовместным, и происходит возврат на предыдущий шаг. В противном случае найденное совместное значение фиксируется, после чего происходит переход к следующему шагу, на котором выбирается и фиксируется следующая переменная. Если все переменные оказались фиксированными - решение найдено. Если все значения первой выбранной переменной оказались несовместными - задача не имеет решений.

В различных реализациях бэктрэкинга могут быть различными стратегии выбора:

• переменной для фиксирования;

• значения для присваивания;

• ограничения для проверки.

Удачно сделанный выбор может уменьшить пространство поиска.

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

Алгоритм backchecking [40] разработан для приложений, в которых проверка совместности значений занимает много времени. Если при фиксировании некоторой переменной у, значение Ъ оказывается несовместным с некоторым значением а фиксированной переменной х, backchecking запоминает это и не проверяет больше значение Ь, пока значением переменной х остается а.

Алгоритм backmarking [40] является улучшением алгоритма backchecking. Как и backchecking, он уменьшает количество проверок совместности, запоминая, какие значения несовместны с ранее фиксированными переменными. Более того, он запоминает, какие значения совместны с ранее фиксированными переменными, и тоже их не проверяет.

Предположим что на текущем шаге ищется совместное значение для переменной Xj. Предположим также, что некоторое время назад все возможные значения переменной Xj были проверены и найдены несовместными. Предположим, что с тех пор backmarking произвел откат до переменной ж*, где г < j, присвоил ей новое значение, после чего нашел совместные значения для переменных Жг+ь., Xj-i. Тогда при поиске совместного значения для переменной Xj backmarking не будет рассматривать те значения, которые "конфликтуют" с переменными xi,., Жг-ъ ПР° них Уже известно, что они несовместны. Кроме того, backmarking не будет проверять совместность между xi,., x^i и теми из оставшихся значений, про которые заранее известно, что они совместны.

Следующий алгоритм - backjumping [69] отличается от бэктрэкинга тем, что при необходимости возврата к предыдущему шагу он проводит анализ и возвращается сразу к той переменной, фиксирование которой привело к отсутствию совместных значений на текущем шаге.

Алгоритм forward checking [40] при фиксировании каждой переменной удаляет из областей возможных значений нефиксированных переменных значения, несовместные со значениями уже фиксированных переменных. При этом, если область значений некоторой переменной становится пустой, фиксируемое значение признается несовместным.

Существуют также алгоритмы, которые после фиксирования каждой переменной вызывают некоторый алгоритм сужения. Такие алгоритмы наряду с forward checking называются lookahead-алгоритмами [75].

Другой подкласс алгоритмов поиска - стохастические алгоритмы [50, 51, 58, 72, 74]. Они обычно применяются в тех случаях, когда необходимо быстро найти одно произвольное решение задачи. Алгоритмы стохастического поиска - это такие алгоритмы поиска, которые включают эвристики и элементы случайности. Большинство стохастических алгоритмов не гарантируют свое завершение за конечное время, и это их самый серьезный недостаток. Их преимущество состоит в том, что они могут оказаться единственно способными найти решение некоторых задач за разумное время. Так, например, алгоритм QS4 [19] решает задачу расстановки N ферзей меньше чем за минуту, если N < 1000000, тогда как бэктрэкинг уже при N, равном 100, не находит ни одного решения за разумное время.

Существуют также эвристические алгоритмы поиска, которые гарантируют свое завершение за конечное время. Примером такого алгоритма является одна из разновидностей бэктрекинга - алгоритм iterative broadening [31]. Его идея состоит в добавлении элементов случайности при распределении вычислительных усилий по дереву поиска. Количество визитов каждого узла дерева ограничивается некоторым пределом, и при достижении этого предела все не рассмотренные ветви этого узла игнорируются. Если при заданном пределе количества посещений алгоритм не находит решение, предел увеличивается.

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

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

Третий класс алгоритмов решения CSP - алгоритмы синтеза решения [75] - применяют тогда, когда необходимо найти все решения данной задачи. Пусть {а^,., жп} - множество переменных некоторой CSP, С - множество ее ограничений. Пусть множество Cj содержит все ограничения задачи, связывающие только переменные из подмножеств множества {xi,., Xi}. Синтез решения - это построение сначала множества значений переменной xi, которые удовлетворяют ограничениям из множества С\, затем множества пар значений переменных х^ и Жг, которые не нарушают ограничения из множества Сг, и т. д. В итоге получим множество кортежей длины п значений переменных xi,.,xn, которые удовлетворяют ограничениям из множества Сп, т. е. множество решений CSP. Первый алгоритм синтеза решения был представлен Фредером (Freuder) в 1978 г. [29].

Как отмечено выше, представление в виде CSP изначально использовалось для задач с конечными областями значений переменных, поэтому большая часть существующих методов решения CSP предназначена для решения конечных CSP. Параллельно с разработкой методов решения конечных CSP разрабатывались методы решения и непрерывных задач. Были обобщены понятия совместностей, для чего использовалось интервальное представление данных [1, 4, 5, 17, 39, 60].

В 1980-х гг. А. Нариньяни предложил метод недоопределенных вычислений (МНВ) [13, 14], который является методом сужения, т. е. относится к первому классу методов решения CSP. МНВ позволяет работать как с переменными, области значений которых конечны, так и с бесконечными и непрерывными областями значений. В этом методе использовано интервальное представление вещественных чисел и областей возможных значений вещественных переменных. Если множества значений всех переменных задачи конечны, алгоритм является алгоритмом достижения совместности по дугам и полностью соответствует алгоритму АС-3. На задачах, в которых области значений всех переменных вещественные интервалы, МНВ является алгоритмом достижения 2В-совместности и соответствует алгоритму М2В [49]. Для решения смешанных задач МНВ использует механизмы обоих методов.

При решении непрерывных задач применяют и специальные методы, неприменимые для конечных CSP [37, 38, 39, 42]. Обычно такие методы неприменимы и для смешанных CSP, более того, они обычно могут применяться только к квадратным системам уравнений, т. е. системам, количество уравнений которых совпадает с количеством переменных. Один из наиболее известных таких методов - интервальный метод Ньютона [39]. Для решения уравнения /(ж) = 0, где х <Е [а, Ь], а функция / дифференцируема в замкнутом промежутке [о, 6], строится последовательность вложенных интервалов [а, 6] = /о С 1\ С . С 1п, где т -гпЛп

1i+1 ij I I \Xi ~YJJ.y'

X{ ^ Ii.

По теореме Лагранжа о среднем значении [3] все корни уравнения f(x) = 0, содержащиеся в /0, содержатся в 1п. Таким образом, интервальный метод Ньютона является методом сужения. Существуют также специальные методы для решения систем полиномиальных уравнений [23, 26, 30].

В 1988 г. в РосНИИ искусственного интеллекта создан решатель систем нелинейных уравнений с не полностью определенными данными UniCalc [2, 20]. Базовым алгоритмом решателя является метод недоопределенных вычислений. Решатель работает как с вещественными, так и с целочисленными переменными и допускает представление ограничений как в виде конечных суперпозиций элементарных функций и операций, так и в виде логических выражений. В РосНИИ ИИ были построены также пробные версии решателя с табличным представлением ограничений, с мультиинтервальным представлением областей значений переменных [16, 68] и др. [6, 45]. На достаточно большом классе задач решатель UniCalc показал существенное преимущество перед обычными методами вычислительной математики. Позже библиотека решателя UniCalc была расширена некоторыми алгоритмами поиска, разработанными для задач с конечными и непрерывными областями.

В интервальных методах для вычисления границ интервалов применяются интервальные математические библиотеки, в которых используются различные подходы к вычислению интервальных функций. Пусть значение некоторой переменной х содержится в некотором интервале [а, Ь]. Предположим, что необходимо оценить значение ех. Очевидно, что оно содержится в интервале [еа,е6], но поскольку числа еа и еь могут оказаться не машинно-представимыми, для оценки значения ех часто используют следующие интервалы:

1) интервал, границы которого - приближенные значения чисел еа и еь. Для вычисления приближенных значений можно использовать, например, функции стандартных математических библиотек, поставляемых с компиляторами с языка С [32];

2) интервал, полученный так же, как и первый, расширенный на некоторое заранее посчитанное е.

3) гарантированный интервал, т. е. интервал, нижняя граница которого - максимальное машинно-представимое число, не превосходящее еа, а верхняя граница - минимальное машинно-представимое число, не меньшее еь;

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

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

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

Анализ доступных интервальных математических библиотек показал, что они производят вычисления либо первым [32], либо вторым способом [55], причем алгоритмы из [32] используются практически во всех библиотеках, поставляемых с компиляторами. При исследовании алгоритмов из [55] было обнаружено, что они также не гарантируют наличия точного значения в получаемом интервале. В связи с этим возникла необходимость построения собственной математической библиотеки для гарантированного вычисления элементарных математических функций.

В 1990-х гг. стали появляться программные продукты, например такие, как Numerica [77], которые на некоторых задачах превосходили UniCalc по быстродействию. В рамках работ по улучшению быстродействия решателя UniCalc и расширения его библиотеки методами решения различных типов задач автор начал решать задачу разработки дополнительных методов сужения для непрерывных и смешанных CSP.

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

Диссертационная работа состоит из введения, трех глав и заключения. Общий объем работы - 134 страниц. Работа включает 3 таблицы и 6 рисунков.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Лоенко, Михаил Юрьевич

Основные результаты работы - создание алгоритма коррекции решения (SC-алгорит-ма) и ньютоновских корректоров для использования в SC-алгоритме.

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

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

Представленные экспериментальные результаты показывают, что на большинстве задач скорость работы SC-алгоритма существенно выше скорости алгоритма МЗВ. Это связано с тем, что время работы алгоритма МЗВ значительно зависит от порядка выбора переменных. В SC-алгоритме эта зависимость сведена к минимуму.

Алгоритм NSC эффективен для задач с так называемыми "ползущими", т.е. кратными корнями. На обычных задачах из-за значительных накладных расходов эффективность алгоритма заметна лишь при использовании с большими начальными областями. Заметим также, что несмотря на то что алгоритм NSC в общем случае не гарантирует достижения ЗВ-совместности, с его помощью можно получить более точную оценку решения, чем с помощью алгоритмов SC и ЗВ, благодаря использованию производных при вычислении предельного значения графа-индикатора.

В настоящее время все большее распространение получает идея создания так называемых кооперативных решателей [54, 71], в которых на разных этапах решения задачи применяются различные алгоритмы. Применение представленных алгоритмов в качестве инструментов кооперативного решателя может существенно ускорить решение задачи в целом. Среди недостатков SC-алгоритма стоит отметить значительный расход памяти при решении задач с большим количеством переменных, особенно при использовании ньютоновских корректоров.

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

Представленный набор функций опирается на следующие условия:

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

2. Если значение операции удовлетворяет формату типа результата, то результат вычисления операции в точности равен ее значению.

3. Существование формата представления вещественного числа, совпадающего с форматом с двойной точностью стандарта ieee754.

4. Возможность установить направление округления результата операции "извлечение квадратного корня" в значение "вниз"

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

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

Представленные в работе алгоритмы применяются в решателе UniCalc, разработанном в Российском научно-исследовательском институте искусственного интеллекта. Алгоритм SC используется также в системах NemoNext, разработанной в РосНИИ ИИ, и Catia, созданной компанией Dassault Systemes.

Заключение

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

Список литературы диссертационного исследования кандидат физико-математических наук Лоенко, Михаил Юрьевич, 2003 год

1. Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления. - М.:Мир, 1987. - 260 с.

2. Выгодский М. Я. Справочник по высшей математике. М: Наука, 1975. - С. 330-331.

3. Добронец Б.С., Шайдуров В.В. Двусторонние численные методы. Новосибирск: Наука. Сиб. отд-ние, 1990. - 208с.

4. Калмыков С.А. Шокин Ю.И., Юлдашев З.Х. Методы интервального анализа. -Новосибирск: Наука. Сиб. отд-ние, 1986. 221с.

5. Кашеварова Т.П. Использование системы UniCalc для решения задач математического моделирования. Новосибирск, 1999. - 34с. - (Препр. / РАН. ИСИ; N. 64).

6. Корн Г., Корн Т. Справочник по математике. М.:Наука, 1974.

7. Лоенко М. Ю. Алгоритм коррекции решения // Тр. конф. молодых ученых, посвященной 10-летию ИВТ СО РАН. Новосибирск, 2001. - Т. 1. - С. 49-53.

8. Лоенко М. Ю. Внешнее оценивание множества решений ЗУ О с помощью ньютоновских корректоров // Тез. докл. конф. молодых ученых по математике, математическому моделированию и информатике. Новосибирск, 2001. - С. 18.

9. Лоенко М. Ю. Решение систем нелинейных уравнений методами интервального распространения ограничений // Вычислительные технологии. 2002. - Т. 7, N. 2. - С. 84-93.

10. Лоенко М. Ю. Вычисление элементарных функций с гарантированной точностью // Программирование. 2001. - Т. 27, N. 2. - С. 101-113.

11. Лоенко М. Ю. Улучшение внешней оценки множества решений задач удовлетворения ограничений // Новосибирск, 2000. 42с. - (Препр. / РАН. ИСИ; N. 79).

12. Нариньяни А.С., Недоопределенность в системах представления и обработки знаний // Изв.АН СССР. Техн. кибернетика. 1986. - N. 5. - С. 3-28.

13. Нариньяни А.С. Недоопределенные модели и операции с недоопределенными значениями. Новосибирск, 1982. - 33 с. - (Препр. / СОАН СССР. ВЦ; N. 400).

14. Ремез У.Я. Основы численных методов чебышевского приближения. Киев: Наукова думка, 1969.

15. Швецов И.Е., Телерман В.В., Интервалы и мультиинтервалы в недоопределенных вычислительных моделях // Тр. Междунар. конф. по интервальным и стохастическим методам в науке и технике "ИНТЕРВАЛ 92". - 1992. - Т. 1. - С. 201-203.

16. Шокин Ю.И. Интервальный анализ. Новосибирск: Наука, 1981.

17. Adams W., Lousraunau Р. Ап introduction to Grobner Bases // Graduate Studies in Math., Oxford University Press, 1994. Vol 3.

18. Aho A. V., Hopcroft J. E., Ullman J. D. Data structures and algorithms. Reading: Addison-Wesley, 1983.

19. Babichev A., Kadyrova O., Kashevarova Т., Semenov A. UniCalc as a tool for solving problems with inaccurate and subdefinite data // Proc. of the Conf. Interval'92. Interval Computations. - 1992. - Vol. 3, N. 5. - P. 13-16.

20. Benhamou F. Interval constraint logic programming // Constraint Programming: Basic and Trends / Ed. by A. Podelski. Berlin a.o.: Springer Verlag, 1995. - P. 1-21. - (Lect. Notes Comput. Sci.; Vol 910).

21. BibTeX bibliography elefunt.bib: http://netlib2.cs.utk.edu/bibnet/journals/ elefunt.html

22. Buchberger B. An algorithm for finding a basis for a residue class ring of a zero-dimensional polynomial ideal: Ph.D. Thesis, Univ. of Innsbruck (Austria), 1965.

23. Cleary. J. Logical Arithmetic // Future Comput. Syst. 1987. - Vol. 2, N. 2. P. 125-149.

24. Collavizza H., Delobel F., Rueher M. A note on partial consistencies over continuous domains // Proc. CP98, Pisa, Italy, October 26-30, 1998. Berlin a. o.: Springer Verlag, 1998. - P. 147-161.

25. Cox D., Little J., O'Shea D. Ideals, varieties, and algorithms. Berlin a.o.: Springer Verlag, 1992.

26. Davis E. Constraint propagation with interval labels // Artificial Intelligence. 1987 -Vol. 32, N. 3. - P. 281-331.

27. Deville Y., van Hentenryck P. An efficient arc consistency algorithm for a class of CSPs // Proc. of 13th Internat. Joint Conf. on AI, Sidney, Australia. 1991. - P. 325-330.

28. Freuder E.C. Synthesizing constraint expressions // Communs ACM. 1978. - Vol 21, N. 11. - P. 958-966.

29. Geddes K.O., Czapor S.R., Labahn G. Algorithms for Computer Algebra. Kluwer, Dordrecht, 1992.

30. Ginsberg M. L., Frank M., Halpin M. P., Torrance M. C. Search lessons learned from crossword puzzles // Proc. of the Eight National Conf. on Artificial Intelligence. San Francisco: Freeman, 1990. - P. 210-215.

31. Glibc Library for use with GNU/HURD and GNU/LINUX: http: //www.gnu/org/gnulist/production/glibc.html.

32. Golomb S.W. , Baumert L.D. Backtrack programming // J. of the ACM. 1965. - Vol 12, N. 4. - P. 516-524.

33. Gotlieb A., Lhomme O., Rueher M., Taillibert P. Boosting the interval narrowing algorithm // Proc. of JICSLP'96. MIT Press, 1996. - P. 378-392.

34. Goto E., Wong W. F. Fast evaluation of the elementary function in double precision // Proc. of the Twenty-Seventh Hawaii Internat. Conf. on System Sciences. Vol. 1: Architecture. Hawaii, 1994. - P. 349-358.

35. Granvilliers L. A Symbolic-numerical branch and prune algorithm for solving non-linear polynomial systems // J. of Universal Comput. Sci. 1998. - Vol 4, N. 2. - P. 125-135.

36. Hansen E. Global optimization using interval analysis. N.-Y.: Marcel Dekker, 1992.

37. Hansen E.A., Sengupta S. Bounding solutions of systems of equations using interval analysis // BIT. 1981. - Vol. 21. - P. 203-211.

38. Hansen E.A., Greenberg R.I. An interval Newton method // Appl. Math. Comput. -1983. Vol. 12. - P. 89-98.

39. Haralick, R.M. Elliot G.L. Increasing the search efficiency for constraint satisfaction problems // AI. 1980. - Vol. 14, N. 3. - P. 263-313.

40. Helzer G. Grebner Bases // Mathematica J. 1995. - Vol. 5, N. 1. - P. 67-73.

41. Hong H., Stahl V. Safe starting regions by fixed points and tightening // Computing. -1994. Vol. 53. - P. 323-335.

42. Huffman D.A. Impossible objects as nonsence sentences // Machine Intelligence. 1971.- Vol. 6. P. 295-323.

43. IEEE standard for binary floating-point arithmetic: Techn. Rep. IEEE Std 754-1985, Institute of Electrical and Electronics Engineers, 1985.- Reaffirmed, 1990.

44. Kashevarova Т., Leshchenko A., Petunin D., Semenov A. Combining various techniques with the algorithm of subdefinite calculations // Proc. of the 3rd International Conf. of PACT'97. London, England, 1997. - P. 287-306.

45. Kumar V. Algorithms for constraint-satisfaction problems: a survey // AI. 1992. - Vol. 13, N. 1. - P. 32-44.

46. Lawler E.L., Wood D.E. Branch-and-bound methods: A survey // Operations Research.- 1966. Vol. 14. - P. 699-719.

47. Lhomme 0., Gotlieb A., Rueher M. Dynamic optimization of Interval Narrowing Algorithms //J. of Logic Programming. 1998. - Vol. 37, N. 1-3. - P. 165-183.

48. Lhomme O. Consistency techniques for numeric CSP's // Proc. of the 13th IJCAI / Ed. by R. Bajcsy. IEEE Computer Society Press, 1993. - P. 232-238.

49. Loenko M. Yu. Solving CSPs with predominating constraints of the "not equal" type // Joint Bulletin of NCC and IIS. 2001. - Vol. 16. P. 45-55.

50. Loenko M. Yu. A non-return search algorithm // Proc. of 4th Int. workshop on Integration of AI and OR techniques in constraint Programming for Combinatorial Optimisation Problems, Le Croisic, France, March 25-27, 2002. Le Croisic, 2002. - P. 251-260.

51. Macworth A. Consistency in networks of relations // Artificial Intelligence. 1977. - Vol. 8, N. 1. - P. 99-118.

52. Marti P., Rueher M. A distributed cooperating constraints solving system // Intern. J. on Artificial Intelligence Tools. 1995. - Vol. 4, N. 1-2. - P. 93-113. - (ps available from: http://wwwi3s.unice.fr/ rueher).

53. Math library fdlibm: http://hpux.dsi.unimi.it/hppd/hpux/Maths/Misc/fdlibm-5.!.

54. Meintjes K., Morgan A.P. Chemical equilibrium systems as numerical test problems // ACM Transact. Math. Software. 1990. - Vol. 16. - P. 143-151.

55. Melenk H. Solving polynomial equation systems by groebner type methods // CWI Quarterly. 1990. - Vol. 3, N. 2. - P. 121-136.

56. Minton S., Johnston M. D., Philips А. В., Laird P. Solving large-scale constraint satisfaction and scheduling problems using a heuristic repair method. // Proc. of AAAI90. 1990. - P. 17-24.

57. Mitten L. G. Branch-and-bound methods // General Formulation and Properties Operations Research. 1970. - Vol. 18. - P. 24-34.

58. Moore. R. Interval analysis. Englewood Cliffs: Prentice-Hall, 1966.

59. More J. J., Garbow B. S., Hillstrom К. E. Testing unconstrained optimization software //ACM Trnsact. Math. Software. 1981. - Vol. 7, N. 1. - P. 17-41.

60. Morgan A.P. Solving polynomial systems using continuation for scientific and engineering problems. Englewood Cliffs: Prentice-Hall, NJ, 1987.

61. Muller J.-M. and Tisserand A. Towards exact rounding of the elementary functions // Scientic Computing and Validated Numerics / Proc. of SCAN'95, Wuppertal, Germany, 1996. Berlin: Akademie Verlag, 1996.

62. Nakos G., Glinos N. Grebner Bases over the Integers // Mathematica J. 1994. - Vol. 4, N. 3. - P. 70-75.

63. Nilsson N.J. Principles of artificial intelligence. Palo Alto: Tioga, 1980.

64. Numerical Computation Guide. Mountain View, USA, November, 1995.

65. Older W. and Vellino A. Constraint arithmetic on real intervals // Constraint Logic Programming: Selected Research / Ed. by F. Benhamou and A. Colmerauer. MIT Press. - 1993. - P. 175-195.

66. Petunin D., Semenov A. The use of multi-intervals in the UniCalc solver // Scientific Computing and Validated Numerics / Ed. by G. Alefeld, A. Frommer and B. Lang. -Berlin: Akademie Verlag, 1996. P. 91-97.

67. Prosser P. MAC-CBJ: maintaining arc consistency with conflict-directed backjumping: Research Rep. 95/177, Department of Computer Science. University of Strathclyde, 1995.

68. Puget J.-F., van Hentenryck P. A Constraint Satisfaction Approach to a Circuit Design Problem: Tech. Rep. N. CS-96-34, Department of Computer Science. Brown University, December 1996.

69. Rueher M. An architecture for cooperating constraint solvers on reals //Constraint Programming: Basics and Trends. Berlin a.o.:Springer Verlag, 1995. - P.231-250. -(Lect. Notes Comput. Sci.; Vol. 910).

70. Selman В., Levesque H., Mitchell D. A new method for solving hard satisfiability problems // Proc. of the 10th National Conf. on AI, San Jose, USA. 1992. - P. 440-446.

71. Semenov A.L. Solving integer/real nonlinear equations by constraint propagation: Tech. Rep. N12, Institute of Mathematical Modelling. The Technical University of Denmark, 1994.

72. Smith B.M. Filling the gaps: reassignment heuristics for constraint satisfaction problems: Rep. N. 92.29, School of Computer Studies. University of Leeds, November 1992.

73. Tsang E. Foundations of constraint satisfaction. London: Academic Press, 1993. - 421 p.

74. Van Hentenryck P., McAllester D., Kapur D. Solving polynomial systems using a branch and prune approach: Techn. Rep. N. CS-95-01, Department of Computer Science. Brown University, February 1995.

75. Van Hentenryck P., Michel L. and Deville Y. Numerica: a modeling language for global optimization. Cambridge: MIT Press, 1997.

76. XSC software: http://www.xsc.de.