Решение задачи методом ветвей и границ

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) Узнаем степени нулей  матрицы. Претендентами на включение  в гамильтонов контур будут  несколько дуг (5;2) и (6;3). Для  дальнейших расчетов выберем  дугу (6;3). Разбиваем множество  на два подмножества: и (табл. 3 и 4). Чтобы не допустить образования негамильтонова контура, в таблице 3 заменяем элемент (3;6) на знак «∞»

 

Табл.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. Программная реализация

 

2.1 Разработка  алгоритма 

 

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

1. Допустим, что мы пришли в какой-то город i. Помечаем его, что мы здесь уже были.
2. Подсчитываем длину пройденного пути.
3. Если она больше чем длина минимального пути, то нет смысла идти по этому пути дальше и помечаем город как не посещенный, выходим из города.
5. Иначе если мы в конце пути тогда, сравниваем с минимальным путем, если он меньше кратчайшего пути,  тогда минимальный путь = кратчайший путь.
6. Переходим к следующему городу, где мы не были путем вызова этой же самой функции, до тех пор пока не просмотрим все города.

 

2.2 Теоретическая сложность

 

Задача коммивояжера относится  к классу NP — задачи, которые могут  быть решены за полиномиально выраженное время с помощью недетерминированной  вычислительной машины, то есть машины, следующее состояние которой  не всегда однозначно определяется предыдущими. Работу такой машины можно представить  как разветвляющийся на каждой неоднозначности  процесс: задача считается решённой, если хотя бы одна ветвь процесса пришла к ответу. Другое определение класса NP: к классу NP относятся задачи, решение  которых с помощью дополнительной информации полиномиальной длины, данной нам свыше, мы можем проверить  за полиномиальное время. В частности, к классу NP относятся все задачи, решение которых можно проверить  за полиномиальное время. Поиск решения требует проверки n! перестановок n городов т.е сложность задачи O(n!).

 

2.3 Разработка программы

Программы была написана в  среде Borland C++ Builder.

i=0 -счетчик количества вершин графа

Al[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" – массив содержащий названия вершин графа

coord [50][2] - массив для координат вершин

mat[50][50] - матрица смежности

M[50] - M-текущий путь

minp[50] - minp-минимальный путь

in1,in2 - индексы вершин графа

min - минимальная сумма

summ - текущая сумма

gor - счетчик пройденных городов

ngor - найден ли город

 

Алгоритм поиска состоит  из 2-х функций:

1. 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];

        }

     }

}

 

2. void pusk() – функция запуска алгоритма поиска и инициализация основных переменных.