Перегляд вихідного коду сторінки Задача комівояжера

[[Файл:TSP Deutschland 3.png|міні|Наведено найкоротший шлях комівояжера через 15 міст Німеччини. Всього існує 43589145600 <ref><math>\frac{14!}2=43\,589\,145\,600</math></ref> різних шляхів.]]
'''Зада́ча комівояже́ра''' ([[комівояжер]]&nbsp;— бродячий торговець; {{lang-en|Travelling Salesman Problem}}, TSP; {{lang-de|Problem des Handlungsreisenden}}) полягає у знаходженні найвигіднішого [[маршрут]]у, що проходить через вказані міста хоча б по одному разу. В умовах завдання вказуються критерій вигідності маршруту (найкоротший, найдешевший, сукупний критерій тощо) і відповідні матриці відстаней, вартості тощо. Зазвичай задано, що маршрут повинен проходити через кожне місто тільки один раз, в такому випадку розв'язок знаходиться серед [[гамільтонів цикл|гамільтонових циклів]].

Існує маса різновидів [[Узагальнена задача комівояжера|узагальненої постановки задачі]], зокрема геометрична задача комівояжера (коли матриця відстаней відображає [[відстань|відстані]] між точками на площині), трикутна задача комівояжера (коли на матриці вартостей виконується [[нерівність трикутника]]), симетрична та асиметрична задачі комівояжера.

Прості методи розв'язання задачі комівояжера: повний лексичний перебір, [[жадібний алгоритм|жадібні алгоритми]] ([[метод найближчого сусіда]]), метод включення найближчого міста, метод найдешевшого включення, метод [[Мінімальне кістякове дерево|мінімального кістяка дерева]]. На практиці застосовують різні модифікації ефективніших методів: [[метод гілок і меж]] і [[генетичний алгоритм|метод генетичних алгоритмів]], а так само [[Мурашиний алгоритм|алгоритм мурашиної колонії]].

Всі ефективні (такі, що скорочують повний перебір) методи розв'язання задачі комівояжера&nbsp;— [[Евристичний алгоритм|евристичні]]. У більшості евристичних методів знаходиться не найефективніший маршрут, а наближений розв'язок. Користуються популярністю так звані ''any-time алгоритми'', тобто алгоритми, що поступово покращують деякий поточний наближений розв'язок.

Задача комівояжера&nbsp;— [[NP-повна задача|NP-повна]]. Часто на ній проводять випробування нових підходів до евристичного скорочення повного перебору.

== Історія ==

Невідомо, коли проблему комівояжера було досліджено вперше. Однак, відома видана в [[1832]] році книжка з назвою «Комівояжер&nbsp;— як він має поводитись і що має робити для того, аби доставляти товар та мати успіх в своїх справах&nbsp;— поради старого Кур'єра» ({{lang-de|Der Handlungsreisende – wie er sein soll und was er zu thun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur}}), в якій описано проблему, але математичний апарат для її розв'язання не застосовується. Натомість, в ній запропоновано приклади маршрутів для деяких регіонів [[Німеччина|Німеччини]] та [[Швейцарія|Швейцарії]].

[[Файл:WilliamRowanHamilton.jpeg|thumb|Вільям Роуен Гамільтон]]
[[File:HasslerWhitney-April1973.jpg|thumb|Гаслер Вітні, 1973]]

Раннім варіантом задачі є гра «[[Ікосіан]]» [[Гамільтон Вільям Роуен|Вільяма Гамільтона]] [[XIX століття]], яка полягала в тому, щоб знайти маршрути на [[граф (математика)|графі]] з 20 вузлами. Перші згадки як математичної задачі на оптимізацію належать {{iw2|Карл Менґер (математик)|Карлу Менґеру||Karl Menger}} ({{lang-de|Karl Menger}}), який сформулював її в математичному колоквіумі в [[1930]] році так:
<blockquote>
Ми називаємо проблемою гінця (оскільки це питання виникає в кожного листоноші, зокрема, її вирішують багато мандрівників) завдання віднайти найкоротший шлях між скінченною множиною місць, відстань між якими відома.
{{приховати|у оригиналі}}
Wir bezeichnen als ''Botenproblem'' (weil diese Frage in der Praxis von jedem Postboten, übrigens auch von vielen Reisenden zu lösen ist) die Aufgabe, für endlich viele Punkte, deren paarweise Abstände bekannt sind, den kürzesten die Punkte verbindenden Weg zu finden. Dieses Problem ist natürlich stets durch endlich viele Versuche lösbar. Regeln, welche die Anzahl der Versuche unter die Anzahl der Permutationen der gegebenen Punkte herunterdrücken würden, sind nicht bekannt. Die Regel, man solle vom Ausgangspunkt erst zum nächstgelegenen Punkt, dann zu dem diesem nächstgelegenen Punkt gehen usw., liefert im allgemeinen nicht den kürzesten Weg.<ref name=schr>Alexander Schrijver. On the history of combinatorial optimization (till 1960). In: Handbook of Discrete Optimization (K. Aardal, G.L. Nemhauser, R. Weismantel, eds.), Elsevier, Amsterdam, 2005, pp. 1–68</ref>
|}
</blockquote>
Невдовзі з'явилась відома зараз назва ''задача мандруючого продавця'' ({{lang-en|Traveling Salesman Problem}}), яку запропонував {{iw2|Гаслер Вітні|||Hassler Whitney}} з [[Принстонський університет|Принстонського Університету]].<ref name=schr/>

Разом із простотою визначення та порівняною простотою знаходження ''гарних'' розв'язків задача комівояжера відрізняється тим, що визначення насправді оптимального шляху є досить складним завданням. Зважаючи на ці властивості, починаючи з другої половини [[20 століття|20-го століття]], дослідження задачі комівояжера, має не так практичний сенс, як теоретичний у ролі моделі для розробки нових алгоритмів оптимізації.

Багато сучасних поширених методів [[дискретна оптимізація|дискретної оптимізації]], таких як метод діленням площиною{{джерело}}, [[Метод гілок і меж|гілок та границь]] та різноманітні варіанти евристичних алгоритмів було розроблено на прикладі задачі комівояжера.

В 1950-ті та [[1960-ті]] роки задача комівояжера привернула увагу науковців в США та Європі. Важливий внесок в дослідження задачі належить Джорджу Данцігу ({{lang-en|George Dantzig}}), Делберту Рею Фалкерсону ({{lang-en|Delbert Ray Fulkerson}}) та Селмеру Джонсону ({{lang-en|Selmer M. Johnson}}), котрі в [[1954]] році в інституті [[RAND|RAND Corportation]] сформулювали задачу у вигляді задачі дискретної оптимізації та розробили метод відсікаючої площини для її розв'язання. Використовуючи новий метод вони обчислили шлях для окремого набору вузлів (екземпляру проблеми) з 49 міст та довели, що не існує коротшого шляху. В [[1960-ті]] та [[1970-ті]] роки численні групи дослідників вивчали задачу з точки зору математики та її застосування, наприклад, в [[інформатика|інформатиці]], [[економіка|економіці]], [[хімія|хімії]] та [[біологія|біології]].

[[Річард Карп]] ({{lang-en|Richard M. Karp}}) в [[1972]] році довів [[NP-повна задача|NP-повноту]] задачі пошуку [[Гамільтонів шлях|гамільтонових шляхів]], із чого, через поліноміальну зводимість, випливала NP-повнота задачі комівояжера. На основі цих властивостей ним було наведено теоретичне обґрунтування складності пошуку розв'язків задачі на практиці.

Більших успіхів вдалося досягнути наприкінці 1970-х та 1980-х років, коли Мартін Ґрьотчел ({{lang-de|Martin Grötschel}}), Манфред Падберґ ({{lang-de|Manfred Padberg}}) та Ґіованні Рінальді ({{lang-de|Giovanni Rinaldi}}) та інші, із застосуванням нових методів відсікаючої площини, гілок та границь обчислили розв'язок для окремого екземпляру задачі з 2393 містами.

В [[1990-ті]] роки Девід Аплгейт ({{lang-en|David Applegate}}), Роберт Біксбі ({{lang-en|Robert Bixby}}), [[Вацлав Хватал|Вашек Хватал]] та Вільям Кук ({{lang-en|William Cook}}) встановили рекорди з програмою [[Конкорд (програма)|Конкорд]]. Ґерхард Райнельт ({{lang-de|Gerhard Reinelt}}) створив TSPLIB&nbsp;— набір стандартизованих екземплярів задачі комівояжера різного ступеня складності для порівняння результатів роботи різних груп дослідників. В березні [[2005]] року задачу з 33&nbsp;810 вузлами було розв'язано програмою Конкорд: було обчислено шлях завдовжки 66&nbsp;048&nbsp;945 та доведено відсутність коротших шляхів. В квітні [[2006]] було знайдено розв'язок для екземпляру з 85&nbsp;900 вузлами. Використовуючи методи декомпозиції можливо обчислити розв'язки для екземплярів задачі з мільйонами вузлів довжина яких менш ніж на 1 % більша за оптимальний.

== Формальне визначення ==

=== Подання у вигляді графа ===

[[Файл:Weighted_K4.svg|thumb|Симетрична задача для чотирьох міст.]]

Для можливості застосування математичного апарату для розв'язання проблеми, її слід представити у вигляді [[математична модель|математичної моделі]]. Проблему комівояжера можна представити у вигляді моделі на [[граф (математика)|графі]], тобто, використовуючи вершини та ребра між ними. Таким чином, вершини графа (на мал.: від A до D) відповідають містам, а ребра <math>\left ( i,j \right )</math> між вершинами <math>i</math> та <math>j</math> сполучення між цими містами. У відповідність кожному ребру <math>\left ( i,j \right )</math> можна зіставити вагу <math>c_{ij} \geqslant  0</math> (на мал.: 20, 42, …), яку можна розуміти як, наприклад, відстань між містами, час або вартість подорожі. ''Маршрутом'' (також гамільтоновим маршрутом) називається [[маршрут (теорія графів)|маршрут]] на цьому графі до якого входить по одному разу кожна вершина графа. Задача полягає у відшуканні найкоротшого маршруту.

З метою спрощення задачі та гарантії існування маршруту, зазвичай вважається, що модельний граф задачі є [[повний граф|повним]], тобто, що між довільною парою вершин існує ребро. Це можна досягти тим, що в тих випадках, коли між окремими містами не існує сполучення, вводити ребра з максимальною вагою (довжиною, вартістю тощо). Через велику довжину таке ребро ніколи не потрапить до оптимального маршруту, якщо він існує.

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

==== Асиметрична та симетрична задачі ====

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

У випадку ''симетричної задачі'' всі пари ребер між одними й тими самими вершинами мають однакову вагу, тобто, для ребра <math>\left ( i,j \right )</math> ваги однакові <math>c_{ij} = c_{ji}</math>. Як наслідок, всі маршрути мають однакову довжину в обидва напрямки. В симетричному випадку кількість можливих маршрутів вдвічі менша за асиметричний випадок. Симетрична задача моделюється [[Граф (математика)#Визначення|неорієнтованим графом]] (як показано на малюнку).

Насправді, задача комівояжера у випадку реальних міст може бути як симетричною, так і асиметричною в залежності від тривалості або довжини маршрутів в залежності від напряму руху.

==== Метрична задача ====

Симетричну задачу комівояжера називають ''метричною'', якщо відносно довжин ребер виконується [[нерівність трикутника]]. Умовно кажучи, в таких задачах обхідні шляхи довші за прямі, тобто, ребро від вершини <math>i</math> до вершини <big>j</big> ніколи не довше за шлях через проміжну вершину <big>k</big>:

{{center| <math>c_{ij} \leqslant  c_{ik} + c_{kj}</math> }}

Така властивість довжини ребер визначає [[вимірна множина|вимірний простір]] на множині ребер та міру віддалі, що задовольняє інтуїтивне розуміння відстані.

Поширені на практиці функції віддалі є також метриками і задовольняють нерівності трикутника:
* [[Евклідова відстань]] в ''евклідовій задачі комівояжера'',
* [[Манхеттенська метрика]] (також квартальна метрика) ''прямокутної задачі комівояжера'', в якій відстань між вершинами на ґратці дорівнює сумі відстаней вздовж осі ординат та абсцис,
* [[Відстань Чебишова]], яка визначає віддаль між вершинами решітчастого графа як максимальне значення відстані вздовж осі ординат та абсцис.
Дві останні метрики знаходять застосування, наприклад, під час свердління отворів в [[друкована плата|друкованих платах]] коли верстат має зробити якнайбільше отворів за найменший час і може пересувати свердло незалежно в обох напрямах для переходу від одного отвору до наступного. Манхеттенська метрика відповідає випадку, коли пересування в обох напрямах відбувається послідовно, а максимальна&nbsp;— випадку коли пересування в обох напрямах відбувається синхронно а загальний час дорівнює максимальному часу пересування вздовж осі ординат або абсцис.

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

Якщо, на практиці, в умовах задачі дозволяється відвідувати міста декілька раз, то симетричну задачу можна звести до метричної. Для цього задачу розглядають на так званому ''графі відстаней''. Цей граф має таку саму множину вершин як і вихідний та, на доданок, є повністю зв'язним. Вага ребер <math>c_{ij}</math> між вершинами <math>i</math> та <math>j</math> на графі відстаней відповідає вазі найліпшого сполучення між вершинами <math>i</math> та <math>j</math> у вихідному графі. Для визначених в такий спосіб ваг <math>c_{ij}</math> виконується нерівність трикутника, і кожному маршруту на графі відстаней завжди відповідає маршрут з можливими повтореннями вершин у вихідному графі.

=== Формулювання у вигляді задачі дискретної оптимізації ===

Одним з підходів до розв'язання задачі є формулювання її у вигляді задачі [[дискретна оптимізація|дискретної оптимізації]], при цьому розв'язки представляються у вигляді змінних, а зв'язки у вигляді відношень [[нерівність|нерівності]] між ними. Таким чином, можливо декілька варіантів. Наприклад, симетричну задачу можна представити у вигляді множини ребер <math>V</math>. Кожному ребру <math>\{i, j\}</math> зіставляється двійкова змінна <math>x_{ij} \in \{0,1\}</math>, яка дорівнює 1 якщо ребро належить маршруту та 0 в протилежному випадку. Довільний маршрут можна представити у вигляді значень множини змінних приналежності, але не кожна така множина визначає маршрут. Умовою того, що значення множини змінних визначають маршрут є описані далі лінійні нерівності.

[[Файл:TSP_degree_constraints.png|thumb|Умова кратності: кожна вершина повинна мати одне вхідне та одне вихідне ребро маршруту.]]

Кожна вершина має сполучатись через пару ребер з рештою вершин, тобто, через вхідне та вихідне ребро:
: <math>\forall i \in V,\; \sum_{j \in V \setminus \{i\}} x_{ij} = 2 \qquad (1)</math>
В [[сума|сумі]] кожний [[доданок]] <math>x_{ij}</math> дорівнює або 1 (належить маршруту) або 0 (не належить). Тобто, отримана сума дорівнює кількості ребер в маршруті, таких що мають вершину <math>i</math> на одному з кінців. Вона дорівнює 2, оскільки кожна вершина має вхідне та вихідне ребро. У наведеному поруч малюнку вершина <math>i</math> показана з вхідним та вихідними ребрами, а ребра маршруту відмічено товстішими лініями. Поруч з ребрами вказано ваги <math>x_{ij}</math> що додаються до вказаної вище суми.

[[Файл:TSP_short_cycles.png|thumb|Цикли: змінні задовольняють умові кратності, але не визначають маршрут.]]

Описані раніше ''умови кратності'' виконуються не лише маршрутами, а й значеннями змінних, що відповідають відокремленим циклам, де кожна вершина належить лише одному циклу (див. малюнок). Аби уникнути подібні випадки, мають виконуватись так звані ''нерівності циклів'' (або ''умови усунення підмаршрутів''), які було визначено Данциґом, Фалкерсоном та Джонсоном в [[1954]] році під назвою ''умови петель'' ({{lang-en|loop conditions}}). Цими нерівностями визначалась додаткова умова того, що кожна множина вершин <math>S \subset V</math>, є або порожньою, або містить всі вершини, що сполучається з рештою вершин через щонайменше два ребра:

: <math>\sum_{i \in S, \; j \notin S} x_{ij} \geq 2 \qquad (2)</math>

для всіх множин вершин <math>S</math> де <math>1 \leq |S| \leq |V|-1</math>. Ця сума дорівнює сумі ваг ребер маршруту між вершиною <math>i \in S</math> та вершиною <math>j \notin S</math>. Аби усунути зайві нерівності, можна обмежитись множинами вершин <math>S</math> з щонайменше двома та щонайбільше <math>|V| - 2</math> вершинами. На малюнку поруч ребра <math>\{i,j\}</math> з вагами <math>x_{ij} = 1</math> відмічено товстішими лініями а решта ребер має вагу <math>x_{ij} = 0</math>. Введення додаткових умов (2) для множини вершин <math>S</math>, що складається з трьох лівих вершин, буде гарантувати, щоб <math>S</math> сполучалась через щонайменше два ребра маршруту з трьома вершинами справа, аби усунути обидва цикли. Кількість нерівностей усунення циклів відповідно до Данциґа, Фалкерсона та Джонсона дорівнює <math>2^{n}-2(n-1)</math>.

В [[1960]] році Міллєр ({{lang-en|Miller}}), Такер ({{lang-en|Tucker}}) та Землін ({{lang-en|Zemlin}}) винайшли альтернативні умови усунення підшляхів шляхом введення <math>n</math> нових змінних, що визначають порядок відвіданих міст, що потребує лише <math>n^2 - n + 1</math> додаткових нерівностей. Більше того, через двійковість <math>x_{ij}</math> у формулюванні Міллєра, Такера та Земліна задача комівояжера залишається NP-складною.

Так, кожен вектор <math>x=(x_{ij})_{i,j \in V}</math> з елементами, що дорівнюють 0 та 1, що задовольняє всім нерівностям визначає коректний маршрут, що є розв'язком переформульованої задачі комівояжера: обчислити
: <math>\min \; \left\{ \sum_{i \in V} \sum_{j \in V \setminus \{i\}} c_{ij} x_{ij} \;|\; x \mbox{ valid (1) (2),}\; x_{ij} \in \{0,1\} \right\}. \qquad (3)</math>

Оскільки змінні <math>x_{ij}</math> мають значення лише 0 та 1, сума дорівнює загальній довжині <math>c_{ij}</math> ребер <math>\{i,j\}</math> що належать маршруту.

Кількість нерівностей типу (2) зростає експоненційно разом зі збільшенням кількості міст, оскільки майже кожна з <math>2^{|V|}</math> підмножин вузлів визначає одну нерівність. Цю проблему можна вирішити застосуванням методу відсічення площиною завдяки якому нерівності додаються лише тоді, коли ці нерівності дійсно необхідні. З геометричної точки зору, лінійні нерівності можна представити як гіперплощину в просторі змінних. Множина векторів, що задовольняють цим нерівностям утворюють в такому просторі політоп (багатовимірний багатогранник), або багатовимірний багатокутник, точна форма визначається вагами <math>c_{ij}</math> і є в основному невідомим. Однак, можна показати, що умови (1) та (2) визначають грані (фацети) політопа, тобто, бічні поверхні політопа з найвищою розмірністю. Тому вони належать до найсильніших лінійних нерівностей, що можуть описувати маршрут. Також існує багато різних граней, що визначаються нерівностями, відомими лише у небагатьох випадках. Хоча (1) та (2) разом з обмеженнями повністю моделюють проблему лише для двійкових векторів, ці нерівності можуть використовуватись в [[метод гілок і меж|методі гілок і меж]] аби відкинути розв'язки методами лінійної оптимізації з не цілими координатами (див. [[#Точні методи|розділ точні методи]] нижче).

== Алгоритмічна складність ==

Оскільки комівояжер в кожному з міст постає перед вибором наступного міста з тих, що він ще не відвідав, існує <math>(n-1)!</math> маршрутів для асиметричної та <math>(n-1)!/2</math> маршрутів для симетричної задачі комівояжера. Таким чином, розмір простору пошуку залежить над-експоненційно від кількості міст.

Різні варіанти задачі комівояжера (метричний, симетричний та асиметричний) є [[NP-еквівалентність|NP-еквівалентними]]. Відповідно до поширеної але недоведеної гіпотези про нерівність класів складності [[Клас складності P|P]] та [[Клас складності NP|NP]] не існує детермінованої машини Тюринга, здатної знаходити розв'язки екземплярів задачі за [[поліноміальний час]] в залежності від кількості міст.

Також відомо, що за умови <math>P \neq NP</math> не існує алгоритму, що для деякого поліному <math>p</math> обчислював би такі розв'язки задачі комівояжера, що відрізнялись би від оптимального щонайбільше на коефіцієнт <math>2^{p(n)}</math>.{{джерело}}

Однак, існують алгоритми пошуку наближених розв'язків для метричної задачі за поліноміальний час, і знайдений маршрут щонайбільше вдвічі (наприклад, 1.5 для алгоритму Христофіда, {{lang-de|Christofides}}) довший за оптимальний. Досі не відомий жоден алгоритм з поліноміальним часом, який би гарантував точність кращу за 1.5 від оптимального. За припущенням <math>P \neq NP</math>, існує (невідома) константа <math>c > 0</math>, така, що жоден алгоритм з поліноміальним часом не може гарантувати точність <math>1 + c</math>. Як було показано Арора, для евклідової задачі комівояжера існує схема пошуку приблизних розв'язків задачі (PTAS).

== Методи розв'язання ==

Відомі методи розв'язання поділяють на дві групи, що можна комбінувати. ''Точні методи'' знаходять, маючи достатньо часу, гарантовано оптимальний шлях. ''Евристичні методи'' знаходять, часто за коротший час, гарні розв'язки, що, в загальному випадку, можуть бути гіршими за оптимальні. Для метричної задачі існують евристики, що знаходять за поліноміальний час розв'язки гірші за оптимальні у 1.5—2 рази.{{джерело}}

=== Точні методи ===
{{main|Метод гілок і меж}}

Можна знайти точний розв'язок задачі комівояжера, тобто, обчислити довжини всіх можливих маршрутів та обрати маршрут з найменшою довжиною. Однак, навіть для невеликої кількості міст в такий спосіб задача практично нерозв'язна. Для простого варіанта, симетричної задачі з <math>n</math> містами, існує <math>(n-1)!/2</math> можливих маршрутів, тобто, для 15 міст існує 43 [[мільярд]]ів маршрутів та для 18 міст вже 177 [[більйон]]ів. Те, як стрімко зростає тривалість обчислень можна показати в наступному прикладі. Якщо існував би пристрій, що знаходив би розв'язок для 30 міст за годину, то для двох додаткових міст в тисячу раз більше часу; тобто, більш ніж 40 діб.

[[Файл:TSP_cutting_plane.png|thumb|Задача комівояжера для трьох міст: червона площина <math>x_1 + x_2 + x_3 \geqslant 2</math> відкидає всі неприпустимі розв'язки з щонайбільше одним ребром. Всі точки в червоному політопі задовільняють цій нерівності, і єдина припустима точка це (1, 1, 1).]]

Методи [[дискретна оптимізація|дискретної оптимізації]], зокрема [[Метод гілок і меж|гілок і меж]] дозволяють знаходити оптимальні або приблизні розв'язки для достатньо великих задач.

В геометричній інтерпретації, ці методи розглядають задачу як [[опуклий багатокутник|опуклий]] [[політоп]], тобто, багатовимірний багатокутник в <math>m</math>-вимірному одиничному кубі <math>[0,1]^m</math>, де <math>m</math> дорівнює кількості ребер в графі. Кожне ребро цього одиничного куба відповідає маршруту, тобто, вектору з елементами 0/1, що задовольняє описаним вище лінійним нерівностям. Гіперплощини, що описуються цими нерівностями відсікають такі ребра одиничного куба, що не відповідають жодному маршруту.

На малюнку поруч показано застосування методу для задачі з трьома вузлами. У відповідність трьом можливим ребрам між вершинами зіставляються бінарні змінні <math>x_1,\, x_2</math> та <math>x_3</math>. В цьому випадку існує лише один можливий маршрут, а саме той, що проходить через три вершини. Цей маршрут задовольняє нерівності <math>x_1 + x_2 + x_3 \geqslant 2</math>, що стверджує, що маршрут повинен проходити через щонайменше дві вершини. Окрім цього маршруту, що відповідає вектору (1,1,1), задовольняють нерівності також всі точки у відміченому червоним регіоні цієї нерівності. Площини, що проходять через червоні лінії відсікають всі кути, що відповідають неіснуючим маршрутам із щонайбільше одним ребром, а саме, нуль-вектор (0, 0, 0), [[одиничний вектор|одиничні вектори]] (1, 0, 0), (0, 1, 0) та (0, 0, 1). Сильніша нерівність <math>x_1 + x_2 + x_3 \geqslant 3</math> відсіче від одиничного куба все, окрім єдиної припустимої точки (1, 1, 1). В цьому окремому випадку можна досягти трьома нерівностями типу (1).

Для визначення припустимого ребра з найменшою вартістю слід розв'язати набори [[Лінійне програмування|задач лінійної оптимізації]], що відсікають січними площинами непотрібні частини одиничного куба (наприклад, типу (2), або ''нерівностями доміно-парності''<ref name=CookEspinozaGoycoolea2005>William Cook, Daniel Espinoza, Marcos Goycoolea: ''[http://www2.isye.gatech.edu/~wcook/papers/DP_paper.pdf Computing with Domino-Parity Inequalities for the TSP.] {{Webarchive|url=https://web.archive.org/web/20120220012854/http://www2.isye.gatech.edu/~wcook/papers/DP_paper.pdf |date=20 лютого 2012 }}'' 2005. (Preprint, pdf)</ref>) та спробувати поділити одиничний куб на менші політопи [[метод гілок і меж|методом гілок і меж]]. Повніше описання цих методів можна знайти в статті про [[дискретна оптимізація|дискретну оптимізацію]].

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

Маючи нижню границю для оптимальних розв'язків можна оцінити те, наскільки відрізняється знайдений маршрут від оптимального. Наприклад, маючи нижню границю на рівні 100, та після знаходження маршруту вартістю 102, оптимальний маршрут може знаходитись в межах від 100 до 102. Так званий ''інтервал оптимальності'', або максимальна відносна відстань між вартістю оптимального маршруту та найдешевшим відомим маршрутом становитиме (102—100)/100 = 2 %, тобто вартість знайденого маршруту 102 щонайбільше на 2 % відрізняється від оптимальної. Коли вартість обчисленого маршруту дорівнює вартості попереднього, вважається, що знайдений розв'язок є оптимальним. Для пошуку маршрутів прийнятної довжини точні методи можуть комбінуватись з евристичними, деякі з них описано нижче.

=== Евристичні методи ===

Для пришвидшення пошуку прийнятних маршрутів можна використовувати [[евристика|евристики]], що, в загальному випадку, не гарантують точності знайдених розв'язків. В залежності від того, чи обчислює евристика новий маршрут, чи намагається покращити вже існуючий, евристики поділяють на ''конструктивні'' та ''ітеративні'' евристики. Крім того, відрізняють ''дуальні'' евристики, та ''метаевристики''.

==== Конструктивні евристики ====
==== Ітеративні евристики ====

Ітеративні евристики (також ''після оптимізаційні евристики'') намагаються шляхом деяких змін скоротити вже обчислений маршрут. Прикладом такої евристики є [[k-opt-евристика|k-opt-евристики]], що систематично видаляють з маршруту групи з <math>k</math> ребер і замінюють їх іншими <math>k</math> ребрами отримуючи новий маршрут. Оскільки повний перебір можливих варіантів дорівнює кількості можливих маршрутів, на практиці обмежують <math>k</math> щонайбільше до 5. При цьому, випробовуються всі варіанти заміни двох та трьох ребер, уникаючи перебору з більшою кількістю ребер через значні витрати часу.

На практиці, ефективність k-opt-евристики сильно залежить від вибору ребер для заміни та параметру <math>k</math>, для вибору яких існують різні евристичні критерії. Однією з відомих, основаних на принципах k-opt, евристик є розроблена в 1973 році Брайаном Керніганом та С. Ліном ''евристика Ліна-Кернігана''. Реалізація Кельда Гельсгауна<ref name=Helsgaun2000>Keld Helsgaun: ''[http://www.akira.ruc.dk/~keld/research/LKH/LKH-1.3/DOC/LKH_REPORT.pdf An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic.] {{Webarchive|url=https://web.archive.org/web/20090928101849/http://www.akira.ruc.dk/~keld/research/LKH/LKH-1.3/DOC/LKH_REPORT.pdf |date=28 вересня 2009 }}'' In: European Journal of Operational Research. Amsterdam 126.2000, Nr. 1, S.106-130. {{ISSN|0377-2217}}</ref> серед іншого була використана для пошуку оптимального розв'язку задачі комівояжера з 24&nbsp;978 містами [[Швеція|Швеції]] в [[2004]] році. Ця евристика полягає в тому, щоб перебрати можливі заміни з двома ребрами, потім з трьома, і так далі, поки не буде виконано один із багатьох критеріїв зупинки.

==== Метаевристичні методи ====

Метаевристичні методи комбінують методи пошуку локальних та глобальних розв'язків у абстрактні стратегії евристичної оптимізації задач. Багато методів цього типу базуються на методах пошуку локальних розв'язків, тобто, вони обчислюють деякий початковий розв'язок (наприклад, застосовуючи [[метод найближчого сусіда]]) та покращують його іншими методами, наприклад, методом k-opt-евристики, доти, поки неможливо буде знайти кращий маршрут. Використовуючи різні стратегії, такі, як, наприклад, [[табуйований пошук]] або [[алгоритм імітації відпалу|симуляції відпалу]], можна спробувати уникнути глухих кутів під час пошуку локальних мінімумів. Інші методи, такі як [[мурашиний алгоритм]], [[генетичний алгоритм|генетичні алгоритми]] або [[штучні нейронні мережі]] (перш за все [[Нейронна мережа Хопфілда|мережа Хопфілда]]) використовують як шаблон природні процеси. В принципі, цими методами можна знаходити як досить якісні розв'язки так і досить віддалені від оптимального. Якість результатів та тривалість обчислення залежать від визначення та реалізації окремих елементів.

==== Дуальні евристики ====
==== Огляд ====

=== Практичні методи обчислення ===

== Варіанти та застосування ==
[[File:ANT Antenna 1.jpg|thumb|Петльові антенні вібратори формату 10×10, синтезовані на основі розв'язку задачі комівояжера]]
Задача комівояжера може застосовуватись для широкого спектра задач, в основі яких лежить проходження певного об'єкту через множину пунктів так, щоб закінчення шляху збігалося з початком.

Прикладами задач в яких доцільне застосування даного методу є:
# В ході планування робіт для кур'єра з доставки товарів. Планування маршруту проходження кур'єром пунктів доставки товару.
# В ході планування робіт для однієї машини. Планування маршруту від пункту початку(автостоянки) до пункту з запасами(складом) та подальше проходження всіх пунктів з потребами, з поверненням машини в кінці зміни на місце початку робіт.

Прикладом застосування розв'язку задачі комівояжера для 100 міст є синтез петльових та непетльових антенних вібраторів формату 10x10 за допомогою [[мурашиний алгоритм|мурашиного алгоритму]] оптимізації.<ref name=slyusarant>{{статья|автор=Ермолаев С.Ю., Слюсар В.И.|заглавие= Синтез антенн на основе муравьиных алгоритмов оптимизации. // 19-я Международная Крымская конференция «СВЧ-техника и телекоммуникационные технологии» (КрыМиКо’2009). Материалы конференции.- Севастополь, 14-18 сентября |ссылка=http://slyusar.kiev.ua/CriMiCo2009.pdf|год=2009|страницы= 431 - 432}}</ref><ref name=slyusarant1>{{статья|автор=Ermolaev S.Y., Slyusar V.I.|заглавие= Antenna synthesis based on the ant colony optimization algorithm.// 7-я Международная конференция по теории и технике антенн (ICATT’09), Львов, Украина, 6 - 9 октября 2009 г.|ссылка=http://slyusar.kiev.ua/298_300_ICATT_2009.pdf|год=2009|страницы= 298 - 300}}</ref>
=== Декілька комівояжерів ===
=== Кластери міст ===
=== Варіанти критеріїв оптимальності ===
=== Додаткові умови ===

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

Відповідно до ''он-лайн задачі'', всі міста не відомі наперед, натомість, кожне наступне місто стає відомим тоді, коли комівояжер вже в дорозі. Комівояжер повинен на основі отриманих даних обчислювати свій маршрут, так, аби нові міста «якнайкраще» вписувались у вже запланований маршрут. Такий варіант може зустрічатись, наприклад, в службі планування [[ADAC]] (технічної допомоги автомобілістам), коли інформація про поламані авто стає відомою поступово, і центр керування повинен нові виклики якнайкраще розподіляти між ремонтними автомобілями. Оскільки на дорозі знаходиться декілька ремонтних автомобілів та центр керування має повідомити про приблизний час прибуття ремонтників, то така задача є ''он-лайн задачею декількох комівояжерів з часовими обмеженнями''.

== Примітки ==
{{reflist}}

== Література ==

* {{cite book|chapter = '''Глава 3. Метод грубой силы: Задача коммивояжера'''|title = Алгоритмы: введение в разработку и анализ (Introduction to The Design and Analysis of Aigorithms)|author = Ананий В. Левитин|url = http://www.williamspublishing.com/Books/5-8459-0987-2.html|isbn = 0-201-74395-7|pages = 159-160|year = 2006|location = М.|publisher = «Вильямс»|accessdate = 18 листопада 2007|archive-date = 2 жовтня 2011|archive-url = https://web.archive.org/web/20111002020819/http://www.williamspublishing.com/Books/5-8459-0987-2.html}}
* {{cite book|
title=Построение и анализ вычислительных алгоритмов|
author=[[Альфред Ахо|А. Ахо]], [[Джон Хопкрофт|Дж. Хопкрофт]], [[Джеффрі Ульман|Дж. Ульман]]|
publisher=«Мир»|
year=1979|
place=Москва}}
* {{cite book|
title=Combinatorial Optimization|
author=Bernhard Korte, Jens Vygen|
edition=3-тє|
publisher=Springer|
year=2006|
isbn=3-540-25684-9}}

== Див. також ==
{{Портал|Математика}}
* [[Узагальнена задача комівояжера]]
* [[Дослідження операцій]],
* [[Задача листоноші]],
* [[Задача пакування рюкзака]].

== Посилання ==
* [http://www.tsp.gatech.edu/ The Traveling Salesman Problem Home] {{Webarchive|url=https://web.archive.org/web/20060207171845/http://www.tsp.gatech.edu/ |date=7 лютого 2006 }}&nbsp;— вичерпна інформація про задачу комівояжера{{ref-en}}
* [http://neo.lcc.uma.es/radi-aeb/WebVRP/ The VRP Web] {{Webarchive|url=https://web.archive.org/web/20081013145227/http://neo.lcc.uma.es/radi-aeb/WebVRP/ |date=13 жовтня 2008 }}&nbsp;— вичерпна інформація про задачу пошуку шляхів для машин{{ref-en}}
* [http://www.nbuv.gov.ua/Portal/natural/VNULP/Komp-nauky/2009_650/34.pdf Дослідження ефективності існуючих алгоритмів для розв'язання задачі комівояжера]
* [https://www.youtube.com/watch?v=SC5CX8drAtU Візуалізація різних стратегій розв'язання задачі комівояжера] {{Webarchive|url=https://web.archive.org/web/20160316060528/https://www.youtube.com/watch?v=SC5CX8drAtU |date=16 березня 2016 }}

{{math-stub}}
{{NP-повні задачі}}
{{ВП-портали|Програмування|Математика}}

[[Категорія:Задача комівояжера| ]]
[[Категорія:NP-складні задачі]]
[[Категорія:Дослідження операцій]]
[[Категорія:Алгоритми на графах]]
[[Категорія:Обчислювальні задачі в теорії графів]]
[[Категорія:Гамільтонові шляхи та цикли]]
[[Категорія:Метафори з посиланням на людей]]