Задача о коммивояжере состоит в том, чтобы объехать заданные города по одному разу в таком порядке, чтобы пройденное расстояние было минимальным.
Такая задача актуальна во многих областях, таких как автомобильные, судовые и железнодорожные перевозки, расчет авиационных линий, конвейерное производство.
Оглавление
Введение3
Постановка задачи4
Метод решения5
Возможно вы искали - Курсовая работа: Решение оптимизационных управленческих задач на основе методов и моделей линейного программирования
Язык программирования7
Описание алгоритма8
Описание основных структур данных12
Описание интерфейса с пользователем14
Заключение16
Похожий материал - Курсовая работа: Решение транспортной задачи с правильным балансом
Литература17
Текст программы18
Введение
Задача состоит в том, чтобы коммивояжер (торговец) обошел все намеченные города единожды и в таком порядке, чтобы его путь был наименьшим.
Эта задача заинтересовала меня потому, что её решение интересно с точки зрения программирования и составления алгоритма. Важно нахождение такого алгоритма, который позволит наиболее оптимально решить задачу.
Сейчас решение данной задачи необходимо во многих областях связанных с замкнутыми и при этом жестко связанными по времени системами, такими как: конвейерное производство, многооперационные обрабатывающие комплексы, судовые и железнодорожные погрузочные системы, перевозки грузов по замкнутому маршруту, расчет авиационных линий.
Очень интересно - Курсовая работа: Решение транспортных задач
Поэтому данная проблема на современном этапе развития общества имеет не самое последнее по значимости место.
Постановка задачи
Имеется N городов, которые должен обойти коммивояжер с минимальными затратами. При этом на его маршрут накладывается два ограничения:
· маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение;
· в каждом из городов коммивояжер должен побывать точно один раз, то есть надо обязательно обойти все города, при этом не побывав ни в одном городе дважды.
Для расчета затрат существует матрица условий, содержащая затраты на переход из каждого города в каждый, при этом считается, что можно перейти из любого города в любой, кроме того же самого (в матрице диагональ заполнена нулями). Целью решения является нахождения маршрута, удовлетворяющего всем условиям и при этом имеющего минимальную сумму затрат.
Метод решения
Вам будет интересно - Курсовая работа: Решения задач линейного программирования геометрическим методом
Для начала следует сказать, что в основе любого метода решения данной задачи лежит полный перебор всевозможных вариантов путей. [2]
Мы проходимся по каждому маршруту: одни отбрасываем, другие сравниваем с минимальным путем. В конце перебора мы получаем кратчайший путь.
Особенностью этой задачи является то, что с увеличением количества городов растет общее число различных комбинаций прохождения пути. А вместе с тем растет и время расчета результата. Поэтому главным решением оптимизации алгоритма можно свести к тому, чтобы во время вычислений отбрасывать заведомо не минимальные пути. Необходимо задать такой критерий, который отсекал бы лишние ветви в дереве поиска кратчайшего пути.
Для пояснения моего варианта решения задачи следует ввести несколько понятий. Промежуточную длину пути можно определить следующим образом: представим, что торговец выбрал какой-либо путь; он вышел из первого города и сейчас находится в каком-то городе i . Тогда все пройденное расстояние из начала в город i будем называть промежуточная длина пути. Если исходить из того, что торговец в каждый момент времени будет находиться в каком-то i -ом городе, то всегда можно подсчитать какое расстояние он прошел из начала до этого города, то есть промежуточную длину пути.
Минимальным путем будем называть маршрут, проходящий по всем городам и имеющий минимальную длину.
Мой критерий строится на одном простом утверждении: если промежуточная длина пути больше минимального пути, тогда очевидно следующее:
Похожий материал - Дипломная работа: Решения задачи планирования производства симплекс методом
1. промежуточная длина будет расти, когда торговец будет двигаться к конечному городу,
2. а значит длина всего пути будет больше длины минимального маршрута.
следовательно такой маршрут можно отбросить.
Пояснения показаны на рисунке 1.