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

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

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

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 мы были, тогда берем следующий не посещенный город – четвертый.

Д) Ставим на третье место маршрута четвертый город. Из четвертого пункта можно посетить только третий.

Е) Пришли в третий пункт. Ставим на четвертое место маршрута город 3. Видим, что все четыре места в нашем пути заполнены и значит путь закончен. Сравниваем длину нашего пути с минимальным. Выходим назад – из пункта 3 в пункт 4 и в маршруте перемещаемся на третье место. Видим что здесь тоже нет не посещенных городов. Опять переходим на уровень вверх: из пункта 4 в пункт2 и в маршруте перемещаемся на второе место. В пункте 2 мы были, но остались не посещенными города 3 и 4. Переходим в третий. На второе место в маршруте записываем третий город.

Ж) Отсюда можно попасть во второй и четвертый. Переходим во второй. На третье место в маршруте ставим второй город. И так далее.

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

0. Начальное значение j = 1 (первое место в маршруте).

1. Мы находимся в городе k.

2. Для каждого города (i = от 1 до n)

3. Рассматриваем город i.