Известная как минимум с 19 века задача коммивояжера имеет множество способов решения и неоднократно описана. Ее оптимизационная версия является NP-трудной, поэтому оптимальное решение можно получить либо полным перебором, либо оптимизированным полным перебором — методом ветвей и границ.



Пытаясь запрограммировать алгоритм Литтла (частный случай метода ветвей и границ), я понял, что в рунете крайне трудно найти его правильное описание понятным языком и разобранную программную реализацию. Однако имеющиеся в изобилии описания обманчиво правдоподобны на данных малого размера и с трудом проверяются без визуализации.



![animation][1]

[Читать дальше →][2]

[1]: https://habrastorage.org/getpro/habr/post_images/d38/d7d/262/d38d7d262f71d6d2775d0bd7d61b3b0a.gif
[2]: https://habrahabr.ru/post/332208/?utm_source=habrahabr&utm_medium=rss&utm_campaign=feed_posts#habracut