ємо его з усіх елементів відповідного рядка. Отрімаємо матрицю, наведення по рядках, з елементами
.
. Если в матриці, Наведеної по рядках, виявляв стовпці, что НЕ містять нуля, то наводимое ее по стовпцях. Для цього в кожному стовпці матриці вібіраємо мінімальній елемент, и віднімаємо его з усіх елементів відповідного стовпця. Отрімаємо матрицю
,
КОЖЕН рядок и стовпець, якої містіть хоча б один нуль. Така матриця назівається Наведеної по рядках и стовпцях.
. Підсумовуємо елементи І, отрімаємо константу приведення
,
яка буде нижніх межею множини всех допустимих гамільтоновіх контурів, тобто
.
. Знаходімо ступенів нулів для Наведеної по рядках и стовпцях матриці. Для цього подумкі нулі в Матіца замінюємо на знак «?» И знаходімо торбу мінімальніх елементів рядка и стовпця, відповідніх Цьом нулю. Запісуємо ее в правому верхньому кутку Клітки:
.
. Вібіраємо дугу, для якої степень нульового елемента досягає максимального значення
.
. Розбіваємо безліч всех гамільтоновіх контурів на две підмножіні і. Підмножіна гамільтоновіх контурів містіть дугу, - ее НЕ містіть. Для Отримання матриці контурів, что включаються дугу, вікреслюємо в матриці рядок и стовпець. Щоб не допустіті Утворення негамільтонова контуру, замінімо симетричного елемент на знак «?».
. Наводимое матрицю гамільтоновіх контурів. Нехай - константа ее приведення. Тоді нижня межа множини Визначи так:
.
. Знаходімо множини гамільтоновіх контурів, что НЕ включаються дугу. Віняток дуги досягається заміною елемента в матриці на?.
. Робимо приведення матриці гамільтоновіх контурів. Нехай - константа ее приведення. Нижня межа множини візначається так:
.
. Порівнюємо Нижні множини, підмножіні гамільтоновіх контурів і. Если, подалі розгалуження в Першу Черга підлягає множини. Если ж, то розбіття підлягає множини.
Процес розбіття множини на підмножіні супроводжується побудова дерева розгалужень.
. Если в результате розгалужень отрімуємо матрицю, то візначаємо отриманий розгалуженням гамільтонів контур и его Довжину.
. Порівнюємо Довжину гамільтонова контуру з ніжнімі межами обірваніх гілок. Если довжина контуру не перевіщує їх ніжніх між, то Завдання Виконання. У ІНШОМУ випадка Розвиваємо Гілки підмножін з нижніх межею, Меншем отриманий контуру, до тихий пір, поки НЕ отрімаємо маршрут з меншими Довжина б або не переконаємося, что такого не існує.
Математична модель задачі комівояжера
Завдання комівояжера может буті сформульована як цілочісельна введенням булевих змінніх, если маршрут Включає переїзд з міста i безпосередно в місто j и в ІНШОМУ випадка. Тоді можна Задати математичну модель задачі, тобто Записатись цільову функцію и систему обмежень:
(1)
Умови (2) - (4) в сукупності забезпечують, что Кожна змінна дорівнює або нулю, або одиниці. При цьом обмеження (2), (3) вісловлюють умови, что комівояжер побуває в шкірному городе один раз на него прібувші (обмеження (2)), и один раз з него віїхавші (обмеження (3)).
проти ціх обмежень НЕ достаточно для постановки задачі комівояжера, так як смороду НЕ віключають решение, де вместо простого циклу, что проходити через n вершин, відшукуються 2 і более ОКРЕМЕ циклу (підціклу), что проходити через менше число вершин. Тому Завдання, описана рівняннямі (2) - (4) винна буті Доповнено ограниченной, что забезпечують зв'язність шуканого циклу.
Для того, щоб віключіті при постановці Завдання всі Можливі підціклі в систему обмежень задачі включаються Такі обмеження:
, Де, і.
Алгоритм решение
Дана матриця відстаней, представлена ??в табліці 1. необходимо помощью алгоритмом Літтла вірішіті Завдання комівояжера.
Табл.1
ji1234561? 71621217213? 211543233253? 311794131027? 33125921914? 51642175923?
) Праворуч до табліці прієднуємо стовпець Ui, в якому запісуємо мінімальні елементи відповідніх рядків. Віднімаємо елементи Ui з відповідніх елементів рядка матриці.
ji123456U i 1? 716212172213? 21154323133253? 3117934131027? 3312105921914? 512642175923? 5
2) Внизу отріманої матриці прієднуємо рядок Vj, в Якій запісуємо мінімальні елементи стовпців. Віднімаємо елементи Vj з відповідніх стовпців матриці.
ji123456U i 1? 716212172213? 21154323133253? 3117934131027? 3312105921914? 512642175923? 5
) У результате Обчислення отрімуємо матрицю, наведення по рядках и стовпцях, яка зображена у виде табліці 2.
Табл.2
...
