Популярні рубрики
Рішення задачі комівояжера online безкоштовно
Приклад рішення задачі комівояжера
ІНСТРУКЦІЯ для вирішення методом гілок і меж Виберіть розмірність матриці (кількість міст), натисніть Далі . Отримане рішення зберігається у файлі MS Word.
Виберіть кількість міст
Вирішити задачу комівояжера методом гілок і меж.
Рішення задачі комівояжера (метод гілок і меж)
Метод гілок і меж
У задачі комівояжера для формування оптимального маршруту об'їзду n міст необхідно вибрати один кращий з (n-1)! варіантів за критерієм часу, вартості або довжини маршруту. Ця задача пов'язана з визначенням Гамільтона циклу мінімальної довжини. У таких випадках безліч всіх можливих рішень слід представити у вигляді дерева - зв'язного графа, що не містить циклів і петель. Корінь дерева об'єднує всі безліч варіантів, а вершини дерева - це підмножини частково впорядкованих варіантів рішень.
Вершина (i, j) відповідає підмножині всіх маршрутів, що містять ребро (i, j), а вершина (i *, j *) - підмножині всіх маршрутів, де це ребро відсутнє.
Процес розбиття на ці підмножини можна розглядати як розгалуження дерева. Тому метод називається методом пошуку по дереву рішень , або методом гілок і меж .
Метод гілок і меж представляє собою алгоритм спрямованого перебору безлічі варіантів рішення задачі. Суть методу гілок і меж полягає в тому, що від кореня дерева гілкуються не всі вершини.