Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

Информатика->Реферат
активное использование постоянно расширяющегося интеллектуального потенциала общества, сконцентрированного в печатном фонде, и научной, производственн...полностью>>
Информатика->Реферат
То, что информация имеет ценность, люди осознали очень давно – недаром переписка сильных мира сего издавна была объектом пристального внимания их недр...полностью>>
Информатика->Реферат
Прямокутні таблиці широко використовуються для впорядкованого зберігання даних і наочного представлення чисел або текстової інформації в багатьох галу...полностью>>
Информатика->Реферат
Microsoft Access — реляционная СУБД корпорации Microsoft. Имеет широкий спектр функций, включая связанные запросы, связь с внешними таблицами и базами...полностью>>

Главная > Курсовая работа >Информатика

Сохрани ссылку в одной из сетей:

Курсовая работа

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

Ярошук Юлия Викторовна – студентка 4 курса специальности «Экономическая кибернетика»

Печко Елена Владимировна – преподаватель кафедры математического моделирования

Брест 2010

СОДЕРЖАНИЕ

ВВЕДЕНИЕ 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

ПРОЛОЖЕНИЕ А 19

ВВЕДЕНИЕ

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

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

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

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

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

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

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. .

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

Если и – вырожденные интервалы, то равенства (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. Из равенства не следует ; например, .

Определим для элементов функцию следующим образом:

.

  1. Уравнение при имеет решение тогда и только тогда, когда , которое выражается в виде .

  2. Уравнение при имеет решение . Если , то существует еще одно решение: .

  3. Уравнение имеет решение . Если , то имеется еще одно решение: .

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



Загрузить файл

Похожие страницы:

  1. Методы принятия управленческих решений в условиях определенности

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

    Курсовая работа >> Экономико-математическое моделирование
    ... ограничений задачи ОДР является пустым множеством. При поиске оптимального решения ... допустимого множества Q0 двойственной задачи, при котором значение целевой функции возрастает, т. е. в применении симплексного метода к решению ... широкое распространение ...
  3. Методы принятия управленческих решений (2)

    Реферат >> Государство и право
    ... решений; определение ограничений и критериев принятия решения ... методах прикладной статистики. Наиболее распространен метод ... очевидна. При применении метода сценариев необходимо ... допустимые полезные результаты при ... Метод инверсии. При поиске идеи решение ...
  4. Методы и модели принятия решений (2)

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

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

Хочу больше похожих работ...

Generated in 0.00148606300354