Применение методов распространения ограничений при поиске допустимых решений (стр. 1 из 6)

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

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

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

Курсовая работа состоит из двух частей.

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

Во второй части рассмотрены два алгоритма распространения ограничений Indigoи IHCS(IncrementalHierarchicalConstraintSolver.

1 ОБЩИЕ СВЕДЕНИЯ ОБ ИНТЕРВАЛЬНОЙ АРИФМЕТИКЕ

1.1 Интервальная арифметика. Интервальные числа

Пусть

– множество всех вещественных чисел. Под интервалом

понимается замкнутое ограниченное подмножество

вида

Множество всех интервалов обозначим через

. Элементы

обычно записывают прописными буквами. Если

– элемент

, то его левый и правый концы обозначаются как

. Элементы

называются интервальными числами.

Символы

и т. п. понимаются в обычном теоретико-множественном смысле, причем

обозначает не обязательно строгое включение, то есть соотношение

допускает равенство интервалов. Два интервала

равны тогда и только тогда, когда

Отношение порядка на множестве

определяется следующим образом:

тогда и только тогда, когда

. Возможно так же упорядочение по включению:

не превосходит

, если

Пересечение

интервалов

пусто, если

или

, в противном случае

– снова интервал.

Симметричным является интервал

, у которого

Шириной

интервала

называется величина

. (1.1)

Середина

есть полусумма концов интервала

. (1.2)

Абсолютная величина

определяется как

. (1.3)

Наконец,

. Нетрудно заметить, что

, когда

, причем

, если

Расстояние

между элементами

вводится равенством

Вырожденныйинтервал, то есть интервал с совпадающими концами

, отождествим с вещественным числом

. Таким образом,

1.2 Стандартная интервальная арифметика

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

. Тогда

, (1.4)

причем в случае деления

Легко проверить, что определение (1.4) эквивалентно соотношениям

, (1.5)

, (1.6)

, (1.7)

. (1.8)

Заметим, что операцию вычитания можно выразить через сложение и умножение, положив

В зависимости от знака чисел

правило (1.7) для интервального умножения будет выглядеть так (мы полагаем