Реализация алгоритма решения задачи коммивояжера в среде С++
Автор: Пользователь скрыл имя, 15 Января 2013 в 18:03, курсовая работа
Описание работы
Данная работа ставит целью исследование фундаментального алгоритма задачи коммивояжера, а также реализацию алгоритма задачи с помощью программы Visual C++ в целях упрощения поиска решения.
Содержание
Введение 3
1 Теоретические основы задачи о коммивояжере 4
1.1 Основные понятия теории графов, используемые при постановке транс-
портных и сетевых задач . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Формулировка и некоторые свойства решений задачи коммивояжера в
матричной постановке и не языке теории графов . . . . . . . . . . . . . .6
1.3 Решение задачи коммивояжера методом ветвей и границ . . . . . . . . .8
1.4 Пример решения задачи коммивояжера методом ветвей и границ . . . . 9
2 Руководство пользователя по работе с программой Voyager 14
2.1 Особенности работы с программой . . . . . . . . . . . . . . . . . . . . .14
2.2 Код программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16
2.3 Описание кода программы . . . . . . . . . . . . . . . . . . . . . . . . . . .18
Заключение 19
Список литературы 20
Работа содержит 1 файл
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ЭКОНОМИЧЕСКИЙ ФАКУЛЬТЕТ
КАФЕДРА ЭКОНОМИЧЕСКОЙ КИБЕРНЕТИКИ
Курсовая работа по исследованию операций
на тему: Реализация алгоритма решения задачи
коммивояжера в среде С++
Выполнила:
студентка 2 курса
специальности
Математические
методы в экономике
Мацюк Юлия Геннадиевна
Научный руководитель:
к. э. н., ст. преподаватель
Малова Александра Сергеевна
Оценка
Санкт-Петербург
2011 г.
Содержание
Введение
3
1 Теоретические основы задачи о коммивояжере
4
1.1 Основные понятия теории графов, используемые при постановке транс-
портных и сетевых задач . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.2 Формулировка и некоторые свойства решений задачи коммивояжера в
матричной постановке и не языке теории графов . . . . . . . . . . . . . .
6
1.3 Решение задачи коммивояжера методом ветвей и границ . . . . . . . . .
8
1.4 Пример решения задачи коммивояжера методом ветвей и границ . . . . .
9
2 Руководство пользователя по работе с программой Voyager
14
2.1 Особенности работы с программой . . . . . . . . . . . . . . . . . . . . . .
14
2.2 Код программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
2.3 Описание кода программы . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
Заключение
19
Список литературы
20
2
Введение
Ввиду возросшей в последние десятилетия важности понятия "экономический
человек"и вследствие того, что доля населения, занимающегося экономической дея-
тельностью и предпринимательством, неуклонно растет, очень большой интерес для
современных специалистов представляют оптимизационные задачи. В связи с тем, что
одним из фундаментальных признаков экономики является рациональность деятельно-
сти, зачастую представляется необходимым найти оптимальный путь и оптимальную
стоимость переезда. Это может быть применимо, например, для мелких и крупных
предприятий, занимающихся перевозками, а также к различного рода логистическим
задачам.
Так, в 1984 году после тщательного анализа временных затрат на операции на
конвейерах заводов компании General Motors, были приняты рекомендованные меры,
благодаря которым удалось увеличить общую производительность почти на 13 процен-
тов при неизменном числе рабочих и том же оборудовании. Для проведения расчетов
были использованы компьютеры IBM 360gr, одни из самых производительных систем в
мире на то время. Операция расчета и оптимизации 287 операций, включающих в себя
200 основных и 87 вспомогательных, занял около 230 часов. Именно так впервые были
применены коммерческие компьютерные технологии в области управления производ-
ством в целом.
С решением подобных оптимизационных задач может столкнуться любой спе-
циалист среднего звена. Производственный процесс требует решения задач различных
задач с учетом некоторого количества ограничений, запрещающих начало решения од-
ной задачи до тех пор, пока не будет завершено решение предыдущей. К подобным
задачам относится задача составления расписаний, целью которой является построе-
ние временного графика решения задач таким образом, чтобы удовлетворить заданным
ограничениям и завершить данный процесс за минимально возможное время.
Сейчас решение данной задачи необходимо во многих областях связанных с за-
мкнутыми и при этом жестко связанными по времени системами, такими как: конвейер-
ное производство, многооперационные обрабатывающие комплексы, судовые и желез-
нодорожные погрузочные системы, перевозки грузов по замкнутому маршруту, расчет
авиационных линий [2].
Данная работа ставит целью исследование фундаментального алгоритма задачи
коммивояжера, а также реализацию алгоритма задачи с помощью программы Visual
C++ в целях упрощения поиска решения.
3
1. Теоретические основы задачи о коммивояжере
В данном разделе рассматриваются теоретические основы задачи о коммивоя-
жере и содержится пример решения задачи коммивояжера методом ветвей и границ.
1.1. Основные понятия теории графов, используемые при поста-
новке транспортных и сетевых задач
Неориентированным графом будем называть тройку (D, I, G), в которой I -
непустое множество вершин, D - множество ребер, а G - отображение, которое каждому
ребру d ∈ D ставит в соответствие неупорядоченную пару вершин (i,j), где i,j ∈ I [1].
Пусть имеется неориентированный граф. Геометрически граф можно предста-
вить как набор вершин (точек), определенные пары которых соединены линиями. На-
пример, сеть трасс, соединяющих пункты E
1
,E
2
,E
3
,E
4
,E
5
можно представить в виде
графа. При этом пункты обозначим точками (вершинами), а трассы - неориентирован-
ными линиями (рис.1).
Рис. 1:
Неориентированная линия предполагает наличие двустороннего движения меж-
ду соединяемой ей парой пунктов. Пересечения линий при этом за вершины не счита-
ются.
При изображении графа не имеет значение расположение вершин на плоскости,
кривизна и длина ребер (рис. 2) [5].
Рис. 2:
4
Вершины графов обозначаются буквами или натуральными числами. Ребра гра-
фа - пары чисел. Так, ребро, соединяющее пункты E
1
и E
2
, будем обозначать (E
1
,E
2
).
Графические представления представляют собой наглядные отображения иссле-
дуемой системы процесса или явления на плоскость. Это могут быть рисунки, черте-
жи, схемы и блок-схемы, диаграммы, графы. На языке теории графов формируются и
решаются многие технические задачи, задачи из области экономики, социологии, ме-
неджмента и т.д. Графы используются для наглядного представления объектов и связи
между ними.
Маршрутом в неориентированном графе называется такая конечная или беско-
нечная последовательность ребер, что каждые два соседних ребра имеют концевую
точку. Причем одно и то же ребро Е может встречаться в маршруте несколько раз.
Циклическим маршрутом называется такой маршрут, начальная и конечная точ-
ки которого совпадают.
Цепью называют маршрут, в котором каждое его ребро встречается не более
одного раза; вершины в цепи могут повторяться не более одного раза. Любой участок
цепи является цепью. Нециклическая цепь является простой цепью, если в ней никакая
вершина не повторяется.
Граф называется сильно связным, если между каждой парой его вершин E
i
, E
j
∈ E,E
i
= E
j
существует путь (e
1
,e
2
...e
m
) такой, что является начальной вершиной
пути, а E
j
- конечной [1].
5
1.2. Формулировка и некоторые свойства решений задачи ком-
мивояжера в матричной постановке и не языке теории гра-
фов
Рассмотрим классическую постановку задачи о коммивояжере: имеется N го-
родов - пунктов посещения; выезжая из исходного города A
1
, коммивояжер должен
побывать во всех городах по одному разу и вернуться в исходный пункт. Смысл за-
дачи коммивояжера заключается в том, чтобы определить такую последовательность
посещения пунктов назначения, которая смогла бы обеспечить минимальную стоимость
проезда. В различных вариациях задачи вместо последней может потребоваться мини-
мизация пройденного расстояния или времени переезда.
Для расчета стоимостей перехода используется матрица условий, содержащая
затраты на переезд из одного пункта в другой.
Пусть города пронумерованы числами j ∈ T = (1,2,3... n). Тур коммивояжера
может быть описан следующей перестановкой t = (j
1
,j
2
... j
n
,j
1
), причём все j
1
... j
n
-
разные номера. Повторяющийся в начале и в конце j
1
, показывает, что мы имеем дело
с циклом. Расстояния между парами вершин C
ij
образуют матрицу затрат С. Задача
состоит в том, чтобы найти такой тур t, чтобы минимизировать функционал
L = L(t) =
n
∑
k=1
C
j
k
j
k+1
Относительно математической формулировки задачи коммивояжера уместно сде-
лать два замечания.
Во-первых, в постановке обозначают цены переездов, поэтому они должны быть
неотрицательными:
∀j ∈ T : C
ij
≥ 0;C
ij
= ∞),
(1.1)
а также симметричными:
∀i,j : C
ij
= C
ji
(1.2)
и удовлетворять неравенству треугольника:
∀i,j : C
ij
+ C
jk
≥ C
ik
(1.3)
При этом равенство C
ij
≥ 0;C
jj
= ∞ трактуется как запрет на петли в туре.
Если пункты поставить в соответствие вершинам неориентированного графа, а
соединяющим пункты трассам - дуги, то в терминах теории графов задачу можно опре-
делить как поиск гамильтонова контура наименьшей длины.
Гамильтоновым контуром будем называть путь, проходящий через все вершины
графа, начальная вершина которого совпадает с конечной, а длина контура определя-
ется суммой длин всех дуг, входящих в контур.
6
Таким образом, для решения задачи представляется необходимым построить
кольцевой маршрут проезда всех пунктов, который имел бы минимальную длину, на-
чиная с любого пункта и в любую сторону [4].
Если мы имеем в общей сложности n пунктов, а коммивояжер, выехав из на-
чального пункта, должен побывать в остальных (n-1) пунктах только единожды, то
существует всего (n-1)! возможных маршрутов, среди которых один или несколько -
оптимальные.
В силу (1.1) стоимость перехода из пункта i в пункт j является симметричным
и равно цене перевозки из j в i.
Маршрут можно представить в виде замкнутого контура, представляющего со-
бой кольцевой маршрут.
7
1.3. Решение задачи коммивояжера методом ветвей и границ
Алгоритм решения задачи коммивояжера методом ветвей и границ был предло-
жен Литтлом, Мурти, Суини и Керелом во второй половине XX века. Основная идея
метода достаточно тривиальна и заключается в полном переборе решений, который в
силу отсечения в процессе решения неоптимальных множеств перебора приходит к оп-
тимальному варианту. Для того, чтобы отбросить неоптимальные варианты, мы дробим
некоторое число рассматриваемых вариантов на классы и получить оценки для этих
классов (получаем оценки снизу, так как имеем дело в задачей минимизации). Это поз-
волит получить возможность отбрасывать варианты не по одному, а целыми классами
что значительно облегчит выполнение задачи.
Трудность состоит в том, чтобы найти такое разделение на классы (ветви) и
такие оценки (границы), чтобы процедура была эффективной.
C
ij
будем трактовать как стоимость проезда из пункта i в пункт j. Представим,
что при въезде в пункт j коммивояжеру выплачивается 5 евро. Соответственно, любой
тур подешевеет на 5 евро, так как в любом туре нужно въехать в пункт j. И поскольку
подешевели все туры на фиксированную величину, то прежний минимальный по сто-
имости тур и теперь останется минимальным. Алгебраически подешевение всех туров
можно представить как уменьшение всех чисел j-ого столбца матрицы стоимостей на
5.
Представим себе обратную ситуацию - пусть при выезде из пункта j коммивоя-
жеру выплачивается 8 евро. Алгебраически это означает вычитание 8 из каждого эле-
мента j-ой строки. Как и в предыдущей ситуации, заданное условие меняет стоимость
каждого тура, но минимальный тур по-прежнему остается минимальным.
Таким образом, вычитая любую константу из всех элементов любой строки или
столбца матрицы цен, мы оставляем минимальный тур минимальным. Для упрощения
расчетов при применении алгоритма удобнее будет получить как можно большее ко-
личество нулей в С, не получая там, однако, отрицательных чисел. Для этого сначала
из каждой строки вычитается ее минимальный элемент, т.е. матрица приводится по
строкам. Приведенную по строкам матрицу затем приводим по столбцам.
Метод ветвей и границ - это один из методов организации полного перебора. Он
применим не всегда, а только тогда, когда выполняются специфические дополнитель-
ные условия на множество M и минимизируемую на нем функцию.
8
1.4. Пример решения задачи коммивояжера методом ветвей и
границ
Рассмотрим пример решения задачи коммивояжера размерностью 6х6:
C
ij
=
∞ 68 73 24 70 9
58 ∞ 16 44 11 92
64 9 ∞ 86 13 18
17 34 76 ∞ 52 70
60 18 3 45 ∞ 58
16 82 11 60 48 ∞
Приведем исходную матрицу по строкам:
C
ij
=
∞ 59 64 15 61 0
47 ∞ 5 33 0 81
55 0 ∞ 77 4
9
0 17 59 ∞ 35 53
57 15 0 42 ∞ 55
5 71 0 49 37 ∞
Приведем матрицу по столбцам:
C
ij
=
∞ 59 64 0 61 0
47 ∞ 5 18 0 81
55 0 ∞ 62 4
9
0 17 59 ∞ 35 53
57 15 0 27 ∞ 55
5 71 0 34 37 ∞
После этих операций мы можем посчитать начальную приведенную стоимость
W
0
, сложив значения всех вычтенных построчно и по столбцам минимальных элемен-
тов.
W
0
= 9 + 11 + 9 + 17 + 3 + 11 + 15 = 75;
Разобъем все множество маршрутов на два подмножества:
В случае под левой стрелкой имеем:
C
1
=
59 64 ∞ 61 0
∞ 5 18 0 81
0 ∞ 62 4
9
15 0 27 ∞ 55
71 0 34 37 ∞
9
Рис. 3: Разбиение D на подмножества 1
Приведем эту матрицу по строкам и по столбцам:
C
1
=
59 64 ∞ 61 0
∞ 5
0
0 81
0 ∞ 44 4
9
15 0
9 ∞ 55
71 0 16 37 ∞
Посчитаем приведенную стоимость: W
1
= W
0
+ 18 = 93.
В случае под правой стрелкой получаем матрицу:
C
1
=
∞ 59 64 0 61 0
47 ∞ 5 18 0 81
55 0 ∞ 62 4
9
∞ 17 59 ∞ 35 53
57 15 0 27 ∞ 55
5 71 0 34 37 ∞
Приведем матрицу по столбцам и по строкам:
C
1
=
∞ 59 64 0 61 0
42 ∞ 5 18 0 81
50 0 ∞ 62 4
9
∞ 0 42 ∞ 18 36
52 15 0 27 ∞ 55
0 71 0 34 37 ∞
Рассчитаем приведенную стоимость для этого случая: W
1
= W
0
+ 17 + 5 = 97.
Очевидно, что W
1
= 93 < 97, а значит в качестве отправной точки маршрута
целесообразно выбрать пункт (4;1) и работать дальше будем с матрицей затрат для
этого маршрута.
Разобъем подмножество под левой стрелкой на еще одно подмножество:
10
Рис. 4: Разбиение D на подмножества 2
Следуя рекомендациям {(4;1)(1;6)//(1;4)(6;1)} имеем:
C
2
=
∞ 5
0
0
0 ∞ 44 4
15 0
9 ∞
∞ 0 16 37
Нетрудно заметить, что приводить эту матрицу не придется, а значит, приведен-
ная стоимость W
2
= W
1
= 93.
В обратном случае получим:
C
2
=
59 64 ∞ 51 ∞
∞ 5
0
0 81
0 ∞ 44 4
9
15 0
9 ∞ 55
71 0 16 37 ∞
Приведенная матрица будет выглядеть следующим образом:
C
2
=
8 13 ∞ 0 ∞
∞ 5
0
0 72
0 ∞ 44 4
0
15 0
9 ∞ 46
71 0 16 37 ∞
Приведенная стоимость W
2
= W
1
+ 51 + 9 = 153 > 93, следовательно, будем
следовать маршруту 6 → 1 → 4. Дробим подмножество {(4;1)(1;6)//(1;4)(6;1)} на еще
2 подмножества:
В первом случае матрица затрат примет вид:
11
Рис. 5: Разбиение D на подмножества 3
C
3
=
∞ 0
0
0 44 4
15 9 ∞
Приведем матрицу по строкам и по столбцам:
C
3
=
∞ 0
0
0 44 4
6
0 ∞
Приведенная стоимость W
3
= W
2
+ 9 = 102.
В ином случае:
C
3
=
8 13 ∞ 0 ∞
∞ 5
0
0 72
0 ∞ 44 4
0
15 0
9 ∞ 46
71 ∞ 16 37 ∞
Приведем матрицу и рассчитаем W
3
для этого случая:
12
C
3
=
8 13 ∞ 0 ∞
∞ 5
0
0 72
0 ∞ 44 4
0
15 0
9 ∞ 46
55 ∞ 0 21 ∞
Заметим, что W
3
= W
2
+ 16 = 109 > 102. Очевидно, что работать дальше целе-
сообразно с матрицей C
3
.
Повторяем роцедуру дробления на подмножества, приведем и рассчитаем при-
веденную стоимость для маршрута (3;2):
C
4
=
(
0 0
0 ∞
)
При этом W
4
= W
3
= 102.
Для маршрута, запрещающего передвижение (3;2)
C
4
=
∞ 0
0
∞ 44 4
6
0 ∞
приведенная матрица выглядит следующим образом:
C
4
=
∞ 0
0
∞ 40 0
0
0 ∞
,
а приведенная стоимость примет значение W
4
= W
3
+ 4 + 6 = 112 > 102. Следуя
алгоритму, включаем передвижение (3;2) в маршрут коммивояжера.
Продолжим разбиение:
C
5
= (0)
Тогда оптимальный путь коммивояжера будет иметь вид: 1 → 6 → 3 → 2 → 5 →
4, а наименьшая стоимость переезда W = 102.
13
2. Руководство пользователя по работе с программой
Voyager
В данном разделе описывается описание программы Voyager, реализующая ал-
горитм решения задачи коммивояжера методом ветвей и границ.
2.1. Особенности работы с программой
Для работы с программой изначально создана txt - файл, в котором необходи-
мо задать размер матрицы и саму матрицу затрат. Для этого открываем файл под
названием input с помощью WordPad:
Рис. 6: Введите размерность матрицы и саму матрицу затрат
Цифра в левом верхнем угла задает размерность матрицы. Программа рассчи-
тана на решение задач размерностью до ста. Для введения элементов матрицы нужно
пользоваться клавишей пробел или обычной табуляцией. Вместо знака бесконечность
на главной диагонали записаны нули.
Цифра в левом верхнем угла задает размерность матрицы. Программа рассчи-
тана на решение задач размерностью до ста. Для введения элементов матрицы нужно
пользоваться клавишей пробел или обычной табуляцией. Вместо знака бесконечность
на главной диагонали записаны нули.
14
Чтобы получить решение программы, нужно открыть приложение win-voyager.
Приложение выдаст решение задачи в следующем виде:
Рис. 7: Результат работы программы
Верхняя строчка определяет значение минимальных затрат на осуществление
оптимального пути. Строчкой ниже описан сам оптимальный путь.
15
2.2. Код программы
include <iostream>
include <fstream>
using namespace std;
const int maxn=100;
int size,i,current-sum,min-path,count,found,a[maxn][maxn],m[maxn],minm[maxn];
void input();
void output();
void search(int);
int main()
input();
current-sum=0;
found=0;
min-path=32767;
for (int i=1;i<=size;i++)
m[i]=0;
count=1;
m[1]=count;
search(1);
output();
cin.get();
return 0;
void input()
ifstream fin("input.txt");
fin size; //читаем из файла размер графа
for (int i=1;i<=size;i++)
for (int j=1;j<=size;j++)
fin a[i][j]; //читаем по элементам матрицу расстояний
void output()
if (found)
cout "Minimum cost is
≪
< min-path endl;
cout "Path is: ";
int number=1;
for (int i=1;i<=size;i++)
int j=1;
while (j<=size minm[j]!=number)
j++;
16
cout j >";
number++;
cout minm[1] endl;
else cout "Path not found!";
void search(int start)
if (count==size a[start][1]!=0 current-sum+a[start][1]<min-path) //если просмот-
рели все города, из последнего города есть путь в первый город и новая сумма рассто-
яний меньше минимальной суммы
found=1;
min-path=current-sum+a[start][1];
for (int i=1;i<=size;i++)
minm[i]=m[i];
else
for (int i=1;i<=size;i++) //из текущего города просматриваем все города
if (i!=start a[start][i]!=0 m[i]==0 current-sum+a[start][i]<min-path)
current-sum+=a[start][i];
count++;
m[i]=count;
search(i);
m[i]=0;
count–;
current-sum-=a[start][i];
17
2.3. Описание кода программы
Для начала пишем "шапку"программы: подключаем стандартную библиотеку
ввода-вывода (include <iostream>), добавляем к ней вспомогательную библиотеку для
некоторых классов include <fstream>, а также строчку, сообщающую программе о том,
что мы будем использовать стандартное пространство имен - using namespace std.
Затем задаем максимальную размерность матрицы и вводим переменные с огра-
ничением целостности для размерности матрицы, элементов матрицы, наименьшей при-
веденной стоимости.
Структура void означает, что мы не задаем тип возвращаемого значения для
метода. В самом коде void input() - это функция ввода матрицы, void output() - функция
вывода результата, а void search(int) - это функция поиска следующего элемента.
Сначала минимальный путь принимаем за бесконечность (min-path = 32767) и
решаем задачу для этого параметра. Изначально примем число пройденных городов за
единицу, а потом начнем движение, т.е. выйдем из первого города.
Затем читаем из текстового файла размер графа и элементы матрицы. Стан-
дартным потоком вывода cout задаем конечный результам, который хотим получить:
программа выведет на экран "Minimum cost is:"и посчитает наименьшую стоимость
перевозки, а также "Path is: представив маршрут в виде: 1 → 2 → 3.
Цикл for выполняет определенное количество повторов, состоит из трех частей:
инициализатор (int i=1), который фиксирует значение переменной, условие выхода
(i<=size), т.е. цикл будет прекрацен, как только i станет больше размерности матри-
цы, а также условие изменения (i++). Последнее означает, что i в цикле каждый раз
увеличивается на единицу. В нашем случае if(count == sizea[start][1]! = 0current −
sum + a[start][1] < min − path) будет означать ,что если мы просмотрели все горо-
да, и из последнего города есть путь в первый город, и новая сумма перехода меньше
минимальной суммы, то путь найден. Тогда к текущей длине пути добавляем путь из
последнего города в первый, сохраняем минимальный путь.
Если путь еще не найден, то из текущего города просматриваем все города. Тогда
if(i! = starta[start][i]! = 0m[i] == 0current − sum + a[start][i] < min − path) будет
означать, что если новый город не совпадает с рассматриваемым, если путь из текущего
города в новый существует и он еще не рассмотрен и текущая сумма затрат на переход
не превышает минимальной, то мы увеличиваем текущую сумму, увеличиваем число
рассматриваемых городов. Затем включаем в порядок обхода текущий город, начинаем
поиск с i-ого города.
18
Заключение
Данная курсовая работа посвящена программной реализации задачи коммиво-
яжера на языке программирования C++ метода ветвей и границ. В результате про-
деланной работы изучен алгоритм данного метода, получены навыки работы в среде
Visual C++ 2010 и текстовом редакторе L
A
T
E
X.
В качестве основного результата получена программа, позволяющая автомати-
зировать для экономиста поиск решения задачи коммивояжера произвольной размер-
ности.
19
Список литературы
[1] Конюховский П.В. Математические методы исследования операций в экономике.
СПб.: Издательство Питер, 2000.
[2] Седжвик Р. Фундаментальные алгоритмы на С.
М.: Изд-во DiaSoft, 2003.
[3] Керниган Б., Ритчи Д. Язык программирования С.
СПб.: Изд-во Невский Диа-
лект, 2003.
[4] Фомин Г.П. Математические методы и модели в коммерческой деятельности. Учеб-
ник.
М.: Изд-во Финансы и статистика, 2001.
[5] Вентцель Е.С. Исследование операций: задачи, принципы, методология.
М.: Выс-
шая школа, 2004.
20
Информация о работе Реализация алгоритма решения задачи коммивояжера в среде С++