Применение методов распространения ограничений при поиске допустимых решений

СОДЕРЖАНИЕ
ВВЕДЕНИЕ. 3
1 ОБЩИЕ СВЕДЕНИЯ ОБ ИНТЕРВАЛЬНОЙ АРИФМЕТИКЕ. 4
1.1 Интервальная арифметика. Интервальные числа. 4
1.2 Стандартная интервальная арифметика. 5
1.3 Интервальная арифметика с нестандартными вычитанием и делением. 6
1.4 Теоретические аспекты методов распространения ограничений. 7
2 МЕТОДЫ РАСПРОСТРАНЕНИЯ ОГРАНИЧЕНИЙ.. 9
2.1 Алгоритм Indigo. 9
2.2 Реализация на ЭВМ алгоритма Indigo. 12
2.3 Алгоритм Incremental Hierarchical Constraint Solver (IHCS)14
ЗАКЛЮЧЕНИЕ. 17
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ.. 18
ПРОЛОЖЕНИЕА. Текст программы на Delphi19

ВВЕДЕНИЕ
Распространение ограничений (иногда также называемое удовлетворением ограничениям или программированием в ограничениях) является одной из наиболее интенсивно развивающихся областей искусственного интеллекта, связанной с решением разнообразных задач. Представление проблемы в виде задачи распространения ограничений позволяет применять для ее решения наряду со специальными методами прикладной области достаточно эффективные и универсальные методы решения задач распространения ограничений. В настоящее время техника распространения ограничений все чаще используется как основа для решения различных прикладных задач, таких как временные рассуждения, задачи ресурсного и календарного планирования, математическое и инженерное моделирование, задачи на графах и т.д. Поэтому естественным является большое внимание, уделяемое исследованию и методов решения задач удовлетворения ограничений.
Как правило, эти задачи представляют собой совокупность уравнений и неравенств, связывающих некоторые непрерывные переменные, хотя иногда ограничения могут задаваться в виде таблиц, а также включать целочисленные переменные.
Целью данной курсовой работы является рассмотрение применения методов распространения ограничений при поиске допустимых решений.
Курсовая работа состоит из двух частей.
В первое части рассмотрены теоретические аспекты задачи распространения ограничений, а также общие сведения об интервальной арифметике.
Во второй части рассмотрены два алгоритма распространения ограничений 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) для интервального умножения будет выглядеть так (мы полагаем ):
1.
2.
3.
4.
5.
6.
7.
8.
9. .
Отсюда видно, что только в одном (последнем) случае для нахождения произведения требуется четыре умножения, а в остальных достаточно двух умножений.
Если и – вырожденные интервалы, то равенства (1.5) – (1.8) совпадают с обычными арифметическими операциями над вещественными числами. Таким образом, интервальное число есть обобщение вещественного числа, а интервальная арифметика – обобщение вещественной.
Из определения (1.4) непосредственно видно, что интервальные сложение и умножение ассоциативны и коммутативны, иначе говоря, для имеют место равенства
,
.
Роль нуля и единицы играют обычные 0 и 1, которые, как отмечалось, отождествляются с вырожденными интервалами и . Другими словами,
для любого . В дальнейшем точку для обозначения умножения будем, как правило, опускать.
Равенство (1.4) (как и (1.5) – (1.8)) показывает, что если один из операндов является невырожденным интервалом, то результат арифметической операции также невырожденный интервал. Исключение составляет умножение на . Отсюда, в частности, следует, что для невырожденного интервала не существует обратных по сложению и умножению элементов, так как если , то должны быть в силу сказанного вырожденными,
т.е вычитание не обратно сложению, деление не обратно умножению. Значит, , когда . Понятно, однако, что всегда .
1.3 Интервальная арифметика с нестандартными вычитанием и делением
Нестандартные операции вычитания и деления , определенные для элементов , вводятся следующим образом:
,
,
Обозначим и укажем некоторые свойства, связанные с операциями и .
1. .
2. , , для (по определению ).
3. Из равенства не следует ; например, .
4. Для уравнение имеет единственное решение: .
5. Для уравнение имеет решение . В случае у этого уравнения есть еще одно решение: .
6. Уравнение имеет решение . Если , то существует еще одно решение: .
7. тогда и только тогда, когда или , или .
8. .
9. , для (по определению ).
10. Из равенства не следует ; например, .
Определим для элементов функцию следующим образом:
.
11. Уравнение при имеет решение тогда и только тогда, когда , которое выражается в виде .
12. Уравнение при имеет решение . Если , то существует еще одно решение: .
13. Уравнение имеет решение . Если , то имеется еще одно решение: .
14. тогда и только тогда, когда или , или .
1.4 Теоретические аспекты методов распространения ограничений
Областью определения переменной называется множество всех возможных значений, которые могут быть присвоены этой переменной. Обозначается . Если же является непрерывной переменной, то соответствующая область содержит бесконечное число элементов, являющихся вещественными числами, большинство из которых не представимо в компьютере. Так как на компьютере можно представить только множество чисел с плавающей запятой, то тем самым в практических приложениях бесконечная область значений непрерывной переменной заменяется конечной.Мы будем обозначать множество чисел с плавающей запятой через FP . Таким образом, для вещественных чисел, не входящих во множество FP , мы используем аппроксимацию элементами из FP [1].
Самым точным и надежным с вычислительной точки зрения является представление вещественного числа интервалом . Таким образом, мы аппроксимируем бесконечное множество значений конечным, заменяя одним элементом бесконечное множество значений, лежащих в данном интервале и не являющихся элементами из FP . Таким образом, мы используем описанные в предыдущей главе методы интервальной математики для определения значений переменных и нахождения значений ограничений, то есть в этом случае результатом вычисления значения левой части отношения будет некоторый интервал.
Пусть мы имеем ограничение , заданное в виде отношения равенства .
Будем говорить, что отношение на множестве непрерывных переменных справедливо для множества значений , где каждое есть интервал, если .
Численной задачей удовлетворения ограничений (ЧЗУО) называется тройка ,
где – конечное множество переменных ,
– функция, отображающая каждую переменную из на множество объектов произвольного типа:
Будем рассматривать как множество объектов, отображенных из функцией . Эти объекты называются значениями переменной , а множество – областью [1].
– конечное (возможно пустое) множество ограничений на произвольном подмножестве переменных из .
Решением численной ЗУО называется множество значений переменных , такое что и все ограничения из удовлетворяются.
2 МЕТОДЫ РАСПРОСТРАНЕНИЯ ОГРАНИЧЕНИЙ
2.1 Алгоритм I ndigo
Входными данными для алгоритма Indigo является множество ограничений, включая равенства и неравенства, и набор переменных. Алгоритм определяет оптимальный интервал для всей системы.
Выполнение алгоритма происходит от самого сильного ограничения к самому слабому, в ходе которого мы пытаемся удовлетворить каждое ограничение путем сжимания границ переменных, входящих в него. Сжимание границ одних переменных ограничения может стать причиной сжимания границ других переменных. Для реализации этого алгоритм содержит очередь ограничений, которые необходимо проверить. Изначально очередь содержит только исходные ограничения . Если мы можем сжать границы любой переменной ограничения , мы добавляем в очередь другие ограничения, содержащие эту переменную. Продолжаем обрабатывать ограничения из очереди до тех пор, пока она не станет пустой. После того, как все ограничения были обработаны, мы получаем значения всех переменных [3].
Псевдокод алгоритм выглядит следующим образом:
all constraints := list of all constraints, strongest first;
all variables := set of all variables;
active_constraints := new set;
for v in all variables do
initialize v.bounds to unbounded;
end for;
for current constraint in all constraints do
tight_variables := new set;
queue := new queue;
queue.add(current_constraint);
while queue not empty do
cn := queue.front;
tighten_bounds(cn, queue, tight_variables,
active_constraints);
check_constraint(cn, active_constraints);
queue.dequeue;
end while;
end for;
Переменная active_constraints содержит множество ограничений, которые уже были рассмотрены, но которые могут быть рассмотрены опять, если мы сожмем границы одной из переменной ограничений. Во время обработки каждого ограничения очередь (queue ) содержит множество ограничений, границы чьих переменных может потребоваться сжать, и tight_variables – это множество переменных, чьи границы были сжаты во время обработки текущего ограничения. Во время обработки текущего ограничения мы никогда не сжимаем границы одной переменной дважды.
Процедура tighten_bounds сжимает границы переменных ограничения , и добавляет в очередь другие затронутые ограничения. Процедура check _ constraint проверяет на неудовлетворенность требуемые ограничения и также определяет, когда ограничения должны быть добавлены или удалены из множества active _ constraints .
Procedure tighten_bounds(cn, queue, tight variables, active constraints)
for v in cn.variables and v not in tight_variables do
tighten_flag := cn.tighten_bounds_for(v);
tight_variables.add(v);
if tighten_flag then
for c in v.constraints do
if c in active_constraints and c not in queue then
queue.add(c);
end if;
end for;
end if;
end for;
endproceduretighten_bounds;
В процедуре tighten _ bounds процедура tighten _ bounds _ for сжимает границы переданной переменной, на сколько это возможно, и возвращает истину, если границы изменились.
Procedure check_constraint(cn, active constraints)
If cn is unary then
If cn is required and cn is not satisfiable then
exception(required_constraint_not_satisfied);
end if;
return;
end if;
if not all of c’s variables have unique values then
active_constraints.add(cn);
return;
end if;
if cn is satisfied then
active_constraints.delete(cn);
else if cn is required then
exception(required_constraint_not_satisfied);
else exception(constraints_too_difficult);
end if;
end procedure check_constraint;
В процедуре check _ constraint мы в первую очередь смотрим, унарное ли ограничение . Унарным является то ограничение, которое содержат только одну переменную. Унарное ограничение должно быть обработано только один раз, т.к. нет больше причин рассматривать его, потому что его влияние полностью представлено в текущих границах переменной, которую оно содержит. Иначе ограничение является -арным. Если не все переменные имеют уникальные значения, то нам необходимо добавить в active _ constraints , т.к. нам будет необходимо рассмотреть опять, когда границы одной из его переменных будут сжаты. Однако, если все переменные имеют уникальные значения, больше никогда не нужно будет рассматривать, и ограничение нужно удалить из active _ constraints , если оно там находится.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию