Использование метода ветвей и границ

      

     Выполняется шаг Б, то есть вычисляется оценка подмножества Е(i;j), содержащего перспективную коммуникацию на ветвление (5;3), как сумма оценки множества Е и значения понижения матрицы, полученного после ее приведения на этом шаге.

     НГЕ(5;3)=НГЕ+ 7+0+0=7

     Так как оценка НГЕ(5;3)=7 меньше, чем оценка НГ (5;3)=13, то можно считать, что искомый оптимальный цикл J^* содержит коммуникацию, выбранную в качестве перспективного претендента на ветвление (5;3), и можно осуществлять дальнейшее ветвление дерева из вершины (5;3). 

     

7. Шаг Е. Построение графа искомого цикла

     Разбиение множества всех полных циклов Е на непересекающиеся подмножества графически изображается деревом ветвей с вершинами  из подмножества Е(i;j) и (i;j).

     

     

8. Шаг Ж. Продолжение ветвления

     Далее проводятся те же действия, что и на шагах В, Г, Д, Е. 

     2.1.Шаг  В. Выбор претендующей  коммуникации на  ветвление

     Определим дугу, исключение которой максимально  увеличило бы полученную оценку НГЕ(5;3). Рассчитаем понижение для элементов (i;j) полученной матрицы, имеющих нулевые значения.

     d(1;4)=2+0=2

     d(2;4)=5+0=5

     d(3;2)=4+2=6

     d(4;1)=0+6=6

     d(4;5)=0+3=3 

     Максимальную  оценку имеют две пары претендентов на ветвление, а именно: (3;2) и (4;1). В  случае равенства максимальных значений для нескольких претендентов выбор из них перспективной коммуникации на ветвление осуществляется произвольно.

     Выбираем  для ветвления пару (3;2). 

     2.2.Шаг  Г. Разделение  на подмножества (ветвление)

     Произведем  ветвление Е(5;3):

     Е(5;3)=Е(i;j)͝ (i;j),

     где Е(i;j)={(5;3),(3;2)}, (i;j)={( }

     Вычислим  оценку подмножества (i;j).

     Оценка (нижняя граница) подмножества (i;j) равно сумме оценки множества Е(5;3) и понижения для наиболее перспективного претендента на ветвление, вычисленного в 2.1. на шаге В. Нижняя граница множества полных циклов Е(5;3) была вычислена в 1.6. на шаге Б. Следовательно:

     НГ (5;3),(3;2)=НГЕ(5;3)+d(3;2)=7+6=13 

     2.3.Шаг  Д. Переход к  матрице меньшего  размера (усечение  матрицы)

     На  этом шаге вычисляется оценка (нижняя граница) подмножества Е(ij).

     В приведенной см 1.6. матрице вычеркивается  третья стока и второй столбец. Для  вновь полученной матрицы повторяется  шаг А. 
 

     Таблица 6

 

     Выполняется шаг Б, то есть вычисляется оценка подмножества Е(i;j), содержащего перспективную коммуникацию на ветвление (3;2), как сумма оценки множества Е(5;3) и значения понижения матрицы, полученного после ее приведения на этом шаге.

     НГЕ(5;3)(3;2)=НГЕ(5;3)+ 7+0+0=7

     Так как оценка НГЕ(5;3)(3;2)=7 меньше, чем  оценка НГ (5;3)(3;2)=13, то стоим графу искомого цикла. 

     2.4. Шаг Е. Построение графа искомого цикла

     Разбиение множества всех полных циклов Е на непересекающиеся подмножества графически изображается деревом ветвей с вершинами из подмножества Е(i;j) и (i;j).

     

     

     5.1.Шаг  В. Выбор претендующей  коммуникации на  ветвление

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

     d(1;4)=3+0=3

     d(2;4)=0+5=5

     d(4;1)=6+0=6

     d(4;5)=5+0=5 

     Максимальное  значение понижения рассматриваемых  элементов соответствует наиболее перспективному претенденту на ветвление. Перспективный претендент на ветвление – пара (4;1), так как d(4;1)=6 является максимальной оценкой из рассмотренных претендентов на ветвление. 

     5.2.Шаг  Г. Разделение  на подмножества (ветвление)

     Произведем  ветвление Е(3;2):

     Е(3;2)=Е(i;j)͝ (i;j),

     где Е(i;j)={(5;3),(3;2)(4;1)}, (i;j)={( }

     Вычислим  оценку подмножества (i;j).

     Оценка (нижняя граница) подмножества (i;j) равно сумме оценки множества Е(3;2) и понижения для наиболее перспективного претендента на ветвление, вычисленного в 5.1. на шаге В. Нижняя граница множества полных циклов Е(3;2) была вычислена в 2.3. на шаге Д. Следовательно:

     НГ (5;3),(3;2),(4;1)=НГЕ(5;3)(3;2)+d(4;1)=7+6=13 

     5.3.Шаг  Д. Переход к  матрице меньшего  размера (усечение  матрицы)

     На  этом шаге вычисляется оценка (нижняя граница) подмножества Е(ij).

     В приведенной (см 2.3.) матрице вычеркивается четвертая стока и первый столбец. Для вновь полученной матрицы повторяется шаг А. 
 
 
 
 
 
 

     Таблица 7

 

     Таблица 8

 

     Выполняется шаг Б, то есть вычисляется оценка подмножества Е(i;j), содержащего перспективную коммуникацию на ветвление (4;1), как сумма оценки множества Е(3;2) и значения понижения матрицы, полученного после ее приведения на этом шаге.

     НГЕ(5;3)(3;2)(4;1)=НГЕ(3;2)+ 7+0+3=10

     Так как оценка НГЕ(5;3)(3;2)(4;1)=10 меньше, чем  оценка НГ (5;3)(3;2)(4;1)=13, то можно осуществлять ветвление дерева из вершины (4;1). 

     5.4.Шаг  Е. Построение  графика искомого цикла

     Разбиение множества всех полных циклов Е на непересекающиеся подмножества графически изображается деревом ветвей с вершинами  из подмножества Е(i;j) и (i;j). 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     6.1.Шаг  В. Выбор претендующей  коммуникации на  ветвление

     Остались  пары: (1;4),(1;5),(2;4). Все они равны нулю, поэтому дальше соединяем график маршрутов. 
 
 
 
 
 
 
 
 

     7.1. Шаг В. Выбор  претендующей коммуникации на ветвление.

     Искомый полный оптимальный цикл J включает коммуникации:

     J={(5;3),(3;2)(4;1)(2;4)(1;5)},

     Имеет длину F(J)=10, а последовательность объезда  городов, если коммивояжер находился  в городе 5, можно представить  в виде:

     5 − 3 − 2 − 4 − 1 − 5. 

     Выполним  проверочный расчет для полученной последовательности. По исходной матрице  посчитаем F(J):

     F(J):1+1+1+3+4=10. Результат тот же, что и расчетный, следовательно расчеты выполнены правильно.