Page 114 - 6197

  1
  2
Із матриці C , яка відповідає множині G вилучаємо i
1 0
рядок і j стовпець, а елементу c   2 присвоюємо значення M ,
0 i 0 0 j
тобто
c   2  M .
j 0 0 i
Прирівнювання c   2 до M запобігає появлення циклу
j 0 0 i
i
i  j  на маршруті.
0 0 0
  3
У результаті отримаємо нову матрицю C , над якою
здійснюємо операцію проведення, і знаходимо
n   3
0 
  r  h i  . (2.22)
i
i 1
  1
Тоді для множини маршрутів G обчислюємо
1
 
L G 1   1  d   ,
0
0
  1
а для G будемо мати
2
 
L G 2   1  d   .
0
ij
Подальші обчислення відбуваються у відповідності з
правилами відсіву і розгалуження за таким алгоритмом.
St1. Серед не відсіяних за правилом відсіву множин, до
яких не була застосована операція розгалуження, вибирається
  t
  t
множина G з найменшою нижньою оцінкою d .
f f
St2. У матриці C , яка відповідає вибраній множині для
всіх c  визначити константи  за формулою (2.20) і
0
sq sq
визначити   max : .
kp sq
c sq  0

  t
St3. Розбити множину G на дві множини G   t  k, p і
f f 1 ,


G   t  k, p . У матриці, що відповідає множині k, p
f 2 ,

заборонити перехід k, p , тобто c  M . Обчислити оцінку
kp
114