Задача коммивояжера (Travelling salesman problem, сокращённо TSP) является одной из самых известных задач комбинаторной оптимизации, состоящей в поиске оптимального объекта в конечном множестве объектов. Попросту говоря, заключается эта задача в том, что нужно найти наиболее выгодный маршрут, проходящий через конкретные города хотя бы один раз, а затем возвращающийся в исходный город.
Краткая историческая справка
Доподлинно неизвестно, когда задача коммивояжера была поставлена в первый раз. Но в 1832 году появилась книга «Коммивояжёр — как он должен вести себя и что должен делать для того, чтобы доставлять товар и иметь успех в своих делах — советы старого курьера», и в ней описывалась данная проблема.
Одним из ранних вариантов задачи можно назвать задачу Icosian Game, разработанную ирландским математиком Уильямом Гамильтоном в 19 столетии. В ней нужно было найти маршруты на графе с двадцатью узлами. А первые данные о подобной задаче в качестве математической датируются 1930 годом.
Тогда австрийский экономист Карл Менгер на математическом коллоквиуме сказал, что проблемой посыльного называется задача определения кратчайшего пути между конечным множеством мест с известным расстоянием между ними. Некоторое время спустя появилась и известная нам вариация задачи – задача странствующего торговца (коммивояжера). Ее предложил американский математик Хасслер Уитни.
Коротко о значении задачи
Условия задачи говорят о критерии выгодности маршрута (с точки зрения расстояния, дешевизны и других составляющих). Маршрут должен проходить только один раз через каждый город, а после – возвращаться в начальную точку.
На первый взгляд может показаться, что найти оптимальный маршрут очень просто, но в действительности это нелегкая задача. К тому же есть разные вариации задачи, например, геометрическая, метрическая, симметричная, асимметричная или обобщенная задача.
С учетом разных свойств задачи уже во второй половине 20 века изучать ее стали не столько с практическим уклоном, сколько с теоретическим – она послужила моделью для разработки новейших алгоритмов оптимизации. На ее примере были разработаны метод ветвей и границ, метод отсечений, всевозможные эвристические алгоритмы и другие.
Начиная с 1960 года, задачу коммивояжера начали изучать программисты, экономисты, химики, биологи и представители других наук. А все по той простой причине, что к ее решению сводятся и решения огромного количества практических задач в разных областях науки и жизни.
В современном мире задача коммивояжера помогает оптимизировать работу транспортных отделов и отделов логистики, упрощает работу почтовых и курьерских служб, повышает эффективность мониторинга объектов, например, станций сотовых операторов и нефтяных вышек.
Способность решить эту задачу позволяет оптимизировать и многие производственные процессы, находить оптимальные стратегии ведения хозяйства, экономить ресурсы.
Чем задача коммивояжера полезна для развития мышления
Ритм современной жизни кардинально меняет отношение людей ко времени. Сегодня люди становятся все более нетерпеливыми, не любят ждать, ищут новые возможности оптимизировать свое время и находить наиболее эффективные решения задач и проблем. Естественно, здесь же встает и вопрос о более оптимальном использовании других ресурсов, в том числе и интеллектуальных, и физических, и финансовых.
Именно поэтому решение задачи коммивояжера несет практическую пользу. Оно не просто настраивает сознание и интеллект человека на определенный – более эффективный с практической точки зрения лад, но и развивает абстрактное, логическое, пространственное и другие виды мышления, которыми мы все активно пользуемся в каждодневной жизни.
Безусловно, решить эту задачу может попытаться каждый, но без специальных знаний и навыков не стоит ждать каких-то серьезных продвижений (не зря же ее решением занимаются целые научные сообщества!). Однако потренироваться вполне можно.
Для этого у вас есть прекрасная возможность пройти нашу бесплатную онлайн-программу «Нейробика», некоторые задания из которой включают в себя элементы задачи коммивояжера. Всего же в ней представлено более 20 интересных заданий, направленных на развитие мышления. Попробуйте – думаем, что вам понравится этот курс.
