Когда два года назад Нэтан Кляйн поступил в аспирантуру, его руководители предложили ему скромный план: совместную работу над одной из самых известных и давних задач теоретической информатики.
Они посчитали, что даже если Нэтану не удастся её решить, то в процессе работы он многому научится. Он согласился на эту идею. «Я не знал, что мне нужно бояться», — говорит Кляйн. «Я был всего лишь начинающим аспирантом, поэтому не понимал сложность этой задачи».
Читать полностью »
Известная как минимум с 19 века задача коммивояжера имеет множество способов решения и неоднократно описана. Ее оптимизационная версия является NP-трудной, поэтому оптимальное решение можно получить либо полным перебором, либо оптимизированным полным перебором — методом ветвей и границ.
Пытаясь запрограммировать алгоритм Литтла (частный случай метода ветвей и границ), я понял, что в рунете крайне трудно найти его правильное описание понятным языком и разобранную программную реализацию. Однако имеющиеся в изобилии описания обманчиво правдоподобны на данных малого размера и с трудом проверяются без визуализации.
