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