Page 115 - 6197


L G   t f 2 ,   d   t f   .
kp

У матриці, що відповідає множині k, p вилучити k -тий
рядок і p -тий стовпець і реалізувати процедуру заборони
циклів.
Необхідно розглянути всі зв’язані шляхи i ,i , ,i , які є
1 2 s
вхідними ребрами і покласти c  M , s  1,r  1. Привести
rs
  t
отриману матрицю. Знайти суму констант приведення  для
f
  t
G і знайти
f 1 ,
 
  t
L G   t f 1 ,  d   t f   .
f
St4. Продовжити процес розгалуження, починаючи з кроку
St1, замінивши t на t  . Процес обчислень закінчується після
1
відсіву всіх множин, які не були піддані розбиттю. У
результаті отримуємо матрицю розміром 2 2 .
Приклад 2.3. Необхідно знайти найкоротший маршрут
комівояжера, коли n  , а віддалі між відповідними
6
пунктами вмішує табл. 2.8. У табл. 2.8 M - досить велике
додатне число.

Таблиця 2.8 – Віддалі між містами
Номера пунктів
1 2 3 4 5 6
1 M 27 43 16 30 26
2 7 M 16 1 30 25
Номера пунктів 3 20 13 M M 18 18
35
0
5
4
16
25
21
5 12 46 27 48 M 5
6 23 5 5 9 5 M

115