Название: Алгоритмы - Учебное пособие ( Редактор )

Жанр: Экономика

Просмотров: 1730


2.5. метод ветвей и границ

Идея метода ветвей и границ обычно излагается по работе Дж. Литтла, К. Мурти, Д. Суини, Е. Я. Карел  «Алгоритм решения задачи коммивояжера» (Экономика и математические методы. – 1965. – № 1. – С. 13–22).

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

2.5.1.  Задача о коммивояжере

Формулировка задачи и ее формализация приведена в п. 2.2.2. Рассмотрим матрицу расстояний, которая определяет систему дорог, связывающих города и расстояния между городами (пример – рис. 2.12).

 

Города

1

2

3

4

5

6

1

@

7

3

10

17

5

2

9

@

4

5

8

6

3

13

2

@

9

11

14

4

5

8

6

@

3

6

5

16

11

13

10

@

8

6

6

5

9

8

4

@

 

Рис. 2.12

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

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

 

   @   4      0     7   14       2

   5    @     0    1   4        2

   11     0     @   7   9      12  сумма вычитаемых констант равна 24.

   2     5      3   @   0       3

   8     3      5    2   @      0

   2    1        5   4    0      @

 

В первом и четвертом столбцах нет нулевых элементов, поэтому аналогичную операцию выполним со столбцами: из элементов первого столбца вычитаем 2, а из четвертого – 1.  

 

@    4    0   6  14     2

 3    @    0   0   4      2

 9    0    @   6   9    12 итоговая сумма вычитаемых констант равна 27.

 0    5    3   @   0    3

 6    3   5   1   @    0

 0    1   5   3   0      @

 

Это значит, что все пути коммивояжера уменьшились на это значение. Операцию уменьшения стоимости пути по строкам и столбцам назовем приведением. Нулями в матрице отмечен путь, стоимость которого равна 27.  При выборе пути, помните, что надо пройти все города и вернуться в исходный город. В нашем примере получится  путь (1®3®2®4®5®6®1) с минимальной стоимостью, любой другой путь имеет бльшую стоимость. Значение 27 – это оценка снизу всех маршрутов коммивояжера. Очевидно, что это удачно подобранный пример. Не обязательно после приведения существует искомый  путь по ребрам с нулевой стоимостью.  Пусть дана другая матрица расстояний:

 

@    1    2     3     4     5         

 2   @    3     4     5     6    

 3    4    @    5     6     7    

 7    6    5     @    4     3    

 6    5    4     3     @    2   

 

После приведения по строкам и столбцам получаем следующую матрицу.

 

@     01   00   1     3     4 

 00    @   0    1     3     4 

 0      1   @   1     3     4   сумма констант приведения равна 14.

 4      3    1   @    1     0

 4      3    1    0    @    00

 4      3    1    00    0    @

 

Путь по нулям в полученной матрице не является путем коммивояжера. Его вид показан на рис.2.13.

 

 

Рис. 2.13

 

Шаги ветвления. Рассмотрим нули в приведенной матрице. Начнем с нуля в позиции (1,2). Ноль в этой позиции означает, что стоимость переезда  из первого города во второй равна нулю. Однако если запретить переезд из первого во второй город, то въезжать во второй город все равно придется. Цена въезда указана во втором столбце – въезд из третьего города дешевле всего. Стоимость этого въезда равна 1. Поскольку из первого города выезжать коммивояжеру когда-либо придется, то дешевле всего выехать в третий город – нулевая стоимость. Вычисляем сумму этих минимумов, она равна  1+0=1. Смысл этой единицы в том, что если не ехать из первого города во второй, то придется заплатить не менее 1. Эта оценка нуля указана на приведенной матрице верхним индексом.

Таким же образом оцениваем все нули в матрице. Затем выбираем ноль с максимальной оценкой. Если таких нулей несколько, то выбираем любой.

 

Смысл ветвления. Все маршруты коммивояжера разбиваются на два класса: содержащих ребро (1,2) и не содержащих это ребро. Для последнего класса оценка снизу увеличивается на  единицу, т.е. равна 15. Для маршрутов из первого класса продолжаем работать с матрицей. Исключаем первую строку и второй столбец. В позиции 2,1 ставим @, запрет на перемещение. Получим следующую уменьшенную матрицу.

 

 

1

3

4

5

6

2

@

02

1

3

4

3

05

@

1

3

4

4

4

1

@

1

01

5

4

1

00

@

00

6

4

1

00

01

@

 

Продолжаем оценку маршрутов из первого класса. Если в строках или столбцах нет нулевых элементов, то приводим матрицу так же, как мы приводили исходную матрицу. В нашем примере сокращенную матрицу привести нельзя, так как минимальные элементы во всех строках и столбцах равны нулю. Таким образом, оценка снизу для классов маршрутов, содержащих (1,2), остается равной 14.

Далее оцениваются нули. Выбираем ноль с максимальной оценкой – он соответствует переезду из третьего города в первый.  

Разбиваем этот класс на подклассы по рассмотренной выше схеме, т.е. подкласс с(3,1) и без (3,1). Для второго подкласса оценка снизу 14+5=19.

В первом подклассе сокращаем матрицу, удаляя первый столбец и третью строку, пишем запрет на перемещение в позицию (2,3).

 

 

3

4

5

6

2

@

1

3

4

4

1

@

1

0

5

1

0

@

0

6

1

0

0

@

 

Матрица допускает операцию приведения. Вычитаем 1

из элементов первой строки и элементов первого столбца. Нижняя оценка маршрутов этого подкласса возрастает на 2, итого

14 +2 = 16.

 

 

3

4

5

6

2

@

02

2

3

4

00

@

1

00

5

00

00

@

00

6

00

00

01

@

 

 

 

 

 

 

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

 

 

3

5

6

4

@

1

01

5

00

@

00

6

00

00

@

 

Весь процесс работы по данной схеме представлен в виде дерева (рис. 2.14). Вершины в этом дереве представляют классы решений. Пометка «без» слева от вершины означает, что соответствующий класс не содержит какой-то конкретный переезд из города в город. Числа у вершин дерева означают оценки снизу для маршрутов данного класса.  Мы получили первую оценку – 16 для маршрута 1® 2® 4® 6® 5® 3® 1. Все подклассы решений, у которых оценки снизу больше или равны 16, исключаются из рассмотрения.  Остался  только подкласс без переезда

Рис. 2.14

 

из первого города во второй, его оценка равна 15. Однако после первого же ветвления по рассмотренной выше схеме получаются подклассы с оценками 16 и 17. Это значит, что обработку можно заканчивать. Найден наилучший маршрут коммивояжера, стоимость проезда по этому маршруту равна 16.

В п. 2.3 рассмотрен один из методов решения задачи коммивояжера, в данном пункте – другой. В чем их отличие?  По некоторым оценкам, встречающимся в литературе, с помощью метода ветвей и границ можно решать задачи с N £ 100, в первом случае – не больше 50.