​​Задача коммивояжера

Задача коммивояжера (Travelling salesman problem, сокращённо TSP) является одной из самых известных задач комбинаторной оптимизации, состоящей в поиске оптимального объекта в конечном множестве объектов. Попросту говоря, заключается эта задача в том, что нужно найти наиболее выгодный маршрут, проходящий через конкретные города хотя бы один раз, а затем возвращающийся в исходный город.

Краткая историческая справка
Доподлинно неизвестно, когда задача коммивояжера была поставлена в первый раз. Но в 1832 году появилась книга «Коммивояжёр — как он должен вести себя и что должен делать для того, чтобы доставлять товар и иметь успех в своих делах — советы старого курьера», и в ней описывалась данная проблема.

Одним из ранних вариантов задачи можно назвать задачу Icosian Game, разработанную ирландским математиком Уильямом Гамильтоном в 19 столетии. В ней нужно было найти маршруты на графе с двадцатью узлами. А первые данные о подобной задаче в качестве математической датируются 1930 годом.

Читать далее