загрузка...
Пошук по сайту

Рішення задачі комівояжера online безкоштовно

Приклад рішення задачі комівояжера

ІНСТРУКЦІЯ для вирішення методом гілок і меж Виберіть розмірність матриці (кількість міст), натисніть Далі . Отримане рішення зберігається у файлі MS Word.

Виберіть кількість міст

Вирішити задачу комівояжера методом гілок і меж.

Рішення задачі комівояжера (метод гілок і меж)

Метод гілок і меж

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