Формулировка задачи коммивояжера и алгоритмы ее решения

Автор работы: Пользователь скрыл имя, 20 Мая 2013 в 11:15, реферат

Описание работы

В 1859 г. У. Гамильтон придумал игру “Кругосветное путешествие”, состоящую в отыскании такого пути, проходящего через все вершины (города, пункты назначения) графа, изображенного на рис. 1, чтобы посетить каждую вершину однократно и возвратиться в исходную. Пути, обладающие таким свойством, называются гамильтоновыми циклами.
Задача о гамильтоновых циклах в графе получила различные обобщения. Одно из этих обобщений – задача коммивояжера, имеющая ряд применений в исследовании операций, в частности при решении некоторых транспортных проблем.

Содержание работы

Введение 3
Задача коммивояжера 4
Общее описание 4
Методы решения задачи коммивояжера 5
Жадный алгоритм. 5
Деревянный алгоритм 8
Метод ветвей и границ 10
Алгоритм Дейкстры 14
Анализ методов решения задачи коммивояжера 17
Практическое применение задачи коммивояжера 18
Выводы 20
Литература 21

Скачать архив (149.58 Кб) Сколько стоит заказать работу?
Файлы: 1 файл

реферат.docx

— 155.31 Кб (Скачать файл)

 

Литература

 

  1. О. Оре  Графы и их применение. Пер. с англ. под ред. И.М. Яглома. - М., “Мир”, 1965, 174 с.
  2. В. П. Сигорский. Математический аппарат инженера. - К., “Техніка”, 1975, 768 с.
  3. Ю. Н. Кузнецов, В. И. Кузубов, А. Б. Волощенко. Математическое программирование: учебное пособие. 2-е изд. перераб. и доп. - М.; Высшая школа, 1980, 300 с., ил.
  4. Е. В. Маркова, А. Н. Лисенков. Комбинаторные планы в задачах многофакторного эксперимента. – М., Наука, 1979, 345 с.
  5. Е. П. Липатов. Теория графов и её применения. - М., Знание, 1986, 32 с.
  6. В. М. Бондарев, В. И. Рублинецкий, Е. Г. Качко. Основы программирования. – Харьков, Фолио; Ростов на Дону, Феникс, 1998, 368 с.
  7. Ф. А. Новиков Дискретная математика для программистов. - Санкт-Петербург, Питер, 2001, 304 с., ил.

 

Стр.


Информация о работе Формулировка задачи коммивояжера и алгоритмы ее решения