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

Введение

      Каждый  человек ежедневно, не всегда  осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда  ограничены. Жизнь была бы менее  интересной, если бы это было  не так. Чтобы достичь наибольшего  эффекта, имея ограниченные средства, надо составить план, или программу  действий.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  1. Теоретическая часть     
  2.  

    1. Постановка задачи

 

Имеются n городов, расстояния (стоимость проезда, расход горючего на дорогу и т.д.) между которыми известны. Коммивояжер должен пройти все n городов по одному разу, вернувшись в тот город, с которого начал. Требуется найти такой маршрут движения, при котором суммарное пройденное расстояние (стоимость проезда и т.д.) будет минимальным.

Очевидно, что задача коммивояжера – это задача отыскания кратчайшего  гамильтонова цикла в полном графе.

Существует метод решения  задачи коммивояжера, который дает оптимальное решение. Этот метод  называется методом ветвей и границ. Решение задачи коммивояжера методом ветвей и границ по-другому называют алгоритмом Литтла.

 

1.2 Описание метода

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

 Определение нижних  границ базируется на том утверждении,  что если ко всем элементам i-й строки или j-го столбца матрицы C прибавить или отнять число , то задача останется эквивалентной прежней, то есть оптимальность маршрута коммивояжера не изменится, а длина любого гамильтонова контура изменится на данную величину .

Опишем алгоритм Литтла для  нахождения минимального гамильтонова контура для графа с 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). Таким  образом, претендентом на включение  в гамильтонов контур является  дуга (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) Узнаем степени нулей  матрицы. Претендентами на включение  в гамильтонов контур будут  несколько дуг (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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  1. Программная реализация

 

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

 

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

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

 

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

        }

     }

}

 

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