Решение задачи коммивояжера
ВНИМАНИЕ!
Здесь приводится очень сокращённый текст курсовой работы. Если данная информация вас заинтересовала, то
вы можете по указанной ниже ссылке скачать бесплатно полную версию курсовой работы с исходными кодами.
Введение
Задача коммивояжёра, известная также как
Задача о сверлильном станке
или
алгоритм коммивояжёра, широко применяется при разработке программного обеспечения
(и не только для этого). Постановка задачи коммивояжёра и решение задачи коммивояжёра
являются темой для данной курсовой работы. В курсовой работе кратко рассмотрены некоторые методы
решения задачи коммивояжера и разработана программа, реализующая один из методов решения данной задачи
(этот метод известен под названием
Жадный алгоритм).
Термин
алгоритм используется в компьютерных науках для описания метода решения задачи,
пригодного для реализации в виде компьютерной программы. Алгоритмы составляют основу
компьютерных наук: они являются основными объектами изучения во многих, если не в
большинстве ее областей.
Изучение алгоритмов требует сочетания нескольких подходов: творческого — для
выработки идеи решения задачи; логического — для анализа правильности решения;
математического — для анализа производительности; и скрупулезного — для выражения
идеи в виде подробной последовательности шагов, чтобы она могла превратиться в программу.
Когда компьютер используется для решения той или иной задачи, как правило, мы сталкиваемся
с рядом возможных различных подходов. При решении простых задач выбор того или иного
подхода вряд ли имеет особое значение, если только выбранный подход приводит к
правильному решению. Однако, при решении сложных задач (или в приложениях, в которых
приходится решать очень большое количество простых задач) мы немедленно сталкиваемся
с необходимостью разработки методов, при которых время или память используются с
максимальной эффективностью.
Основная побудительная причина изучения алгоритмов состоит в том, что это
позволяет обеспечить огромную экономию ресурсов, вплоть до получения решений задач,
которые в противном случае были бы невозможны. В приложениях, в которых обрабатываются
миллионы объектов, часто оказывается возможным ускорить работу программы в
миллионы раз, используя хорошо разработанный алгоритм. Для сравнения, вложение
дополнительных денег или времени для приобретения и установки нового компьютера
потенциально позволяет ускорить работу программы всего в 10-100 раз.
Тщательная разработка алгоритма — исключительно эффективная часть процесса
решения сложной задачи в любой области применения.
Данная курсовая работа рассматривает один из хорошо известных алгоритмов –
жадный алгоритм, который будет использован при решении задачи коммивояжера.
А еще мы напишем несложную программу, которая будет использовать этот алгоритм.
Задача коммивояжера
Гамильтонов цикл
Классические комбинаторные задачи – это задачи выбора и расположения элементов
конечного множества, имеющие в качестве исходной некоторую формулировку развлекательного
содержания типа головоломок.
В 1859 г. У. Гамильтон придумал игру «Кругосветное путешествие», состоящую в отыскании
такого пути, проходящего через все вершины (города, пункты назначения) графа,
изображенного на рис. 1, чтобы посетить каждую вершину однократно и возвратиться в исходную.
Пути, обладающие таким свойством, называются гамильтоновыми циклами.
Практическое применение
Задача коммивояжера имеет ряд практических применений. Как следует из самого названия
задачи, ее можно использовать для составления маршрута человека, который должен
посетить ряд пунктов и, в конце концов, вернуться в исходный пункт. Например, задача коммивояжера
использовалась для составления маршрутов лиц, занимающихся выемкой монет из таксофонов.
В этом случае вершинами являются места установки таксофонов и "базовый пункт".
Стоимостью каждого ребра (отрезка маршрута) является время в пути между двумя
точками (вершинами) на маршруте.
Еще одно применение – это задача о сверлильном станке. Сверлильный станок
изготавливает металлические листы с некоторым количеством отверстий. Координаты
отверстий известны. Необходимо найти кратчайший путь через все отверстия, а значит,
и наименьшее время, затрачиваемое на изготовление одной детали. Как говорится,
смех смехом, а если такой станок делает миллион деталей в год, то даже
миллиметровая выгода может сэкономить приличные средства. Поэтому в цивилизованных
странах и не жалеют денег на инвестиции в информационные технологии.
Но это уже другая история…
Общее описание
Задача коммивояжера (в дальнейшем сокращённо - ЗК) является одной из знаменитых задач
теории комбинаторики. Она была поставлена в 1934 году, и об неё, как об
Великую теорему Ферма обламывали зубы лучшие математики. В своей области
(оптимизации дискретных задач) ЗК служит своеобразным полигоном, на котором
испытываются всё новые методы.
Постановка задачи следующая.
Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по
одному разу в неизвестном порядке города 2,3,4..n и вернуться в первый город.
Расстояния между городами известны. В каком порядке следует обходить города,
чтобы замкнутый путь (тур) коммивояжера был кратчайшим?
Методы решения задачи коммивояжера
Жадный алгоритм
Жадный алгоритм – алгоритм нахождения наикратчайшего расстояния путём выбора
самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла
с уже выбранными рёбрами. «Жадным» этот алгоритм назван потому, что на последних
шагах приходится жестоко расплачиваться за жадность.
Посмотрим, как поведет себя при решении ЗК жадный алгоритм. Здесь он превратится
в стратегию «иди в ближайший (в который еще не входил) город». Жадный алгоритм,
очевидно, бессилен в этой задаче. Рассмотрим для примера сеть на рис. 2,
представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм
«иди в ближайший город» выведет его в город 2, затем 3, затем 4; на последнем
шаге придется платить за жадность, возвращаясь по длинной диагонали ромба.
В результате получится не кратчайший, а длиннейший тур. Однако в некоторых
ситуациях «жадный» алгоритм определяет-таки кратчайший путь.
Полный перебор
Метод полного перебора
заключается в том, что выполняется перебор всех возможных
комбинаций точек (пунктов назначения). Как известно из математики, число таких
перестановок равно n!, где n – количество точек. Так как в задаче коммивояжера
исходный пункт обычно принимается одним и тем же (первая точка), то нам достаточно
перебрать оставшиеся, т.е. количество перестановок будет равно
(n–1)!. Этот алгоритм почти всегда дает точное решение задачи коммивояжера, однако
продолжительность таких вычислений может занять непозволительно много времени.
Известно, что при значениях n > 12, современный компьютер не смог бы решить
задачу коммивояжера даже за все время существования вселенной.
А теперь рассмотрим пример (см. рис.3). На рис. 3а показан граф с шестью вершинами
(их часто называют "городами"), который может служить основой для задачи коммивояжера.
Заданы координаты каждой вершины, а весом каждого ребра считается его длина.
Мы предполагаем (и такое предположение характерно для задачи коммивояжера), что
существуют все ребра графа, т.е. граф является полным. В более общих случаях,
когда вес ребер не основывается на евклидовом расстоянии, у ребра может оказаться
бесконечный вес, чего в действительности, конечно, не бывает.
На рис. 3 b,c,d,e показаны четыре маршрута по шести "городам". Протяженности
этих четырех маршрутов равняются 50.00, 49.73, 48.39 и 49.78 соответственно.
Маршрут на рис. 3d является кратчайшим из всех возможных маршрутов.
Результат, показанный на рис. 3b, можно получить с помощью жадного алгоритма.
Как видим, от кратчайшего маршрута этот результат отличается всего на 3,22%.
Такая погрешность вполне допустима, если скорость выполнения алгоритма имеет значение
(а при решении сложных задач так всегда и бывает). В данном примере можно было
бы применить и полный перебор – современный компьютер справился бы довольно быстро.
Как уже упоминалось, существуют и другие алгоритмы для решения задачи коммивояжера,
которые значительно точнее жадного алгоритма и значительно быстрее метода полного
перебора. Однако дисциплина называется «Программирование и основы алгоритмизации»,
из чего следует, что на первом месте у нас все-таки программирование, а уж потом
можно и с алгоритмами разбираться. Поэтому в данной курсовой работе другие
алгоритмы не рассматриваются в виду относительной сложности. Да и пора бы
нам уже написать какую-нибудь программу…
