Курсовая работа: Решение задачи о коммивояжере

Задача о коммивояжере состоит в том, чтобы объехать заданные города по одному разу в таком порядке, чтобы пройденное расстояние было минимальным.

Такая задача актуальна во многих областях, таких как автомобильные, судовые и железнодорожные перевозки, расчет авиационных линий, конвейерное производство.


Оглавление

Введение3

Постановка задачи4

Метод решения5

Возможно вы искали - Курсовая работа: Решение оптимизационных управленческих задач на основе методов и моделей линейного программирования

Язык программирования7

Описание алгоритма8

Описание основных структур данных12

Описание интерфейса с пользователем14

Заключение16

Похожий материал - Курсовая работа: Решение транспортной задачи с правильным балансом

Литература17

Текст программы18

Введение

Задача состоит в том, чтобы коммивояжер (торговец) обошел все намеченные города единожды и в таком порядке, чтобы его путь был наименьшим.

Эта задача заинтересовала меня потому, что её решение интересно с точки зрения программирования и составления алгоритма. Важно нахождение такого алгоритма, который позволит наиболее оптимально решить задачу.

Сейчас решение данной задачи необходимо во многих областях связанных с замкнутыми и при этом жестко связанными по времени системами, такими как: конвейерное производство, многооперационные обрабатывающие комплексы, судовые и железнодорожные погрузочные системы, перевозки грузов по замкнутому маршруту, расчет авиационных линий.

Очень интересно - Курсовая работа: Решение транспортных задач

Поэтому данная проблема на современном этапе развития общества имеет не самое последнее по значимости место.

Постановка задачи

Имеется N городов, которые должен обойти коммивояжер с минимальными затратами. При этом на его маршрут накладывается два ограничения:

· маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение;

· в каждом из городов коммивояжер должен побывать точно один раз, то есть надо обязательно обойти все города, при этом не побывав ни в одном городе дважды.

Для расчета затрат существует матрица условий, содержащая затраты на переход из каждого города в каждый, при этом считается, что можно перейти из любого города в любой, кроме того же самого (в матрице диагональ заполнена нулями). Целью решения является нахождения маршрута, удовлетворяющего всем условиям и при этом имеющего минимальную сумму затрат.

Метод решения

Вам будет интересно - Курсовая работа: Решения задач линейного программирования геометрическим методом

Для начала следует сказать, что в основе любого метода решения данной задачи лежит полный перебор всевозможных вариантов путей. [2]
Мы проходимся по каждому маршруту: одни отбрасываем, другие сравниваем с минимальным путем. В конце перебора мы получаем кратчайший путь.

Особенностью этой задачи является то, что с увеличением количества городов растет общее число различных комбинаций прохождения пути. А вместе с тем растет и время расчета результата. Поэтому главным решением оптимизации алгоритма можно свести к тому, чтобы во время вычислений отбрасывать заведомо не минимальные пути. Необходимо задать такой критерий, который отсекал бы лишние ветви в дереве поиска кратчайшего пути.

Для пояснения моего варианта решения задачи следует ввести несколько понятий. Промежуточную длину пути можно определить следующим образом: представим, что торговец выбрал какой-либо путь; он вышел из первого города и сейчас находится в каком-то городе i . Тогда все пройденное расстояние из начала в город i будем называть промежуточная длина пути. Если исходить из того, что торговец в каждый момент времени будет находиться в каком-то i -ом городе, то всегда можно подсчитать какое расстояние он прошел из начала до этого города, то есть промежуточную длину пути.

Минимальным путем будем называть маршрут, проходящий по всем городам и имеющий минимальную длину.

Мой критерий строится на одном простом утверждении: если промежуточная длина пути больше минимального пути, тогда очевидно следующее:

Похожий материал - Дипломная работа: Решения задачи планирования производства симплекс методом

1. промежуточная длина будет расти, когда торговец будет двигаться к конечному городу,

2. а значит длина всего пути будет больше длины минимального маршрута.

следовательно такой маршрут можно отбросить.

Пояснения показаны на рисунке 1.