Решение задачи методом ветвей и границ
Введение
Каждый
человек ежедневно, не всегда
осознавая это, решает
Актуальность
темы: сейчас решение данной задачи
необходимо во многих областях
промышленности и народного
- Теоретическая часть
- Постановка задачи
Имеются n городов, расстояния (стоимость проезда, расход горючего на дорогу и т.д.) между которыми известны. Коммивояжер должен пройти все n городов по одному разу, вернувшись в тот город, с которого начал. Требуется найти такой маршрут движения, при котором суммарное пройденное расстояние (стоимость проезда и т.д.) будет минимальным.
Очевидно, что задача коммивояжера – это задача отыскания кратчайшего гамильтонова цикла в полном графе.
Существует метод решения задачи коммивояжера, который дает оптимальное решение. Этот метод называется методом ветвей и границ. Решение задачи коммивояжера методом ветвей и границ по-другому называют алгоритмом Литтла.
1.2 Описание метода
Для практической реализации идеи метода ветвей и границ применительно к задаче коммивояжера нужно найти метод определения нижних границ подмножества и разбиения множества гамильтоновых контуров на подмножества (ветвление).
Определение нижних
границ базируется на том
Опишем алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Граф представляют в виде матрицы его дуг. Если между вершинами Xi и Xj нет дуги, то ставится символ «∞».
Алгоритм Литтла для решения задачи коммивояжера можно сформулировать в виде следующих правил:
1. Находим в каждой строке матрицы минимальный элемент и вычитаем его из всех элементов соответствующей строки. Получим матрицу, приведенную по строкам, с элементами
2. Если в матрице , приведенной по строкам, окажутся столбцы, не содержащие нуля, то приводим ее по столбцам. Для этого в каждом столбце матрицы выбираем минимальный элемент , и вычитаем его из всех элементов соответствующего столбца. Получим матрицу
каждая строка и столбец, которой содержит хотя бы один нуль. Такая матрица называется приведенной по строкам и столбцам.
3. Суммируем элементы и , получим константу приведения
которая будет нижней границей множества всех допустимых гамильтоновых контуров, то есть
4. Находим степени нулей
для приведенной по строкам
и столбцам матрицы. Для этого
мысленно нули в матице
5. Выбираем дугу , для которой степень нулевого элемента достигает максимального значения
6. Разбиваем множество всех гамильтоновых контуров на два подмножества и . Подмножество гамильтоновых контуров содержит дугу , - ее не содержит. Для получения матрицы контуров , включающих дугу , вычеркиваем в матрице строку и столбец . Чтобы не допустить образования негамильтонова контура, заменим симметричный элемент на знак «∞».
7. Приводим матрицу
8. Находим множество
9. Делаем приведение матрицы гамильтоновых контуров . Пусть - константа ее приведения. Нижняя граница множества определится так:
10. Сравниваем нижние границы
подмножества гамильтоновых
Процесс разбиения множеств на подмножества сопровождается построением дерева ветвлений.
11. Если в результате ветвлений получаем матрицу , то определяем полученный ветвлением гамильтонов контур и его длину.
12. Сравниваем длину гамильтонова
контура с нижними границами
оборванных ветвей. Если длина
контура не превышает их
1.3 Математическая модель задачи коммивояжера
Задача коммивояжера может быть сформулирована как целочисленная введением булевых переменных , если маршрут включает переезд из города i непосредственно в город j и в противном случае. Тогда можно задать математическую модель задачи, то есть записать целевую функцию и систему ограничений:
(1)
Условия (2) – (4) в совокупности обеспечивают, что каждая переменная равна или нулю, или единице. При этом ограничения (2), (3) выражают условия, что коммивояжер побывает в каждом городе один раз в него прибыв (ограничение (2)), и один раз из него выехав (ограничение (3)).
Однако этих ограничений не достаточно для постановки задачи коммивояжера, так как они не исключают решения, где вместо простого цикла, проходящего через n вершин, отыскиваются 2 и более отдельных цикла (подцикла), проходящего через меньшее число вершин. Поэтому задача, описанная уравнениями (2) – (4) должна быть дополнена ограничениями, обеспечивающими связность искомого цикла.
Для того, чтобы исключить при постановке задачи все возможные подциклы в систему ограничений задачи включают следующее ограничение:
1.4 Алгоритм решения
Дана матрица расстояний, представленная в таблице 1. Необходимо с помощью алгоритма Литтла решить задачу коммивояжера.
Табл.1
j i |
1 |
2 |
3 |
4 |
5 |
6 |
1 |
∞ |
7 |
16 |
21 |
2 |
17 |
2 |
13 |
∞ |
21 |
15 |
43 |
23 |
3 |
25 |
3 |
∞ |
31 |
17 |
9 |
4 |
13 |
10 |
27 |
∞ |
33 |
12 |
5 |
9 |
2 |
19 |
14 |
∞ |
51 |
6 |
42 |
17 |
5 |
9 |
23 |
∞ |
1) Справа к таблице присоединяем столбец Ui, в котором записываем минимальные элементы соответствующих строк. Вычитаем элементы Ui из соответствующих элементов строки матрицы.
j i |
1 |
2 |
3 |
4 |
5 |
6 |
Ui |
|
1 |
∞ |
7 |
16 |
21 |
2 |
17 |
2 |
2 |
13 |
∞ |
21 |
15 |
43 |
23 |
13 |
3 |
25 |
3 |
∞ |
31 |
17 |
9 |
3 |
4 |
13 |
10 |
27 |
∞ |
33 |
12 |
10 |
5 |
9 |
2 |
19 |
14 |
∞ |
51 |
2 |
6 |
42 |
17 |
5 |
9 |
23 |
∞ |
5 |
2) Внизу полученной матрицы присоединяем строку Vj, в которой записываем минимальные элементы столбцов. Вычитаем элементы Vj из соответствующих столбцов матрицы.
j i |
1 |
2 |
3 |
4 |
5 |
6 |
1 |
∞ |
5 |
14 |
19 |
0 |
15 |
2 |
0 |
∞ |
8 |
2 |
30 |
10 |
3 |
22 |
0 |
∞ |
28 |
14 |
6 |
4 |
3 |
0 |
17 |
∞ |
23 |
2 |
5 |
7 |
0 |
17 |
12 |
∞ |
49 |
6 |
37 |
12 |
0 |
4 |
18 |
∞ |
Vj |
0 |
0 |
0 |
2 |
0 |
2 |
3) В результате вычислений получаем матрицу, приведенную по строкам и столбцам, которая изображена в виде таблицы 2.
Табл.2
j i |
1 |
2 |
3 |
4 |
5 |
6 |
1 |
∞ |
5 |
14 |
17 |
019 |
13 |
2 |
03 |
∞ |
8 |
02 |
30 |
8 |
3 |
22 |
04 |
∞ |
26 |
14 |
4 |
4 |
3 |
00 |
17 |
∞ |
23 |
04 |
|
5 |
7 |
07 |
17 |
10 |
∞ |
47 |
6 |
37 |
12 |
08 |
2 |
18 |
∞ |
4) Находим константу приведения:
Таким образом, нижней границей множества всех гамильтоновых контуров будет число .
5) Находим степени нулей
полностью приведенной матрицы.
6) Определяем максимальную
степень нуля. Она равна 19 и
соответствует клетке (1;5). Таким
образом, претендентом на
7) Разбиваем множество всех гамильтоновых контуров на два: и . Матрицу с дугой (1;5) получаем табл.2 путем вычеркивания строки 1 и столбца 5. Чтобы не допускать образования негамильтонова контура, заменяем элемент (5;1) на знак «∞».
j i |
1 |
2 |
3 |
4 |
6 |
2 |
0 |
∞ |
8 |
0 |
8 |
3 |
22 |
0 |
∞ |
26 |
4 |
4 |
3 |
0 |
17 |
∞ |
0 |
5 |
∞ |
0 |
17 |
10 |
47 |
6 |
37 |
12 |
0 |
2 |
∞ |
8) Матрицу гамильтоновых контуров получим из таблицы 2 путем замены элемента (1;5) на знак «∞».
j i |
1 |
2 |
3 |
4 |
5 |
6 | |
1 |
∞ |
5 |
14 |
17 |
∞ |
13 |
5 |
2 |
0 |
∞ |
8 |
0 |
30 |
8 | |
3 |
22 |
0 |
∞ |
26 |
14 |
4 | |
4 |
3 |
0 |
17 |
∞ |
23 |
0 | |
5 |
7 |
0 |
17 |
10 |
∞ |
47 | |
6 |
37 |
12 |
0 |
2 |
18 |
∞ | |
14 |
9) Делаем дополнительное приведение матрицы контуров : = 0. Нижняя граница множества равна .
10) Находим константу приведения для множества контуров : . Следовательно, нижняя граница множества равна .
11) Сравниваем нижние границы подмножеств и . Так как , то дальнейшему ветвлению подвергаем множество .
На рис.1 представлено ветвление по дуге (1;5).
рис.1
Переходим к ветвлению подмножества . Его приведенная матрица представлена в таблице ниже.
j i |
1 |
2 |
3 |
4 |
6 |
2 |
03 |
∞ |
8 |
02 |
8 |
3 |
22 |
04 |
∞ |
26 |
4 |
4 |
3 |
00 |
17 |
∞ |
04 |
|
5 |
∞ |
010 |
17 |
10 |
47 |
6 |
37 |
12 |
010 |
2 |
∞ |
12) Узнаем степени нулей
матрицы. Претендентами на
Табл.3
j i |
1 |
2 |
4 |
6 |
2 |
0 |
∞ |
0 |
8 |
3 |
22 |
0 |
26 |
∞ |
4 |
3 |
0 |
∞ |
0 |
5 |
∞ |
0 |
10 |
47 |
Табл.4
j i |
1 |
2 |
3 |
4 |
6 | |
2 |
0 |
∞ |
8 |
0 |
8 | |
3 |
22 |
0 |
∞ |
26 |
4 | |
4 |
3 |
0 |
17 |
∞ |
0 | |
5 |
∞ |
0 |
17 |
10 |
47 | |
6 |
37 |
12 |
∞ |
2 |
∞ |
2 |
8 |
Определим константы приведения для этих матриц , . Следовательно, , . Так как , то дальнейшему ветвлению подлежит подмножество . Находим степени нулей матрицы.
j i |
1 |
2 |
4 |
6 |
2 |
03 |
∞ |
02 |
8 |
3 |
22 |
022 |
26 |
∞ |
4 |
3 |
00 |
∞ |
08 |
|
5 |
∞ |
010 |
10 |
47 |
Претендентом к включению в гамильтонов контур станет дуга (3;2). Разбиваем множество на два и .
j i |
1 |
4 |
6 | |
2 |
0 |
0 |
8 | |
4 |
3 |
∞ |
0 | |
5 |
∞ |
10 |
47 |
10 |
j i |
1 |
2 |
4 |
6 | |
2 |
0 |
∞ |
0 |
8 | |
3 |
22 |
∞ |
26 |
∞ |
22 |
4 |
3 |
0 |
∞ |
0 | |
5 |
∞ |
0 |
10 |
47 |
Очевидно, , . Следовательно, очередному ветвлению нужно подвергнуть подмножество .
Переходим к ветвлению подмножества . Его приведенная матрица представлена в таблице ниже.
j i |
1 |
4 |
6 |
2 |
03 |
00 |
8 |
4 |
3 |
∞ |
011 |
|
5 |
∞ |
037 |
37 |
Определяем степени нулей. Претендентом на включение в гамильтонов контур является дуга (5;4). Разбиваем множество на два подмножества: и .
j i |
1 |
6 |
2 |
0 |
8 |
4 |
3 |
0 |
j i |
1 |
4 |
6 | |
2 |
0 |
0 |
8 | |
4 |
3 |
∞ |
0 | |
5 |
∞ |
∞ |
37 |
37 |
Находим нижние границы , . Следовательно, очередному ветвлению нужно подвергнуть подмножество . Но его матрица имеет размерность . Поэтому в гамильтонов контур следует включить дуги, соответствующие в матрице нулевым элементам. Это дуги (2;1) и (4;6).
На рис.2 представлено дерево ветвлений. Определим полученный гамильтонов контур. В него вошли дуги . Длина контура равна . Так как границы оборванных ветвей больше длины контура 1 – 5 – 4 – 6 – 3 – 2 – 1, то этот контура имеет наименьшую длину.
рис.2
- Программная реализация
2.1 Разработка алгоритма
Для поиска самого короткого пути, в программе используется рекурсивная функция, которая обеспечивает перебор всех возможных путей в графе. Эта функция и реализует решение задачи коммивояжёра методом ветвей и границ.
- Допустим, что мы пришли в какой-то город i. Помечаем его, что мы здесь уже были.
- Подсчитываем длину пройденного пути.
- Если она больше чем длина минимального пути, то нет смысла идти по этому пути дальше и помечаем город как не посещенный, выходим из города.
- Иначе если мы в конце пути тогда, сравниваем с минимальным путем, если он меньше кратчайшего пути, тогда минимальный путь = кратчайший путь.
- Переходим к следующему городу, где мы не были путем вызова этой же самой функции, до тех пор пока не просмотрим все города.
2.2 Теоретическая сложность
Задача коммивояжера относится
к классу NP — задачи, которые могут
быть решены за полиномиально выраженное
время с помощью
2.3 Разработка программы
Программы была написана в среде Borland C++ Builder.
i=0 -счетчик количества вершин графа
Al[]="
coord [50][2] - массив для координат вершин
mat[50][50] - матрица смежности
M[50] - M-текущий путь
minp[50] - minp-минимальный путь
in1,in2 - индексы вершин графа
min - минимальная сумма
summ - текущая сумма
gor - счетчик пройденных городов
ngor - найден ли город
Алгоритм поиска состоит из 2-х функций:
- void poisk(int x) - функция в которой происходят основные вычисления т.е нахождение кратчайшего пути.
Код функции:
void poisk(int x) //поиск следующего города в порядке обхода после города с номером Х
{
if ((gor==k)&& //если просмотрены все города,
(mat[x][1]!=0)&&
(summ+mat[x][1]<min))
{
ngor=1; //маршрут найден
min=summ+mat[x][1];
for (int i=1;i<=k;i++)minp[i]=M[i]; //изменяем: новый минимальный путь
}
else
{
for (int i=1;i<=k;i++)
//из текущего города
if ((i!=x)&& //новый город не совпадает с текущим
(mat[x][i]!=0)&& //есть прямой путь из x в i
(M[i]==0)&&
//новый город еще не
(summ+mat[x][i]<min)) //текущая сумма не превышает минимальной
{
summ+=mat[x][i];
gor++;
//количество просмотренных
M[i]=gor; //отмечаем у нового города новый номер в порядке обхода
poisk(i); //поиск нового города начиная с города i
M[i]=0; //возвращаем все назад
gor--;
summ-=mat[x][i];
}
}
}
- void pusk() – функция запуска алгоритма поиска и инициализация основных переменных.