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

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

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

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

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

Етап 1. Виконуємо редукцію рядків, тобто в кожному рядку знаходимо мінімальний елемент і віднімаємо його від елементів даного рядка. В результаті отримуємо наступну таблицю:

де стовбець містить значення мінімальних елементів кожного рядка.

Далі, виконуємо редукцію колонок — в кожній колонці знаходимо мінімальний елемент і віднімаємо йлго від елементів даної колонки (рядок  містить мінімальні елементи кожної колонки).

Після цього, обчислюємо найнижчу можливу межу функції мети.

Тобто, функція мети  повинна знаходитьсь в межах .

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

Штрафом i-го  рядка називається найменше значення даного рядка після першого нуля. Якщо i-й рядок містить дві чи більше нульові комірки, то .

Штрафом j-ї колонки називається найменше значення даної колонки після першого нуля. Якщо j-та колонка містить дві чи більше нульові комірки, то .

Для кожної нульової комірки визначаємо вторинні штрафи за наступною формулою: . Після чого заносимо їх в наступну таблицю:

Далі, знаходимо максимальне значення серед знайдених вторинних штрафів. В нашому випадку найбільшим є . Тобто, в шлях комівояжера потрібно внести комірку (5,3). В результаті, отримуємо нову таблицю, в якій викреслюємо з розгляду п'ятий рядок і третю колонку.

Виходячи з того, що у будь-якому рядку і у будь-якій колонці таблиці комівояжера повинна існувати одна заборонена комірка. В нашому випадку, такої комірки немає у рядку i=3 та колонці j=5. Тому забороняємо дану комірку. В результаті отримуємо нову таблицю, яку використовуємо для розрахунків на другому етапі.

Етап 2. Анілогічно першому етапу виконуємо редукцію рядків і колонок. Отримуємо:

Якщо б дані  і  відрізнялися від нуля, то ми повинні були б визначити нову функцію:

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

Знаходимо штрафи рядків і колонок.

Для кожної нульової комірки визначаємо вторинні штрафи.

Серед знайдених значень вторинних штрафів знаходимо максимальне. Це означає, що комівояжер повинен використати на своєму шляху відвідати місто (1,2). В результаті, для третього етапу отримуємо нову таблицю, в якій відсутні рядок i=1 та колонку j=2, та комірка (2, 1) являється забороненою.

Етап 3. Виконуємо редукцію рядків і колонок, а також знаходимо штрафи рядків і колонок.

Для кожної нульової комірки визначаємо вторинні штрафи.

Серед знайдених значень вторинних штрафів знаходимо максимальне і заносимо до оптимального шляху комівояжера місто (3,4). В результаті ми отримали ма таблицю, яка містить два рядки і дві колонкт. На цьому алгоритм припиняється, бо дана таблиця вказує завершальний шлях комівояжера (2,5) і (4,1).

Таким чином, ми отримали маршрут:

з витратами . При цьому виконується умова .