о дереву варіантів до вершини і довжину одного їх шляхів використовуємо для подальшої оцінки варіантів. p> Повертаємося тепер по дереву вгору до найближчого вузла (12). Чи не розглянута гілку дерева () має нижню оцінку 30, що гірше досягнутого результату. Значить, цю гілку можна далі не досліджувати. Переходимо до гілки (). Оцінювання цієї гілки нижче 27, тому дане безліч слід розглянути. p> У результаті дослідження прийдемо до результату, що оптимальний шлях (123541).
Порівняємо тепер даний метод з динамічним програмуванням. У ДП на черговому кроці вибирається найкоротший шлях, що веде в дану точку; всі інші шляхи виключаються з подальшого розгляду. У МВГ при розбитті також розглядається найкоротший шлях, що містить перехід (ij) і безліч інших шляхів (). Але, на відміну від ДП, ми не може безліч (ij) виключити з подальшого розгляду. У процесі послідовного розбиття, рухаючись від кореня до однієї з вершин, необхідно запам'ятати в кожному з вузлів інформацію для подальшого аналізу безлічі можливих шляхів при поверненні від вершини до кореня дерева. Слід зазначити, що МВГ досить економічний з точки зору необхідної пам'яті. Якщо рішення задачі метод гілок і меж перервати (наприклад, після закінчення відведеного часу), то хоча оптимальне рішення не буде досягнуто, в пам'яті буде зберігатися одне з можливих рішень. У динамічному програмуванні рішення виходить тільки на останньому кроці обчислювального процесу (воно ж і оптимальне). p> З викладеного слід зробити висновок, що МВГ - вельми ефективний метод, за допомогою якого можна вирішувати різноманітні завдання з адитивною цільовою функцією.
Лістинг програми
В
var
Way: TVector;
LengthOfWay: real;: boolean; Addiction (var to SizeOfMatrix do (Matrix [NumRow, i] Maxint then s: = 'X' Str (Round (Matrix [i, j]): 3, s);: = Text + s + '';: = Text + # 13 + # 10;: = Text + # 13 + # 10; FindNextPoint (var BestPointAfterBasis: integer; var SpareDistance: real);, min2: real;: integer;, BestColumn: integer; i: = 1 to SizeOfMatrix doRound (Matrix [i, 0]) = basis then: = i;; i: = 1 to SizeOfMatrix doMatrix [RowOfBasis, i] = 0 then: = i;: = Round (Matrix [0, i]);;: = 1e38; i: = 1 to SizeOfMatrix do (i <> BestColumn) and (Matrix [RowOfBasis, i]
