Завдання комівояжера

Введення

Комбінаторика - розділ математики, присвячений вирішенню задач вибору та розташування елементів деякого, зазвичай скінченної множини відповідно до заданих правил.

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

Великий внесок у систематичне розвиток комбінаторних методів був зроблений Г. Лейбніцем (дисертація «Комбінаторні мистецтво»), Я. Бернуллі (робота «Мистецтво припущень»), Л. Ейлером. Можна вважати, що з появою робіт Я. Бернуллі і Г. Лейб-ка комбінаторні методи виділилися в самостійну частину математики. У роботах Л. Ейлера по розбиття та композиціям натуральних чисел на складові було покладено початок одному з основних методів перерахування комбінаторних конфігурацій - методом генератрис.

Повернення інтересу до комбінаторного аналізу відноситься до 50-х років ХХ ст. у зв'язку з бурхливим розвитком кібернетики і дискретної математики і широким використанням електронно-обчислювальної техніки. У цей період активізувався інтерес до класичних комбінаторним завданням.

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

У 1859 р. У. Гамільтон придумав гру «Навколосвітня подорож», що складається в знаходженні такого шляху, що проходить через усі вершини (міста, пункти призначення) графа, зображеного на рис. 1, щоб відвідати кожну вершину одноразово і повернутися в початкову. Шляхи, що мають таку властивість, називаються гамильтонова циклу.

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

Завдання комівояжера. Загальний опис

Завдання комівояжера (надалі скорочено - ЗК) є однією із знаменитих задач теорії комбінаторики. Вона була поставлена ​​в 1934 році, і про неї, як про Велику теорему Ферма обламували зуби найкращі математики. У своїй області (оптимізації дискретних задач) ЗК служить своєрідним полігоном, на якому випробовуються всі нові методи.

Постановка завдання наступна.

Комівояжер (бродячий торговець) повинен вийти з першого міста, відвідати по разу в невідомому порядку міста 2,1,3 .. n і повернутися в перший місто. Відстані між містами відомі. У якому порядку слід обходити міста, щоб замкнутий шлях (тур) комівояжера був найкоротшим?

Щоб привести завдання до наукового увазі, введемо деякі терміни. Отже, міста перенумеровані числами jÎТ = (1,2,3 .. n). Тур комівояжера може бути описаний циклічної перестановкою t = (j1, j2, .., jn, j1), причому всі j1 .. jn - різні номери; повторюється на початку і в кінці j1, показує, що перестановка зациклена. Відстані між парами вершин Сij утворюють матрицю С. Завдання полягає в тому, щоб знайти такий тур t, щоб мінімізувати функціонал

Щодо математизувати формулювання ЗК доречно зробити два зауваження.

По-перше, у постановці Сij означали відстані, тому вони повинні бути невід'ємними, тобто для всіх jÎТ:

(Останнє рівність означає заборону на петлі в турі), симетричними, тобто для всіх i, j:

і задовольняти нерівності трикутника, тобто для всіх:

У математичній постановці йдеться про довільної матриці. Зроблено це тому, що є багато прикладних задач, які описуються основною моделлю, але всім умовам (2) - (4) не задовольняють. Особливо часто порушується умова (3) (наприклад, якщо Сij - не відстань, а плата за проїзд: часто туди квиток коштує одну ціну, а назад - іншу). Тому ми будемо розрізняти два варіанти ЗК: симетричну задачу, коли умова (3) виконано, і несиметричну - в іншому випадку. Умови (2) - (4) за замовчуванням ми будемо вважати виконаними.

Друге зауваження стосується числа всіх можливих турів. У несиметричною ЗК всі тури t = (j1, j2, .., jn, j1) і t '= (j1, jn, .., j2, j1) мають різну довжину і повинні враховуватися обидва. Різних турів очевидно (n-1)!.

Зафіксуємо на першому і останньому місці в циклічній перестановці номер j1, а що залишилися n-1 номерів переставимо усіма (n-1)! можливими способами. У результаті отримаємо всі несиметричні тури. Симетричних турів є в два раз менше, тому що кожен зарахований два рази: як t і як t '.

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

У термінах теорії графів симетричну ЗК можна сформулювати так:

Дана повна мережу з n вершинами, довжина ребра (i, j) = Сij. Знайти гамільтонів цикл мінімальної довжини.

У несиметричною ЗК замість «цикл» треба говорити «контур», а замість «ребра» - «дуги» або «стрілки».

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

1.2. Методи розв'язання ЗК

1.2.1. Жадібний алгоритм

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

Подивимося, як поведеться при вирішенні ЗК жадібний алгоритм. Тут він перетвориться в стратегію «йди до найближчого (до якого ще не входив) місто». Жадібний алгоритм, очевидно, безсилий у цьому завданні. Розглянемо для прикладу мережу на рис. 2, що представляє вузький ромб. Нехай комівояжер стартує з міста 1. Алгоритм «Іди ви найближче місто» виведе його в місто 2, потім 3, потім 4; на останньому кроці доведеться платити за жадібність, повертаючись по довгій діагоналі ромба. У результаті вийде не найкоротший, а довжелезний тур.

На користь процедури «йди до найближчого» можна сказати лише те, що при старті з одного міста вона не поступиться стратегії «йди в подальший».

Як бачимо, жадібний алгоритм помиляється. Чи можна довести, що він помиляється помірно, що отриманий ним тур гірше мінімального, приміром, у 1000 разів? Ми доведемо, що цього довести не можна, причому не тільки для жадібного логарифма, а для алгоритмів набагато більш потужних. Але спочатку потрібно домовитися, як оцінювати похибка неточних алгоритмів, для визначеності, в задачі мінімізації. Нехай fB - справжній мінімум, а fA - той квазімінімум, який отримано за алгоритмом. Ясно, що fA / fB ≥ 1, але це - тривіальне твердження, що може бути похибка. Щоб оцінити її, потрібно затиснути ставлення оцінкою зверху:

де, як зазвичай у вищій математиці, ε ≥ 0, але, проти звичаю, може бути дуже великим. Величина ε і буде служити мірою похибки. Якщо алгоритм мінімізації буде задовольняти нерівності (5), ми будемо говорити, що він має похибка ε.

Припустимо тепер, що є алгоритм А рішення ЗК, похибка якого потрібно оцінити. Візьмемо довільний граф G (V, E) і по ньому складемо вхідну матрицю ЗК:

Якщо в графі G є гамільтонів цикл, то мінімальний тур проходить по цьому циклу і fB = n. Якщо алгоритм А теж завжди буде знаходити цей шлях, то за результатами алгоритму можна судити, чи є гамільтонів цикл в довільному графі. Однак, неперебiрний алгоритм, який міг би відповісти, чи є гамільтонів цикл в довільному графі, до цих пір нікому не відомо. Таким чином, наш алгоритм А повинен іноді помилятися і включати в тур хоча б одне ребро довжини 1 + nε. Але тоді fA ³ (n-1) + (1 + nε) так що fA / fB = 1 + nε тобто перевершує похибка ε на задану нерівністю (5). Про величину ε в нашому міркуванні ми не домовлялися, так що ε може бути безпідставно великий.

Таким чином доведена наступна теорема.

Або алгоритм А визначає, чи існує в довільному графі гамільтонів цикл, або похибка А при вирішенні ЗК може бути безпідставно велика.

Це міркування було вперше опубліковано Сані і Гонзалес в 1980 р. Теорема Сані-Гонзалеса заснована на тому, що немає ніяких обмежень на довжину ребер. Теорема не проходить, якщо відстані підпорядковуються нерівності трикутника (4).

Якщо її дотримуються, можна запропонувати кілька алгоритмів з похибкою 12. Перш, ніж описати такий алгоритм, слід згадати старовинну головоломку. Чи можна накреслити однією лінією відкритий конверт? Рис.2 показує, що можна (цифри на відрізках показують порядок їх проведення). Закритий конверт (рис.3.) Однією лінією намалювати не можна і ось чому. Будемо називати лінії ребрами, а їх перехрестя - вершинами.

Коли через точку проводиться лінія, то використовується два ребра - одне для входу в вершину, одне - для виходу. Якщо ступінь вершини непарна - то в ній лінія повинна початися або скінчитися. На рис. 3 вершин непарної ступеня дві: в одній лінія починається, в іншій - кінчається. Однак на рис. 4 є чотири вершини ступені три, але в однієї лінії не може бути чотири кінця. Якщо ж потрібно прокреслити фігуру однією замкненою лінією, то всі її вершини повинні мати парну ступінь.

Вірно і зворотне твердження: якщо всі вершини мають парну ступінь, то фігуру можна намалювати однієї незамкненою лінією. Дійсно, процес проведення лінії може скінчитися, тільки якщо лінія прийде в вершину, звідки вже виходу немає: всі ребра, приєднані до цієї вершини (зазвичай кажуть: інцидентних цій вершині), вже прокреслені. Якщо при цьому намальована вся фігура, щось потрібне твердження доведено, а якщо ні, видалимо вже намальовану частина G '. Після цього від графа залишиться одна або кілька зв'язкових компонент; нехай G '- одна з таких компонент. У силу зв'язності вихідного графа G, G 'і G''мають хоч одну спільну вершину, скажімо, v. Якщо в G''видалені якісь ребра, то по парним числом від кожної вершини. Тому G''- зв'язний і всі його вершини мають парну ступінь. Побудуємо цикл в G''(може бути, не намалювавши всього G'') і через v додамо промальовувала частина G''до G '. Збільшуючи таким чином промальовувала частина G ', ми доб'ємося того, що G' охопить весь G.

Це завдання колись вирішив Ейлер, і замкнуту лінію, яка покриває всі ребра графа, тепер називаю ейлеровим циклом. По суті була доведена наступна теорема.

Ейлеров цикл в графі існує тоді і тільки тоді, коли (1) граф зв'язний і (2) всі його вершини мають парні ступеня.

1.2.2. Дерев'яний алгоритм.

Тепер можна обговорити алгоритм розв'язання ЗК через побудову найкоротшого кістяка. Для стислості буде називати цей алгоритм дерев'яним.

Спочатку обговоримо властивість випрямлення. Розглянемо яку-небудь ланцюг, наприклад, на рис.5. Якщо справедливо нерівність трикутника, то d [1,3] £ d [1,2] + d [2,3] і d [3,5] £ d [3,4] + d [4,5] Склавши ці два нерівності, отримаємо d [1,3] + d [3,5] £ d [1,2] + d [2,3] + d [3,4] + d [4,5]. За нерівності трикутника отримаємо. d [1,5] £ d [1,3] + d [3,5]. Остаточно

d [1,5] £ d [1,2] + d [2,3] + d [3,4] + d [4,5]

Отже, якщо справедливо нерівність трикутника, то для кожного кола вірно, що відстань від початку до кінця ланцюга менше (або дорівнює) сумарної довжини всіх ребер ланцюга. Це узагальнення розхожого переконання, що пряма коротше кривої.

Повернемося до ЗК і опишемо вирішальний її дерев'яний алгоритм.

Побудуємо на вхідний мережі ЗК найкоротший кістяк і подвоїмо всі його ребра. Отримаємо граф G - зв'язний і з вершинами, що мають лише парні ступеня.

Побудуємо Ейлером цикл G, починаючи з вершини 1, цикл задається переліком вершин.

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

Приклад 1. Дана повна мережа, показана на рис.5. Знайти тур жадібним і дерев'яним алгоритмами.

Рішення. Жадібний алгоритм (йди до найближчого міста з міста 1) дає тур 1 - (4) -3 - (3) -5 (5) -4 - (11) -6 - (10) -2 - (6) -1, де без дужок показані номери вершин, а в дужках - довжини ребер. Довжина туру дорівнює 39, тур показана на рис. 5.

2. Дерев'яний алгоритм спочатку будує кістяк, показане на рис. 6 штриховою лінією, потім Ейлером цикл 1-2-1-3-4-3-5-6-5-3-1, потім тур 1-2-3-4-5-6-1 завдовжки 43, який показаний суцільний лінією на рис. 6.

Теорема. Похибка дерев'яного алгоритму дорівнює 1.

Доказ. Візьмемо мінімальний тур довжини fB і вилучимо з нього максимальний ребро. Довжина вийшла гамильтоновой ланцюга LHC менше fB. Але цю ж ланцюг можна розглядати як кістяк, тому що цей ланцюг досягає всі вершини і не має циклів. Довжина найкоротшого кістяка LMT менше або дорівнює LHC. Маємо ланцюжок нерівностей

Але подвоєне дерево - воно ж Ейлером граф - ми звели до туру допомогою випрямлення, отже, довжина отриманого за алгоритмом туру задовольняє нерівності

Множачи (6) на два і з'єднуючи з (7), отримуємо ланцюжок нерівностей

Тобто 2fB> fA, тобто fA / fB> 1 + e; e = 1.

Теорема доведена.

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

Відомо ще декілька простих алгоритмів, які гарантують у гіршому випадку e = 1. Для того, щоб знайти серед них алгоритм точніше, зайдемо з іншого кінця і для початку опишемо «brute-force enumeration» - «перебір тваринною силою», як його називають в англомовній літературі. Зрозуміло, що повний перебір практично застосовується лише в задачах малого розміру. Нагадаємо, що ЗК з n містами вимагає при повному переборі розгляду (n-1)! / 2 турів в симетричній завданню і (n-1)! Турів у несиметричною, а факторіал, як показано в таблиці, зростає гнітюче швидко:

Щоб проводити повний перебір у ЗК, потрібно навчитися (зрозуміло, без повторень) генерувати всі перестановки заданого числа m елементів. Це можна зробити декількома способами, але найпоширеніший (тобто застосовний для переборних алгоритмів вирішення інших завдань) - це перебір у лексикографічному порядку.

Нехай є деякий алфавіт і набори символів алфавіту (літер), звані словами. Букви в алфавіті впорядковані: наприклад, у російській алфавіті порядок букв аμбμя (символ μ читається «передує)». Якщо заданий порядок букв, можна впорядкувати і слова. Скажімо, дано слово u = (u1, u2, .., um) - що складається з букв u1, u2, .., um - і слово v = (v1, v2, .., vb). Тоді якщо u1μv1, то й uμv, якщо ж u1 = v1, то порівнюють другий букви і т.д. Цей порядок слів і називається лексикографічним. Тому в російських словниках (лексиконів) слово «абажур» варто раніше слова «абака». Слово «бур» варто раніше слова «бура», тому що пробіл вважається попереднім будь букві алфавіту.

Розглянемо, скажімо, перестановки з п'яти елементів, позначених цифрами 1 .. 5. Лексикографічно перший перестановкою є 1-2-3-4-5, другий - 1-2-3-5-4, ..., останньою - 5-4-3-2-1. Потрібно усвідомити загальний алгоритм перетворення будь перестановки в безпосередньо наступну.

Правило таке: скажімо, дана перестановка 1-3-5-4-2. Потрібно рухатися по перестановці справа наліво, поки вперше не побачимо число, менше, ніж попереднє (у прикладі це 3 після 5). Це число, Pi-1 треба збільшити, поставивши замість нього якесь число з розташованих правіше, від Pi до Pn. Число більше, ніж Pi-1, безсумнівно, знайдеться, так як Pi-1 <Pi. Якщо є кілька великих чисел, то, очевидно, треба ставити менше з них. Нехай це буде Pj, j> i-1. Потім число Pi-1 і всі числа від Pi до Pn, не рахуючи Pj потрібно упорядкувати за зростанням. У результаті вийде безпосередньо наступна перестановка, у прикладі - 1-4-2-3-5. Потім вийде 1-4-2-5-3 (той же алгоритм, але спрощений випадок) і т.д.

Потрібно розуміти, що в ЗК з n містами не потрібні всі перестановки з n елементів. Тому що перестановки, скажімо, 1-3-5-4-2 і 3-5-4-2-1 (останній елемент з'єднаний з першим) задають один і той же тур, лічений спершу з міста 1, а потім з міста 3 . Тому потрібно зафіксувати початковий місто 1 і приєднувати до нього всі перестановки з інших елементів. Цей перебір дасть (n-1)! різних турів, тобто повний перебір у несиметричною ЗК (ми як і раніше будемо розрізняти тури 1-3-5-4-2 і 1-2-4-5-3).

Даний алгоритм описаний мовою Паскаль (див. Додатки).

Приклад 2. Вирішимо ЗК, поставлену в Прикладі 1 лексикографічним перебором. Наведена вище програма надрукує міста, складові кращий тур: 1-2-6-5-4-3 і його довжину 36.

Бажано удосконалити перебір, застосувавши розум. У наступному пункті описаний алгоритм, який реалізує просту, але широко застосовну і дуже корисну ідею.

1.2.3. Метод гілок і меж

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

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

Викладемо алгоритм Літтла на прикладі 1 попереднього розділу .. Повторно запишемо матрицю:

Нам буде зручніше трактувати Сij як вартість проїзду з міста i в місто j. Припустимо, що добрий мер міста j видав указ виплачувати кожному що в'їхали в місто комівояжеру 5 доларів. Це означає, що будь-який тур подешевшає на 5 доларів, оскільки в будь-якому турі потрібно в'їхати в місто j. Але оскільки всі тури рівномірно подешевшали, то колишній мінімальний тур буде і тепер коштуватиме менше за всіх. Добрий же вчинок мера можна представити як зменшення всіх чисел j-го стовпця матриці С на 5. Якби мер хотів спровадити комівояжерів з j-го міста і встановив нагороду за виїзд у розмірі 10 доларів, це можна було б висловити вирахуванням 10 з усіх елементів j-й того рядка. Це знову б змінило вартість кожного туру, але мінімальний тур залишився б мінімальним. Отже, доведена наступна лема.

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

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

Прочерки по діагоналі означають, що з міста i в місто i ходити не можна. Зауважимо, що сума констант приведення по рядках дорівнює 27, сума по стовпцях 7, сума сум дорівнює 34.

Тур можна задати системою з шести підкреслених (виділених іншим кольором) елементів матриці С, наприклад, такий, як показано на табл. 2. Підкреслення елемента означає, що в турі з i-го елемента йдуть саме в j-тий. Для туру з шести міст підкреслених елементів повинне бути шість, так як в турі з шести міст є шість ребер. Кожен стовпець повинен містити рівно один підкреслений елемент (у кожне місто комівояжер в'їхав один раз), в кожному рядку повинен бути тільки один підкреслений елемент (з кожного міста комівояжер виїхав один раз); крім того, підкреслені елементи повинні описувати один тур, а не кілька менших циклів. Сума чисел підкреслених елементів є вартість туру. На табл. 2 вартість дорівнює 36, це той мінімальний тур, який отримано лексикографічним перебором.

Тепер будемо розмірковувати від наведеної матриці на табл. 2. Якщо в ній вдасться побудувати правильну систему підкреслених елементів, тобто систему, що б трьом вищеописаним вимогам, і цими підкресленими елементами будуть лише нулі, то ясно, що для цієї матриці ми отримаємо мінімальний тур. Але він же буде мінімальним і для вихідної матриці С, тільки для того, щоб отримати правильну вартість туру, потрібно буде назад додати всі константи приведення, і вартість туру зміниться з 0 до 34. Таким чином, мінімальний тур не може бути менше 34. Ми отримали оцінку знизу для всіх турів.

Тепер приступимо до розгалуження. Для цього виконаємо крок оцінки нулів. Розглянемо нуль в клітці (1,2) наведеної матриці. Він означає, що ціна переходу з міста 1 в місто 2 дорівнює 0. А якщо ми не підемо з міста 1 в місто 2? Тоді все одно потрібно в'їхати в місто 2 за ціни, зазначені в другому стовпці; дешевше всього за 1 (з міста 6). Далі, все одно треба буде виїхати з міста 1 за ціну, зазначену в першому рядку; найдешевше в місто 3 за 0. Підсумовуючи ці два мінімуму, маємо 1 +0 = 1: якщо не їхати «по нулю» з міста 1 в місто 2, то треба заплатити не менше 1. Це і є оцінка нуля. Оцінки всіх нулів поставлені на табл. 5 правіше і вище нуля (оцінки нуля, рівні нулю, не ставилися).

Виберемо максимальну з цих оцінок (у прикладі є кілька оцінок, рівних одиниці, виберемо першу з них, у клітині (1,2)).

Отже, вибрано нульове ребро (1,2). Розіб'ємо всі тури на два класи - включають ребро (1,2) і не включають ребро (1,2). Про другий клас можна сказати, що доведеться доплатити ще 1, так що тури цього класу коштують 35 або більше.

Що стосується першого класу, то в ньому треба розглянути матрицю на табл. 6 з викресленою першим рядком і другим стовпцем.

Додатково в зменшеної матриці поставлений заборона в клітці (2,1), тому що вибрано ребро (1,2) і замикати передчасно тур ребром (2,1) не можна. Зменшену матрицю можна привести на 1 по одну колонку, так що кожен тур, їй відповідає, коштує не менше 35. Результат наших розгалужень і отримання оцінок зображений на рис.6.

Гуртки представляють класи: верхній гурток - клас всіх турів; нижній лівий - клас всіх турів, що включають ребро (1,2); нижній правий - клас всіх турів, що не включають ребро (1,2). Числа над кружками - оцінки знизу.

Продовжимо розгалуження в позитивну сторону: вліво - вниз. Для цього оцінимо нулі у зменшеній матриці C [1,2] на табл. 7. Максимальна оцінка в клітці (3,1) дорівнює 3. Таким чином, оцінка для правої нижньої вершини на рис. 7 є 35 +3 = 38. Для оцінки лівої нижньої вершини на рис. 7 потрібно викреслити з матриці C [1,2] ще рядок 3 і стовпець 1, отримавши матрицю C [(1,2), (3,1)] на табл. 8. У цю матрицю потрібно поставити заборону в клітку (2,3), тому що вже побудований фрагмент туру з ребер (1,2) і (3,1), тобто [3,1,2], і потрібно заборонити передчасне замикання (2,3). Ця матриця наводиться за стовпцем на 1 (табл. 9), таким чином, кожен тур відповідного класу (тобто тур, що містить ребра (1,2) і (3,1)) коштує 36 і більше.

Оцінюємо тепер нулі у наведеній матриці C [(1,2), (3,1)] нуль з максимальною оцінкою 3 знаходиться в клітці (6,5). Негативний варіант має оцінку 38 +3 = 41. Для отримання оцінки позитивного варіанту прибираємо рядок 6 і стовпець 5, ставимо заборона в клітку (5,6), див. табл. 10. Ця матриця непріводімих. Отже, оцінка позитивного варіанту не збільшується (рис.8).

Оцінюючи нулі в матриці на табл. 10, отримуємо розгалуження за вибором ребра (2,6), негативний варіант отримує оцінку 36 +3 = 39, а для отримання оцінки позитивного варіанту викреслюємо другий рядок і шостий стовпець, отримуючи матрицю на табл. 11.

У матрицю треба додати заборона в клітку (5,3), бо вже побудований фрагмент тури [3,1,2,6,5] і треба заборонити передчасний повернення (5,3). Тепер, коли залишилася матриця 2х2 із заборонами по діагоналі, добудовуємо тур ребрами (4,3) і (5,4). Ми не даремно гілкувалися, за позитивними варіантами. Зараз отриманий тур: 1 → 2 → 6 → 5 → 4 → 3 → 1 вартістю в 36. При досягненні низу по дереву перебору клас турів звузився до одного туру, а оцінка знизу перетворилася в точну вартість.

Отже, всі класи, що мають оцінку 36 і вище, кращого туру не містять. Тому відповідні вершини викреслюються. Викреслюються також вершини, обидва нащадка якої викреслені. Ми колосально скоротили повний перебір. Залишилося перевірити, чи не містить кращого туру клас, відповідний матриці З [Not (1,2)], тобто наведеної матриці С з забороною в клітці 1,2, наведеної на 1 по стовпцю (що дало оцінку 34 +1 = 35). Оцінка нулів дає 3 для нуля в клітці (1,3), так що оцінка негативного варіанту 35 +3 перевершує вартість вже отриманого туру 36 і негативний варіант відсікається.

Для отримання оцінки позитивного варіанту виключаємо з матриці перший рядок і третій стовпець, ставимо заборона (3,1) і отримуємо матрицю. Ця матриця приводиться по четвертій рядку на 1, оцінка класу сягає 36 і гурток закреслюється. Оскільки у вершини «все» вбиті обидва нащадка, вона побивається теж. Вершин не залишилося, перебір закінчений. Ми отримали той же мінімальний тур, який показаний підкресленням на табл. 2.

Задовільних теоретичних оцінок швидкодії алгоритму Літтла та споріднених алгоритмів немає, але практика показує, що на сучасних ЕОМ вони часто дозволяють вирішити ЗК з n = 100. Це величезний прогрес у порівнянні з повним перебором. Крім того, алгоритми типу гілок і меж є, якщо немає можливості доводити їх до кінця, ефективними евристичними процедурами.

1.2.4. Алгоритм Дейкстри

Одним з варіантів розв'язання ЗК є варіант знаходження найкоротшою ланцюга, що містить всі міста. Потім отримана ланцюг доповнюється початковим містом - виходить шуканий тур.

Можна запропонувати багато процедур вирішення цього завдання, наприклад, фізичне моделювання. На плоскій дошці малюється карта місцевості, в міста, що лежать на розвилці доріг, забиваються цвяхи, на кожен цвях надівається кільце, дороги укладаються мотузками, які прив'язуються до відповідних кільцям. Щоб знайти найкоротша відстань між i та k, потрібно взяти I в одну руку і k в іншу і розтягнути. Ті мотузки, які натягнуться і не дадуть розводити руки ширше і утворюють найкоротший шлях між i і k. Однак математична процедура, яка промоделірует цю фізичну, виглядає дуже складно. Відомі алгоритми простіше. Один з них - алгоритм Дейкстри, запропонований Дейкстри ще в 1959р. Цей алгоритм вирішує загальну задачу:

У орієнтованої, неориентированной чи змішаної (тобто такий, де частина доріг має односторонній рух) мережі знайти найкоротший шлях між двома заданими вершинами.

Алгоритм використовує три масиву з n (= числу вершин мережі) чисел кожен. Перший масив a містить мітки з двома значеннями: 0 (вершина ще не розглянута) та 1 (вершина вже розглянута); другий масив b містить відстані - поточні найкоротші відстані від vi до відповідної вершини, третій масив c містить номери вершин - k-й елемент ck є номер передостанній вершини на поточному найкоротшому шляху з vi у vk. Матриця відстаней Dik задає довжини дуг dik; якщо такої дуги немає, то dik присвоюється велика кількість Б, рівне «машинної нескінченності».

Тепер можна описати:

Алгоритм Дейкстри

1 (ініціалізація).

У циклі від одного до n заповнити нулями масив а; заповнити числом i масив з: перенести i-ту рядок матриці D в масив b;

a [i]: = 1; c [i]: = 0; {i-номер стартовою вершини}

2 (спільний крок).

Знайти мінімум серед невідміченим (тобто тих k, для яких a [k] = 0); нехай мінімум досягається на індексі j, тобто bj £ bk; a [j]: = 1;

якщо bk> bj + djk то (bk: = bj + djk; ck: = j) {Умова означає, що шлях vi .. vk довший, ніж шлях vi .. vj, vk. Якщо все a [k] відзначені, то довжина шляху vi .. vk дорівнює b [k]. Тепер треба перерахувати вершини, що входять в найкоротший шлях}

3 (видача відповіді).

{Шлях vi .. vk видається у зворотному порядку такої процедури:}

3.1. z: = c [k];

3.2. Видати z;

3.3. z: = c [z]; Якщо z = 0, то кінець, інакше перейти до 3.2.

Для виконання алгоритму потрібно n раз переглянути масив b з n елементів, тобто алгоритм Дейкстри має квадратичну складність. Проілюструємо роботу алгоритму Дейкстри чисельним прикладом (для більшої складності, вважаємо, що деякі міста (вершини) i, j не з'єднані між собою, тобто D [i, j] = ∞). Нехай, наприклад, i = 3. Потрібно знайти найкоротші шляхи з вершини 3. Вміст масивів a, b, c після виконання першого пункту показано на табл. 12:

Очевидно, вміст таблиці змінюється в міру виконання загального кроку. Це видно з наступної таблиці:

Таким чином, для вирішення ЗК потрібно n раз застосувати алгоритм Дейкстри наступним чином.

Візьмемо довільну пару вершин

j, k. Виключимо безпосереднє ребро C [j, k]. За допомогою алгоритму Дейкстри знайдемо найкоротша відстань між містами j.. K. Нехай це відстань включає деякий місто m. Маємо частина туру j, m, k. Тепер для кожної пари сусідніх міст (у даному прикладі - для j, m і m, k) видалимо відповідне ребро і знайдемо найкоротша відстань. При цьому в найкоротший відстань не повинен входити вже використаний місто.

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

1.2.5. Мій метод (метод Аніщенко) рішення задачі комівояжера

Я запропоную свій метод вирішення задачі комівояжера.

Розглянемо рис. 9-10 і спробуємо знайти в них найкоротші тури. Очевидно, що найкоротший тур не повинен містити пересічних ребер (в іншому випадку, помінявши вершини за пересічних ребрах місцями, отримаємо більш короткий тур). У першому випадку найкоротшим є тур 1-2-4-5-3-1, а в другому - тур 1-2-3-4-5-1. Аналізуючи безліч інших аналогічних розташувань п'яти і більше міст, можна зробити наступне загальне припущення:

1. Якщо можна побудувати опуклий багатокутник, по периметру якого лежать усі міста, то такий опуклий багатокутник є найкоротшим туром.

Проте не завжди можна побудувати опуклий багатокутник, по периметру якого лежали б усі міста. Велика ймовірність того, що деякі міста не увійдуть до опуклий багатокутник. Такі міста будемо називати «центральними». Так як побудувати опуклий багатокутник досить легко, то завдання зводиться до того, щоб включити в тур у вигляді опуклого багатокутника всі центральні міста з мінімальними втратами. Нехай є масив T [n +1], що містить в собі номери міст по порядку, які повинен відвідати комівояжер, тобто спочатку комівояжер повинен відвідати місто T [1], потім T [2], потім T [3] тощо . д,, причому T [n +1] = T [1] (комівояжер повинен повернутися в початковий місто). Тоді, якщо виконується рівність "i ∈ [1,2 .. n]; C [T [i], p] + C [p, T [i +1]] - C [T [I], T [i + 1]] = min, то центральний місто з номером p потрібно включити в тур між містами T [i] і T [i +1]. Виконавши цю операцію для всіх центральних міст, в результаті отримаємо найкоротший тур. Даний алгоритм можна реалізувати на мові Паскаль і перевірити вірність припущення 1. Для задачі, вирішеною нами методом гілок і меж, мій алгоритм дає правильне рішення.

Спробуємо вирішити даними алгоритмом ЗК для восьми міст. Нехай маємо вісім міст, розташування яких показано на рис. 11. Матриця відстаней наведена поруч на табл. 13. Проміжні побудови найкоротшого туру показані пунктирними лініями, цифри - порядок видалення ребер. Таким чином, маємо для даного випадку найкоротший тур 1-3-7-5-4-8-6-2-1. Довжина цього туру: D = 6 +7 +5 +2 +6 +5 +13 +13 = 57. Цей результат є правильним, тому що алгоритм лексичного перебору, який ніколи не помиляється, дає такий самий тур. (Слід також зазначити, що жадібний алгоритм для цього випадку помиляється лише на 1 і дає тур 1-3-4-5-7-8-6-2-1 довжиною в 58).

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

На основі вищевикладеного можна зробити висновок, що мій алгоритм, поряд з дерев'яним алгоритмом і алгоритмом Дейкстри, можна віднести до наближених (хоча за цим алгоритмом жодного разу не було помічено видачі неправильного варіанту).

1.2.6. Аналіз методів розв'язання задачі комівояжера

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

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

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

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

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

Завдання про виробництво фарб. Є виробнича лінія для виробництва n фарб різного кольору; позначимо ці фарби номерами 1,2 ... n. Всю виробничу лінію будемо вважати одним процесором .. Будемо вважати також, що одноразово процесор виробляє тільки одну фарбу, тому фарби потрібно виробляти в деякому порядку Оскільки виробництво циклічне, то фарби треба робити в циклічному порядку p = (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))

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

Висновки

Вивчено евристичний, наближений і точний алгоритми розв'язання ЗК. Точні алгоритми розв'язання ЗК - це повний перебір чи удосконалений перебір. Обидва вони, особливо перший, не ефективні при великому числі вершин графа.

Запропоновано власний ефективний метод розв'язання ЗК на основі побудови опуклого багатокутника і включення в нього центральних вершин (міст).

Проведено аналіз найбільш раціональних методів вирішення ЗК та визначені області їх ефективної дії: для малого числа вершин можна використовувати точний метод лексичного перебору; для великого числа вершин раціональніше застосовувати метод гілок і меж або метод автора роботи (Аніщенко Сергія Олександровича).

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

Наведено тексти програм, що дозволяють вирішити ЗК різними методами.

Список літератури

О. Оре Графи і їхнє застосування. Пер. з англ. під ред. І.М. Яглом. - М., «Світ», 1965, 174 с.

В. П. Сигорський. Математичний апарат інженера. - К., «Техніка», 1975, 768 с.

Ю. М. Кузнєцов, В. І. Кузубов, А. Б. Волощенко. Математичне програмування: навчальний посібник. 2-е вид. перераб. і доп. - М.; Вища школа, 1980, 300 с., Іл.

Є. В. Маркова, А. М. Лисенков. Комбінаторні плани в задачах багатофакторного експерименту. - М., Наука, 1979, 345 с.

Є. П. Ліпатов. Теорія графів та її застосування. - М., Знання, 1986, 32 с.

В. М. Бондарєв, В. І. Рублінецкій, Є. Г. Качко. Основи програмування. - Харків, Фоліо; Ростов на Дону, Фенікс, 1998, 368 с.

Ф. А. Новиков Дискретна математика для програмістів. - Санкт-Петербург, Пітер, 2001, 304 с., Іл.