Эвристические методы
Курсовая работа, 22 Ноября 2013, автор: пользователь скрыл имя
Краткое описание
ТЕОРИЯ ГРАФОВ - это область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Теория графов находится сейчас в самом расцвете. Обычно её относят к топологии (потому что во многих случаях рассматриваются лишь топологические свойства графов), однако она пересекается со многими разделами теории множеств, комбинаторной математики, алгебры, геометрии, теории матриц, теории игр, математической логики и многих других математических дисциплин. Основной объект теории графов-граф и его обобщения.
Содержание
Введение
I. Основные понятия
1.Эйлеровы графы.
2. Кротчайшие пути.
3. Деревья.
II.Задача коммивояжера.
1.Общие описание.
2.Методы решения ЗК.
а. Жадный алгоритм.
б. Деревянный алгоритм.
в. Метод ветвей и границ.
III. Выводы.
Литература.
Вложенные файлы: 1 файл
kursovik.doc
— 1.67 Мб (Скачать файл)Таким образом, для решения ЗК нужно n раз применить алгоритм Дейкстры следующим образом.
Возьмём произвольную пару вершин
j,k. Исключим непосредственное ребро C[j,k]. С помощью алгоритма Дейкстры найдём кратчайшее расстояние между городами j..k. Пусть это расстояние включает некоторый город m. Имеем часть тура j,m,k. Теперь для каждой пары соседних городов (в данном примере – для j,m и m,k) удалим соответственное ребро и найдём кратчайшее расстояние. При этом в кратчайшее расстояние не должен входить уже использованный город.
Далее аналогично находим кратчайшее расстояние между парами вершин алгоритмом Дейкстры, до тех пор, пока все вершины не будут задействованы. Соединим последнюю вершину с первой и получим тур. Чаще всего это последнее ребро оказывается очень большим, и тур получается с погрешностью, однако алгоритм Дейкстры можно отнести к приближённым алгоритмам.
III. Выводы
- Изучены эвристический, приближенный и точный алгоритмы решения ЗК. Точные алгоритмы решения ЗК – это полный перебор или усовершенствованный перебор. Оба они, особенно первый, не эффективны при большом числе вершин графа.
- Проведён анализ наиболее рациональных методов решения ЗК и определены области их эффективного действия: для малого числа вершин можно использовать точный метод лексического перебора; для большого числа вершин рациональнее применять метод ветвей и границ.
- Изучены практические применения ЗК и задачи с переналадками, сводимые к ЗК.
- Приведены тексты программ, позволяющие решить ЗК различными методами.
Литература
- О. Оре Графы и их применение. Пер. с англ. под ред. И.М. Яглома. - М., “Мир”, 1965, 174 с.
- В. П. Сигорский. Математический аппарат инженера. - К., “Техніка”, 1975, 768 с.
- Ю. Н. Кузнецов, В. И. Кузубов, А. Б. Волощенко. Математическое программирование: учебное пособие. 2-е изд. перераб. и доп. - М.; Высшая школа, 1980, 300 с., ил.
- Е. В. Маркова, А. Н. Лисенков. Комбинаторные планы в задачах многофакторного эксперимента. – М., Наука, 1979, 345 с.
- Е. П. Липатов. Теория графов и её применения. - М., Знание, 1986, 32 с.
- В. М. Бондарев, В. И. Рублинецкий, Е. Г. Качко. Основы программирования. – Харьков, Фолио; Ростов на Дону, Феникс, 1998, 368 с.
- Ф. А. Новиков Дискретная математика для программистов. - Санкт-Петербург, Питер, 2001, 304 с., ил.