Завдання комівояжера (англ.Travellingsalesmanproblem, TSP) (комівояжер - мандрівний торговець) - одна з найвідоміших задач комбінаторної оптимізації, що полягає в знаходженні самого вигідного маршруту, що проходить через зазначені міста хоча б по одному разу з наступним поверненням в початковий місто. В умовах задачі вказуються критерій вигідності маршруту (найкоротший, найдешевший, сукупний критерій тощо) і відповідні матриці відстаней, вартості тощо. Як правило, вказується, що маршрут повинен проходити через кожне місто тільки один раз - в такому випадку вибір здійснюється серед гамільтонових циклів.
Існує кілька окремих випадків загальної постановки завдання, зокрема геометрична задача комівояжера (також звана планарной або евклідової, коли матриця відстаней відображає відстані між точками на площині), метрична задача комівояжера (коли на матриці вартостей виконується нерівність трикутника), симетрична і асиметрична завдання комівояжера. Також існує узагальнення завдання, так звана узагальнена задача комівояжера.
Оптимізаційна постановка задачі належить до класу NP-важких задач, втім як і більшість її окремих випадків. Версія «decision problem» (тобто така, в якій ставиться питання чи існує маршрут не довше, ніж задане значення k) відноситься до класу NP-повних задач. Завдання комівояжера відноситься до числа трансобчислювальної: вже при відносно невеликому числі міст (66 і більше) вона не може бути вирішена методом перебору варіантів ніякими теоретично можливими комп'ютерами за час, менше кількох мільярдів років.
Неодмінною умовою і єдиним сенсом завдання комівояжера є пошук найвигіднішого шляху. Для цього необхідно знайти і описати всі можливі шляхи при будь-якому з варіантів способів пошуку рішення. Якщо ми не прорахували всі шляхи в обраному варіанті рішення, то ми не можемо стверджувати, що знайдене рішення найвигідніше. Що таке перевірка рішення? - це пошук помилки в процесі рішення або звірка отриманого результату зі свідомо правильним. Другий варіант тимчасово відкидаємо, так як немає практичного сенсу в рішенні завдання, якщо вже є рішення (в свою чергу, використання раніше виконаного вірного рішення для частини наявної завдання - спосіб зменшити рішення). В рамках даної роботи не ставилося метою порівняння різних методів і способів вирішення, тому приймаємо, що перевіряючий також вважає обраний спосіб вирішення оптимальним і перевіряє його на правильність. Що потрібно зробити перевіряючому? - повторити роботу, виконану при вирішенні, в повному обсязі для пошуку помилки на кожному етапі вирішення. Якщо буде знайдена помилка, то перевіряючому буде необхідно продовжити процес вирішення для пошуку більш вигідного маршруту. Таким чином, ми отримуємо, що перевірка виконання завдання комівояжера дорівнює або більше самого рішення.
Подання у вигляді графа.
Симетрична задача для чотирьох міст.
Для можливості застосування математичного апарату для розв'язання проблеми, її слід представити у вигляді математичної моделі. Проблему комівояжера можна представити у вигляді моделі на графі, тобто, використовуючи вершини і ребра між ними. Таким чином, вершини графа відповідають містам, а ребра (i, j) між вершинами i та j - шляхи сполучення між цими містами. Кожному ребру (i, j)> = 0 можна зіставити критерій вигідності маршруту, який можна розуміти як, наприклад, відстань між містами, час або вартість поїздки. Маршрутом (також гамільтоновим маршрутом) називається маршрут на такому графі, в який входить по одному разу кожна вершина графа. Завдання полягає в знаходженні найкоротшого маршруту.
З метою спрощення завдання і гарантії існування маршруту, зазвичай вважається, що модельний граф завдання є повністю зв'язковим, тобто, що між довільною парою вершин існує ребро. У тих випадках, коли між окремими містами не існує повідомлення, цього можна досягти шляхом введення ребер з максимальною довжиною. Через велику довжину таке ребро ніколи не потрапить до оптимального маршруту, якщо він існує.
Залежно від того, який критерій вигідності маршруту зіставляється величиною ребер, розрізняють різні варіанти завдання, найважливішими з яких є симетрична і метрична завдання.
Приклад рішення задачі комівояжера на мові python на заданому графі (Рис. 3.2).
У лістингу 2 наводиться скрипт для вирішення даного завдання.
Даний скрипт знаходить самий «вигідний» шлях від вершини 1 до вершини 4.
