Решение задачи о коммивояжере

Аннотация

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

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

Оглавление

Введение3

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

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

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

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

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

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

Заключение16

Литература17

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для написания программы был выбран язык Си++ по следующим причинам:

1. Среда программирования Windows-приложений Microsoft Visual C++ 6.0 позволяет в моей задаче наглядно отобразить карту городов и схему их соединения.

2. Это один из языков, в котором я неплохо разбираюсь. Поэтому мне удобнее писать программу с помощью Visual C++.

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

В программе содержится рекурсивная функция, которая обеспечивает перебор возможных путей для поиска самого короткого. Именно здесь заключен алгоритм решения задачи «коммивояжера». Рассмотрим его подробнее:

1. Для каждого города (i = от 1 до n), где мы еще не были.

2. Допустим, что мы пришли в какой-то город i. Помечаем его, что мы здесь уже были.

3. Подсчитываем длину пройденного пути.

4. Если она больше чем длина минимального пути,

4.1. Тогда нет смысла идти по этому пути дальше.

4.1.1. помечаем город как не посещенный, выходим из города.

4.2. Иначе,

4.2.1. если мы в конце пути

4.2.1.1. тогда, сравниваем с минимальным путем, если он меньше кратчайшего пути, тогда минимальный путь = кратчайший путь.

4.2.1.2. иначе переходим к пункту 1.

5. Переходим к следующему городу, где мы не были.

Следует рассмотреть один из основных моментов алгоритма, связанных с перебором маршрутов. Из рисунка №2 можно проследить порядок формирования путей и рассмотреть на конкретном примере, как работает алгоритм. Здесь приведен пример для 4 городов. Остановимся на рисунке по подробнее.

А) Мы начинаем путь из пункта 1. В нашем маршруте записан первый город. Рассматриваем те города, где мы не были: это 2, 3 и 4. Сначала переходим во второй.

Б) Добавляем к маршруту 2 город. Смотрим, можно ли куда-то перейти из второго города. Можно посетить третий и четвертый. Мы выбираем третий город.

В) Ставим на третье место в нашем маршруте город 3. Далее мы смотрим, куда можно отправиться – в пункт 4.

Г) На четвертое место в маршруте ставим город 4. Здесь мы видим, что в нашем маршруте заполнены все четыре места и значит наш путь закончен. Сравниваем длину нашего пути с минимальным. Затем мы выходим назад из пункта 4 в пункт 3 и в маршруте перемещаемся на третье место. Смотрим, что в городе 3 мы были, тогда берем следующий не посещенный город – четвертый.

 Скачать реферат