Текущая Нижняя граница=32800
Найдем минимальные элементы в каждой строке и
затем вычтем его из остальных элементов строки (минимальные элементы записаны
напротив соответствующих строк). Получим матрицу представленную ниже.
|
|
1 |
2 |
4 |
7 |
|
1 |
∞ |
0 |
8900 |
3500 |
|
2 |
0 |
∞ |
5400 |
0 |
|
3 |
3500 |
0 |
∞ |
3500 |
|
5 |
3500 |
0 |
700 |
∞ |
То же проделаем и со столбцами, не содержащими
нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.
|
1247 |
|
|
|
|
|
1 |
∞ |
0 |
8200 |
3500 |
|
2 |
0 |
∞ |
4700 |
0 |
|
3 |
3500 |
0 |
∞ |
3500 |
|
5 |
3500 |
0 |
0 |
∞ |
Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г1,2=3500, Г2,1=3500, Г2,7=3500, Г3,2=3500, Г5,2=0, Г5,4=4700,
Максимальное значение имеет Г5,4=4700
Удалим из матрицы стоимости строку 5 и столбец
4. Внесем в текущий ориентированный граф дугу (5,4)
|
|
1 |
2 |
7 |
|
1 |
∞ |
0 |
3500 |
|
2 |
0 |
∞ |
0 |
|
3 |
3500 |
0 |
3500 |
В строке 3 и столбце 7 отсутствует элемент равный ∞. Присвоим элементу (3,7) значение бесконечности чтобы избежать преждевременного замыкания контура.
Текущая Нижняя граница=34600
Найдем минимальные элементы в каждой строке и
затем вычтем его из остальных элементов строки (минимальные элементы записаны
напротив соответствующих строк). Получим матрицу представленную ниже.
|
127 |
|
|
|
|
1 |
∞ |
0 |
3500 |
|
2 |
0 |
∞ |
0 |
|
3 |
3500 |
0 |
∞ |
То же проделаем и со столбцами, не содержащими
нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.
|
127 |
|
|
|
|
1 |
∞ |
0 |
3500 |
|
2 |
0 |
∞ |
0 |
|
3 |
3500 |
0 |
∞ |
Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г1,2=3500, Г2,1=3500, Г2,7=3500, Г3,2=3500,
В результате сравнения мы получили 4 одинаковых максимальных Г=3500. Это означает что алгоритм разветвляется и мы должны рассмотреть все получившиеся варианты поочередно. Рассмотрим вариант Г1,2=3500
Удалим из матрицы стоимости строку 1 и столбец
2, и присвоим элементу (2,1) значение бесконечности. Внесем в текущий
ориентированный граф дугу (1,2)
|
|
1 |
7 |
|
2 |
0 |
0 |
|
3 |
3500 |
∞ |
В строке 2 и столбце 1 отсутствует элемент равный ∞. Присвоим элементу (2,1) значение бесконечности, чтобы избежать преждевременного замыкания контура.
Текущая Нижняя граница=34600
После того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтенные элементы матрицы к нижней границе), и добавляем к маршруту коммивояжера дуги которым соответствуют нулевые элементы.
НГр=38100
Маршрут коммивояжера включает в себя дуги:, (7, 6), (6, 5), (4, 3), (5, 4), (1, 2), (2, 7), (3, 1)
------------------------------------------------------------------------
Вернемся к возникшему у нас ветвлению и
рассмотрим случай, при котором максимальное значение имеет Г3,2. Удалим из
матрицы стоимости строку 2 и столбец 3. Внесем в текущий ориентированный граф
дугу (3,2)
|
|
1 |
7 |
|
1 |
∞ |
3500 |
|
2 |
0 |
0 |
В строке 2 и столбце 7 отсутствует элемент равный ∞. Присвоим элементу (2,7) значение бесконечности, чтобы избежать преждевременного замыкания контура.
После того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтенные элементы матрицы к нижней границе), и добавляем к маршруту коммивояжера дуги которым соответствуют нулевые элементы.
НГр=38100
Маршрут коммивояжера включает в себя дуги:, (7, 6), (6, 5), (4, 3), (5, 4), (3, 2), (1, 7), (2, 1)
------------------------------------------------------------------------
Вернемся к возникшему у нас ветвлению и
рассмотрим случай при котором максимальное значение имеет Г2,7. Удалим из
матрицы стоимости строку 7 и столбец 2. Внесем в текущий ориентированный граф
дугу (2,7)
|
|
1 |
2 |
|
1 |
∞ |
0 |
|
3 |
3500 |
0 |
В строке 3 и столбце 2 отсутствует элемент равный ∞. Присвоим элементу (3,2) значение бесконечности, чтобы избежать преждевременного замыкания контура.
После того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтенные элементы матрицы к нижней границе), и добавляем к маршруту коммивояжера дуги которым соответствуют нулевые элементы.
НГр=38100
Маршрут коммивояжера включает в себя дуги:, (7, 6), (6, 5), (4, 3), (5, 4), (2, 7), (1, 2), (3, 1)
------------------------------------------------------------------------
Вернемся к возникшему у нас ветвлению и
рассмотрим случай при котором максимальное значение имеет Г2,1. Удалим из
матрицы стоимости строку 1 и столбец 2. Внесем в текущий ориентированный граф
дугу (2,1)
|
|
2 |
7 |
|
1 |
0 |
3500 |
|
3 |
0 |
∞ |
В строке 1 и столбце 2 отсутствует элемент равный ∞. Присвоим элементу (1,2) значение бесконечности чтобы избежать преждевременногог замыкания контура.
После того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтеные элементы матрицы к нижней границе), и добавляем к маршруту комивояжера дуги которым соответствуют нулевые элементы.
НГр=38100
Маршрут коммивояжера включает в себя дуги:, (7, 6), (6, 5), (4, 3), (5, 4), (2, 1), (1, 7), (3, 2)
-------------------------------------------------------------------------
Мы рассмотрели все возможные ветви алгоритма, теперь необходимо выбрать из полученых в результате рассмотрения каждой ветви значений нижней границы - минимальное. Это и будет оптимальной длиной пути коммивояжераМинимальное значение имеет НГр=38100
Соответствующий оптимальный контур включет дуги:, (6, 7), (5, 6), (3, 4), (4, 5), (1, 2), (2, 3), (7, 1)