Завдання комівояжера (Travelling salesman problem, скорочено TSP) є одним з найвідоміших завдань комбінаторної оптимізації, що складається в пошуку оптимального об'єкта в кінцевій безлічі об'єктів. Просто кажучи, полягає це завдання в тому, що потрібно знайти найбільш вигідний маршрут, що проходить через конкретні міста хоча б один раз, а потім повертається у вихідне місто.
Коротка історична довідка
Достеменно невідомо, коли завдання комівояжера було поставлено в перший раз. Але в 1832 році з'явилася книга «Комівояжер - як він повинен поводитися і що повинен робити для того, щоб доставляти товар і мати успіх у своїх справах - поради старого кур'єра», і в ній описувалася дана проблема.
Одним з ранніх варіантів завдання можна назвати завдання Icosian Game, розроблене ірландським математиком Вільямом Гамільтоном в 19 столітті. У ній потрібно було знайти маршрути на графі з двадцятьма вузлами. А перші дані про подібне завдання як математичне датуються 1930 роком.
Тоді австрійський економіст Карл Менгер на математичному колоквіумі сказав, що проблемою посильного називається завдання визначення найкоротшого шляху між кінцевою безліччю місць з відомою відстанню між ними. Деякий час потому з'явилася і відома нам варіація завдання - завдання мандрівного торговця (комівояжера). Її запропонував американський математик Хасслер Вітні.
Коротко про значення завдання
Умови завдання говорять про критерій вигідності маршруту (з точки зору відстані, дешевизни та інших складових). Маршрут повинен проходити тільки один раз через кожне місто, а після - повертатися в початкову точку.
На перший погляд може здатися, що знайти оптимальний маршрут дуже просто, але насправді це нелегке завдання. До того ж є різні варіації завдання, наприклад, геометричне, метричне, симетричне, асиметричне або узагальнене завдання.
З урахуванням різних властивостей завдання вже в другій половині 20 століття вивчати її стали не стільки з практичним ухилом, скільки з теоретичним - вона послужила моделлю для розробки новітніх алгоритмів оптимізації. На її прикладі були розроблені метод гілок і кордонів, метод відсікань, всілякі евристичні алгоритми та інші.
Починаючи з 1960 року, завдання комівояжера почали вивчати програмісти, економісти, хіміки, біологи та представники інших наук. А все з тієї простої причини, що до її вирішення зводяться і рішення величезної кількості практичних завдань у різних галузях науки і життя.
У сучасному світі завдання комівояжера допомагає оптимізувати роботу транспортних відділів і відділів логістики, спрощує роботу поштових і кур'єрських служб, підвищує ефективність моніторингу об'єктів, наприклад, станцій стільникових операторів і нафтових вишок.
Здатність вирішити це завдання дозволяє оптимізувати і багато виробничих процесів, знаходити оптимальні стратегії ведення господарства, економити ресурси.
Чим завдання комівояжера корисне для розвитку мислення
Ритм сучасного життя кардинально змінює ставлення людей до часу. Сьогодні люди стають все більш нетерплячими, не люблять чекати, шукають нові можливості оптимізувати свій час і знаходити найбільш ефективні рішення завдань і проблем. Природно, тут же постає і питання про більш оптимальне використання інших ресурсів, в тому числі і інтелектуальних, і фізичних, і фінансових.
Саме тому вирішення завдання комівояжера несе практичну користь. Воно не просто налаштовує свідомість та інтелект людини на певний - більш ефективний з практичної точки зору лад, а й розвиває абстрактне, логічне, просторове та інші види мислення, якими ми всі активно користуємося в щоденному житті.
Безумовно, вирішити цю задачу може спробувати кожен, але без спеціальних знань і навичок не варто чекати якихось серйозних просувань (не дарма ж її рішенням займаються цілі наукові спільноти!). Однак потренуватися цілком можна.
Для цього у вас є чудова можливість пройти нашу безкоштовну онлайн-програму «Нейробіка», деякі завдання з якої включають в себе елементи завдання комівояжера. Всього ж у ній представлено понад 20 цікавих завдань, спрямованих на розвиток мислення. Спробуйте - думаємо, що вам сподобається цей курс.
Сподобалася стаття? Приєднуйтесь до наших спільнот у соцмережах або каналу в Telegram і не пропускайте вихід нових корисних матеріалів:
Teleg ВконтактеFacebook