1. Введение 3
2. Постановка задачи коммивояжера. Описание алгоритма 4
3. Иерархическая кластеризация 6
4. Метод ветвей и границ. Как соединять локальные маршруты? 8
5. Разработка программы для анализа алгоритма 11
6. Экспериментальный анализ алгоритма 19
7. Заключение 25
8. Приложения 26
9. Список литературы 61
Задача коммивояжера это задача комбинаторной оптимизации, которая заключается в отыскании оптимального маршрута для прохождения через каждый город по одному разу и возврата в исходный город. Одним из первых эту задачу пытался решить еще в 18 веке ирландский математик Уильям Роуэн Гамильтон. Сейчас существует множество методов решения этой задачи: приближенных, точных. Задачу коммивояжера можно решить перебором, но число решений быстро увеличивается с увеличением числа объектов.Доказано, что не существует алгоритма решения имеющего степенную сложность (то есть требующего порядка паопераций для некоторого а). Поэтому алгоритмы точного решения существуют только для очень небольшого числа объектов. Большинство алгоритмов направлены на нахождение приближенного решения.
Одними из самых популярных методов решения задачи коммивояжера являются: «метод ветвей и границ», метод минимального остовного дерева. Алгоритм «ветвей и границ» был разработан Лендом и Доигом в 1960 году для решения задач целочисленного программирования. Также существует алгоритм Дейкстры, который ищет кратчайший путь между двумя парами точек. Он был изобретен нидерландским ученым Эдсгером Дейкстрой в 1959 году и также может использоваться для решения задачи коммивояжера. Алгоритм работает только для графов без ребер отрицательного веса.
Цель моей дипломной работы состоит в том, чтобы исследовать эвристический алгоритм, основная идея которого состоит в том, чтобы разбить исходную задачу на множество подзадач с помощью иерархической кластеризации. Кластеризация - задача анализа данных,относящаяся к типу задач «обучение без учителя». Такой тип задач подразумевает ,что известны только описания объектов и требуется найти взаимосвязи, закономерности между ними. Иерархическая кластеризация подразумевает последовательное объединение объектов сходных по какому-то признаку в группу, которая называется кластером. Кластеризация будет продолжаться до тех пор, пока все объекты не объединятся в один кластер. Таким образом, у нас будет иерархия, вложенность последовательных объединений объектов.
Итак, общий итог проведенной работы можно определить так: эвристические алгоритмы, в том числе описанный мной, могут применяться и быть полезными в решении задач, в частности задачи коммивояжера. Зачастую воспользоваться эвристическим алгоритмом удобней и проще. Конечно вероятность неточного решения высока, но есть много задач, для которых достаточно и приближенного решения.
Вышеописанный алгоритм, я считаю, применим поскольку погрешность этого алгоритма при оптимальной кластеризации в пределах допустимого, а также алгоритм увеличивает скорость выполнения задачи, благодаря свой основной идее: разбиение большого множества на подмножества для ускорения и упрощения расчетов.Тем не менее, результатами исследований я доволен, они практически полностью отвечают моим ожиданиям. Задача коммивояжера одна из сложнейших задач исследования операций.Она широко используется на практике. Большинство задач логистики, транспортировки так или иначе сводятся к задаче коммивояжера. Исследованный мной алгоритм вполне можно развивать оптимизировать, находить новые варианты упрощения алгоритма и его оптимизации. На основе вышесказанного, считаю, что работа проведена успешно и с пользой. Программный продукт, разработанный мной для исследования алгоритма, считаю, является хорошим и удобным инструментом исследования данного алгоритма, который также можно доработать и оптимизировать. В целом, считаю, что цели дипломной работы достигнуты и задачи в большей мере выполнены.
