Вибираючи один з них, ми вибираємо оптимізацію одного кроку шляху (найкоротший перший крок). При цьому, звичайно, ми не знаємо, як це відіб'ється на довжині подальшого шляху. Позначимо (ij) безліч шляхів, що не містять безпосередній перехід з i в j. Оскільки з i треба кудись вийти, а в j звідкись прийти, то цій безлічі відповідає оцінка:
LS Ві g (ij) = d0 + qij, де qij =
Тоді нижньої оцінкою для безлічі шляхів буде g2 = d0 + qij. Ми зацікавлені у виборі такого переходу ij, для якого ця оцінка є найвищою. Цей вибір можна зробити, відшукавши серед нульових елементів i рядки такий, якому відповідає q2 = max qij. Вибором пари (ij) усі безліч можливих шляхів розбивається на дві підмножини. Одне з них містить перехід (ij) (йому відповідає оцінка g1 = d0 + q1), інше (ij) (йому відповідає оцінка g2 = d0 + q2). p> У нашому прикладі першим кроком шляху повинен бути перехід з п.1. Сij = 0 для i, j = 1,2. Безліч всіх можливих шляхів W розбиваємо на два: що містять перехід (12) і не містять перехід (12). Будуємо для них нижні оцінки. g1 = d0 = 23. Для переходу, що не містить (12), відповідає шлях, що містить переходи (14) і (32). На цьому перша ітерація обчислювального процесу закінчується. При подальшому русі за пошуком оптимального шляху будемо спостерігати за допомогою дерева варіантів (рис.2). <В
Рис. 2. br/>
Розглянемо тепер перші підмножина. У ньому вже реалізований перехід (12), тому в таблиці С02 рядок 1 і стовпець 2 видаляємо (викреслюємо) з подальшого розгляду. С02 перетворюється на С1, а після приведення - у С12. У верхньому лівому куті таблиці С1 ставимо хрестик, оскільки перехід (21) у розглянутому підмножині (12) ставати неможливим. p> Тепер над новою таблицею проробляємо ті ж дії, що і над С2. Для С12 константа приведення a1 = 2. Далі в якості можливих розглянемо підмножини, що містять шляхи (23) і (), і проведемо їх оцінку:
(23) g23 = g1 = (d0 + d1) + с23 = 23 + 2 + 0 = 25.
() = g2 = (d0 + d1) + W23 = 25 + 5 = 30,
де W23 == C24 + C 43 = 3 +2 = 5.
Після викреслювання з таблиці C12 рядка i = 2 і стовпця j = 3 виходить матриця С2 розміром 3х3. Чергове розбиття можливих варіантів переміщення на підмножині (34) і () дає оцінки g34 = 26 і = 27. p> Після чергового скорочення матриці таблиця приймає розмір 2х2 і однозначно визначає шлях: початкова точка 4, кінцева - 1, шлях (451). Він має довжину 6. По дереву варіантів ми пройшли шлях до вершини. Довгий шлях (123451) має довжину 32. Аналогічно безліч () містить єдиний шлях (3541) довжиною 2. Шлях (123541) має довжину 27, його довжина менше, ніж у дорозі, що містить перехід (34). В якості нижньої межі тепер слід вибирати 27. Будь-яке безліч, що має оцінку більше 27, слід відкинути. Якщо ж оцінка менше 27, то такий шлях підлягає дослідженню. Якщо, пройшовши по новому шляху, отримаємо значення довжини менше 27, то це нове значення слід взяти в якості нової оцінки. Отже, ми пройшли п...
