Роз'вязання задачі комівояжера за методом редукції рядків і колонок

Процес знаходження оптимального маршруту, в задачі комівояжера, методом редукції рядків і колонок розкладається на (n-2) етапа. У межах кожного етапу алгоритм розрахунків однаковий.

Для наглядності, розглянемо конкретний випадок задачі комівояжера, а саме, комівояжер повинен обїхати 5 міст, побувавши в кожному по одному разу і повернутися у початкове. При цьому витрати повинні бути мінімальними.

Тарифи на переміщення між містами знаходяться в наступній таблиці:

Метод редукції рядків і колонок

Перш ніж приступити до першого етапу, знайдемо можливу верхню межу функції мети. Для цього, вибираємо довільний маршрут metod_redukcii_radkiv_i_kolonok19, для якого обчислюємо значення функції Метод редукції рядків і колонок. Значення функції мети Метод редукції рядків і колонок повинно бути меншим за Метод редукції рядків і колонок.

Читати повністю