Формулировка задачи коммивояжера и алгоритмы ее решения
Реферат, 20 Мая 2013, автор: пользователь скрыл имя
Описание работы
В 1859 г. У. Гамильтон придумал игру “Кругосветное путешествие”, состоящую в отыскании такого пути, проходящего через все вершины (города, пункты назначения) графа, изображенного на рис. 1, чтобы посетить каждую вершину однократно и возвратиться в исходную. Пути, обладающие таким свойством, называются гамильтоновыми циклами.
Задача о гамильтоновых циклах в графе получила различные обобщения. Одно из этих обобщений – задача коммивояжера, имеющая ряд применений в исследовании операций, в частности при решении некоторых транспортных проблем.
Содержание работы
Введение 3
Задача коммивояжера 4
Общее описание 4
Методы решения задачи коммивояжера 5
Жадный алгоритм. 5
Деревянный алгоритм 8
Метод ветвей и границ 10
Алгоритм Дейкстры 14
Анализ методов решения задачи коммивояжера 17
Практическое применение задачи коммивояжера 18
Выводы 20
Литература 21