1.4 Аналіз методів рішення задачі комівояжера

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

Алгоритм лексического перебора
Кол-во городов	Время обработки, c	Вероятность неправильного ответа, %	Тип алгоритма
10	41	0	точный
12	12000=3ч.20мин	0
32	-*	0
100	-*	0
Метод ветвей и границ
10	~0	0	точный
32	~0.0001	0
100	1.2	0
Мой алгоритм решения ЗК
10	0.001	0	приближенный
32	2.5	0
100	6	0

* - ЗК з такою кількістю міст методом лексичного перебору сучасний комп'ютер не зміг би вирішити навіть за весь час існування Всесвіту.

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

1.5 Практичне застосування задачі комівояжера

Крім очевидного застосування ЗК на практиці, існує ще ряд завдань, приводяться до вирішення ЗК.

Завдання про виробництві фарб. Є виробнича лінія для виробництва n фарб різного кольору; позначимо ці фарби номерами 1,2 ... n. Всю виробничу лінію будемо вважати одним процесором .. Будемо вважати також, що одноразово процесор виробляє тільки одну фарбу, тому фарби потрібно виробляти в деякому порядку Оскільки виробництво циклічне, то фарби треба виробляти в циклічному порядку  = (j1, j2, .., jn , j1). Після закінчення провадження фарби i і перед початком виробництва фарби j треба відмити обладнання від фарби i. Для цього потрібен час C [i, j]. Очевидно, що C [i, j] залежить як від i, так і від j, і що, взагалі кажучи, C [i, j] ≠ C [j, i]. При деякому вибраному порядку доведеться на цикл виробництва фарб витратити час.

Таким чином, ЗК і завдання щодо мінімізації часу переналагодження - це просто одна задача, тільки варіанти її описані різними словами.

Завдання про діропробивні преси. Діропробивний прес справляє велике число однакових панелей - металевих листів, в яких послідовно по одному пробиваються отвори різної форми і величини. Схематично прес можна представити у вигляді столу, що рухається незалежно за координатами x, y, і обертового над столом диска, по периметру якого розташовані диропробивні інструменти різної форми і величини. Кожен інструмент є у одному примірнику. Диск може обертатися однаково в двох напрямках (координата обертання z). Мається власне прес, який натискає на підвішений під нього інструмент тоді, коли під інструмент підведена потрібна точка листа.

Операція пробивки j-того отвори характеризується четвіркою чисел (xj, yj, zj, tj),, де xj, yj- координати потрібного положення столу, zj - координата потрібного положення диска і tj - час пробивки j-того отвори.

Виробництво панелей носить циклічний характер: на початку і наприкінці обробки кожного аркуша стіл повинен знаходитися в положеннях (x0, y0) диск в положенні z0 причому в цьому положенні слив не пробивається. Це початковий стан системи можна вважати пробивкой фіктивного нульового отвори. З параметрами (x0, y0, z0,0).

Щоб пробити j-тое отвір безпосередньо після i-того необхідно зробити наступні дії:

1. Перемістити стіл по осі x з положення xi в положення xj, витрачаючи при цьому час t (x) (| xi-xj |) = ti, j (x)

Проробити те ж саме по осі y, витративши час ti, j (y)

Повернути головку по найкоротшій з двох дуг з положення zi в положення zj, витративши час ti, j (z).

Пробити j-тое отвір, витративши час tj.

Конкретний вид функцій t (x), t (y), t (z) залежить від механічних властивостей преса і досить громіздкий. Явно виписувати ці функції немає необхідності

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

С [i, j] = max (t (x), t (y), t (z))

Тепер, як і в попередньому випадку, завдання складання оптимальної програми для діропробивні преси зводиться до ЗК (тут - симетричною).