Схема работы метода ветвей и границ для задачи коммивояжера

Шаг 1. Определение начального рекорда. (При отсутствии дополнительной информации можно взять длину любого маршрута). Приведение исходной матрицы. Задать k=0.

Шаг 2. Выбор пары .

Шаг 3.  Ветвление .

Шаг 4. Преобразование матрицы . Вычисление матриц и . Если какая-то из этих матриц имеет размер 2 2, то переход к шагу 7.

Шаг 5.   Вычисление оценок  и .

Шаг 6.  Выбор перспективного множества  в соответствии со стратегией. Положить  Переход к шагу 2.

Шаг 7. Получение допустимого маршрута, возможная смена рекорда и сокращение перебора.

Шаг 8. Проверка критерия оптимальности. Если он  выполнен, то останов. Иначе переход к шагу 6.

Замечание. В момент получения матрицы 2 2 определяется замыкающая пара городов для образования допустимого маршрута.

Пример. Рассмотрим задачу коммивояжера с  и матрицей расстояний

+	5	3	2	4	5	2	7
7	+	1	6	7	8	9	6
3	2	+	3	2	4	5	7
4	6	2	+	1	3	6	2
4	5	1	2	+	4	2	3
3	8	9	6	4	+	1	5
1	6	6	4	2	1	+	0
7	8	7	2	8	3	0	+

 

С =

 

Положим R= . Осуществив операцию приведения, получаем матрицу .

№	1	2	3	4	5	6	7	8
1	+	3	1	0	2	2	0	5	2
2	5	+	0	5	6	6	8	5	1
3	0	0	+	1	0	1	3	5	2
4	2	5	1	+	0	1	5	1	1
5	2	4	0	1	+	2	1	2	1
6	1	7	8	5	3	+	0	4	1
7	0	6	6	4	2	0	+	0	0
8	6	8	7	2	8	2	0	+	0
	1	0	0	0	0	1	0	0	10

 

=      

 

В последнем столбце и нижней строке записаны приводящие константы. Их сумма S =10, то есть . Для каждого нулевого элемента матрицы  считаем : , . Имеем . Следовательно, . Формируем множества  и , добавляя соответственно условия  и . Вычисляем матрицы  и .

№	1	2	4	5	6	7	8
1	+	0	0	2	6	0	5	0
2	0	+	1	0	1	3	5	0
4	2	2	+	0	1	5	1	0
5	1	0	0	+	1	0	1	1
6	1	4	5	3	+	0	4	0
7	0	3	4	2	0	+	0	0
8	6	5	2	8	2	0	+	0
	0	3	0	0	0	0	0	4

 

=

 

 

№	1	2	3	4	5	6	7	8
1	+	3	1	0	2	2	0	5	0
2	0	+	+	0	1	1	3	0	5
3	0	0	+	1	0	1	3	5	0
4	2	5	1	+	0	1	5	1	0
5	2	4	0	1	+	2	1	2	0
6	1	7	8	5	3	+	0	4	0
7	0	6	6	4	2	0	+	0	0
8	6	8	7	2	8	2	0	+	0
	0	0	0	0	0	0	0	0	5

 

=      

 

 

Считаем оценки: , .
Выберем стратегию “по минимуму оценки”. В таком случае дальнейшему ветвлению подлежит множество . Для каждого нулевого элемента матрицы считаем : . Имеем . Следовательно, .

Формируем множества  и , добавляя соответственно условия  и . Вычисляем матрицы  и .

№	1	2	4	5	6	8
1	+	0	0	2	2	4	0
2	0	+	1	0	1	4	0
4	2	2	+	0	1	0	0
5	1	0	0	+	1	0	0
6	0	3	4	2	+	2	1
7	0	3	4	2	0	+	0
	0	0	0	0	0	1	2

  

 

=                                                        

 

№	1	2	4	5	6	7	8
1	+	0	0	2	2	0	5	0
3	0	+	1	0	1	3	5	0
4	2	2	+	0	1	5	1	0
5	1	0	0	+	1	0	1	0
6	1	4	5	3	+	0	4	0
7	0	3	4	2	0	+	0	0
8	4	3	0	6	0	+	+	2
	0	0	0	0	0	0	0	2

 

=

 

 

  

  

 

Вычисляем оценки: , .

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

№	1	3	4	5	6	7	8
1	+	1	0	2	2	0	5	0
2	0	+	0	1	1	3	0	0
4	2	1	+	0	1	5	1	0
5	2	0	1	+	2	1	2	0
6	1	8	5	3	+	0	4	0
7	0	6	4	2	0	+	0	0
8	6	7	2	8	2	0	+	0
	0	0	0	0	0	0	0	0

 

=      

 

№	1	2	3	4	5	6	7	8
1	+	0	1	0	2	2	0	5	0
2	0	+	+	0	1	1	3	0	5
3	0	+	+	1	0	1	3	5	0
4	2	2	1	+	0	1	5	1	0
5	2	1	0	1	+	2	1	2	0
6	1	4	8	5	3	+	0	4	0
7	0	3	6	4	2	0	+	0	0
8	6	5	7	2	8	2	0	+	0
	0	3	0	0	0	0	0	0	3

 

=      

 

Вычисляем оценки: , . Дальнейшему ветвлению подлежит множество .

Делим  на подмножества  и  по паре . Рассчитав матрицы  и , определяем , . Минимальную оценку 16 имеет три подмножества:  и .

Выберем для дальнейшего ветвления . Делим его на подмножества  и  по паре . Получим , .

Далее делим  на подмножества  и  по паре . Вычисляем , .

Делим  по паре  на  и . При этом получаем матрицу   размера 2 2. В результате выписываем допустимую точку

 

0	1	0	0	0	0	0	0
0	0	1	0	0	0	0	0
0	0	0	0	1	0	0	0
0	0	0	0	0	0	0	1
0	0	0	1	0	0	0	0
1	0	0	0	0	0	0	0
0	0	0	0	0	1	0	0
0	0	0	0	0	0	1	0

 

 

  со значением целевой функции .

Соответствующий маршрут: 1-2-3-5-4-8-7-5-1

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

Дерево вариантов в рассмотренном примере имеет вид

 

 

                                                              

 

                                                              

                              

                                                 

 

                     

 

         

 

      

УПРАЖНЕНИЯ

1. Предложите другие стратегии ветвления в задаче коммивояжера.

2. Решите задачу коммивояжера с матрицей:

a)                                                                                                                                  b)

+	3	93	13	33	9	57
4	+	77	42	21	16	34
45	17	+	36	16	28	25
39	90	80	+	56	7	91
28	46	88	33	+	25	57
3	88	18	46	92	+	7
44	26	33	27	84	39	+

+	27	43	16	30	26
7	+	16	1	30	25
20	13	+	35	5	0
21	16	25	+	18	18
12	46	27	48	+	5
23	5	5	9	5	+

 С =              C=

                            

 

             

Ответ: 1-4-6-7-3-5-2-1, L= 126.                      Ответ: 4-3-5-6-2-1-4, L= 63.

c)                                                              d)

+	14	9	8	10	6
10	+	7	4	11	5
11	10	+	10	20	11
12	4	4	+	9	4
13	10	9	7	+	10
11	9	8	3	4	+

+	4	10	13	4	8
2	+	9	7	6	7
8	5	+	5	5	9
5	8	5	+	7	10
6	4	4	9	+	4
5	1	4	8	3	+

 

 С =  С =     С =              

 

       

      Ответ: 3-1-6-5-4-2-3, L= 39.                        Ответ: 2-1-5-3-4-6-2, L= 26.