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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

з витратами Метод редукції рядків і колонок. При цьому виконується умова Метод редукції рядків і колонок.

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар