ВНИМАНИЕ!
Здесь приводится Курсовая работа по программированию в очень сокращённом
варианте. Бесплатно скачать курсовую в полной версии вместе с исходными кодами
можно по указанной выше ссылке.
Алгоритм решения задачи коммивояжера
Задача коммивояжёра, известная также как
Задача о сверлильном станке или алгоритм коммивояжёра,
широко применяется при разработке программного обеспечения (и не только для этого).
Иногда говорят Программа решения задачи коммивояжера, однако это не совсем правильно
с точки зрения русского языка))).
Постановка задачи коммивояжёра и решение задачи коммивояжёра являются темой для данной
курсовой работы. В курсовой работе кратко рассмотрены некоторые методы решения задачи коммивояжера
и разработана программа, реализующая один из методов решения данной задачи (этот метод известен
под названием Жадный алгоритм).
Данная курсовая работа рассматривает один из хорошо известных алгоритмов – жадный алгоритм,
который будет использован при решении задачи коммивояжера. А еще мы напишем
в среде разработки Delphi несложную программу,
которая будет использовать этот алгоритм. Хотя среда разработки и язык программирования значения не имеют.
Задачу коммивояжёра можно решить и спомощью других средств, например, Excel.
Применение задачи коммивояжера на практике подробно обсуждать
не будем. Очевидно, что методы решения задачи коммивояжёра можно использовать, например,
при определении оптимального маршрута автомобиля, развозящего продукты по нескольким
торговым точкам.
Постановка задачи коммивояжера
Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по одному
разу в неизвестном порядке города 2,3,4..n и вернуться в первый город. Расстояния
между городами известны. В каком порядке следует обходить города, чтобы замкнутый
путь (тур) коммивояжера был кратчайшим?
Алгоритм решения задачи коммивояжера
Жадный алгоритм
Жадный алгоритм – алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого,
ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами.
«Жадным» этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться
за жадность.
Посмотрим, как поведет себя при решении ЗК жадный алгоритм. Здесь он превратится
в стратегию «иди в ближайший (в который еще не входил) город». Жадный алгоритм, очевидно,
бессилен в этой задаче. Рассмотрим для примера сеть на рис. 2, представляющую узкий ромб.
Пусть коммивояжер стартует из города 1. Алгоритм «иди в ближайший город» выведет его в город 2,
затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной
диагонали ромба. В результате получится не кратчайший, а длиннейший тур. Однако в некоторых
ситуациях «жадный» алгоритм определяет-таки кратчайший путь.
Полный перебор
Метод полного перебора (иногда говорят Метод перебора, подразумевая
при этом полный перебор - это не совсем правильно, так как перебор может быть и не полным)
заключается в том, что выполняется перебор всех возможных
комбинаций точек (пунктов назначения). Как известно из математики, число таких перестановок
равно n!, где n – количество точек. Так как в задаче коммивояжера исходный пункт обычно
принимается одним и тем же (первая точка), то нам достаточно перебрать оставшиеся,
т.е. количество перестановок будет равно (n–1)!. Этот алгоритм почти всегда дает точное
решение задачи коммивояжера, однако продолжительность таких вычислений может занять
непозволительно много времени. Известно, что при значениях n > 12, современный компьютер
не смог бы решить задачу коммивояжера даже за все время существования вселенной.
Как уже упоминалось, существуют и другие алгоритмы для решения задачи коммивояжера,
которые значительно точнее жадного алгоритма и значительно быстрее метода полного перебора.
Однако дисциплина называется «Программирование и основы алгоритмизации», из чего следует,
что на первом месте у нас все-таки программирование, а уж потом можно и с алгоритмами разбираться.
Поэтому в данной курсовой работе другие алгоритмы не рассматриваются в виду относительной
сложности. Да и пора бы нам уже написать какую-нибудь программу в любимой нами Delphi.
|
