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