Читать курсовая по финансовому менеджменту, финансовой математике: "Решение задачи о коммивояжере" Страница 2

(Назад) (Cкачать работу)

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

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

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

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

40

30

28

14

32

1

2

3

5

4

1

Промежуточная длина пути = 102

18

27

30

10

15

1

5

2

4

3

1

i = 4

100

Минимальный путь

Текущий путь

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

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

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

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

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

Для каждого города (i = от 1 до n), где мы еще не были.Допустим, что мы пришли в какой-то город i. Помечаем его, что мы здесь уже были. Подсчитываем длину пройденного пути. Если она больше чем длина минимального пути,

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

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

Иначе,

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

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

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

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

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

Похожие работы