#кристофидес — Public Fediverse posts
Live and recent posts from across the Fediverse tagged #кристофидес, aggregated by home.social.
-
Алгоритм Кристофидеса-Сердюкова
В прошлой заметке я коснулся принципа работы некоторых популярных алгоритмов неточного решения задачи коммивояжера (TSP). Материал получился объемным и сунуть туда еще одно описание алгоритма было бы чрезмерностью. Тем не менее, считаю важным рассказать еще об одном решении, которое носит название - Алгоритм Кристофидеса-Сердюкова . Причины, по которым мне хочется об этом поговорить следующие: 1. Речь идет про алгоритм, который часто используется в качестве бенчмарка при оценке эффективности поиска решений сетками с использованием трансформеров, например в работе TranSPormer: A Transformer Network for the Travelling Salesman Problem и не только 2. Несмотря на то, что алгоритм назван в честь русского математика в русскоязычном сегменте интернета не так много публикаций на эту тему, можно отметить статью Сердюкова от 1978 и упоминание в Википедии 3. Наконец, алгоритм просто красив. Понимаю, что математическая эстетика – это нечто скрытое в глубине вещей и недоступное суетливому взору, но верю, что и такая категория красоты найдет своего читателя.