Ученые НГУ исследовали историю открытия известного алгоритма для задачи коммивояжера

Описание

Заведующий лабораторией алгоритмики Механико-математического факультета НГУ Рене ван Беверн и заместитель директора Гуманитарного института по научной работе Виктория Слугина провели исследование происхождения алгоритма для одной из классических задач комбинаторной оптимизации. В своей статье сотрудники университета доказывают, что всемирно известный «алгоритм Кристофидеса», предложенный для задачи коммивояжера, независимо построил советский ученый новосибирского Института математики Анатолий Иванович Сердюков, и предложил он его к публикации даже раньше, чем это сделал Кристофидес. Исследования ученых НГУ были опубликованы на сайте официального журнала международной комиссии по истории математики Международного союза истории и философии науки Historia Mathematica

Предмет

Задача коммивояжера является одной из классических задач комбинаторной оптимизации. Она была сформулирована еще в 1832 году и состоит в том, чтобы найти кратчайший маршрут для посещения n городов ровно по одному разу и возвращения в исходный город. Задача относится к классу NP-трудных задач, для которых неизвестны эффективные алгоритмы решения. Однако для метрического случая, когда расстояния между городами удовлетворяют неравенству треугольника, Никос Кристофидес в феврале 1976 года предложил алгоритм, который эффективно строит маршрут, чья длина не превосходит 3/2 от оптимума. Это один из первых приближенных алгоритмов для NP-трудных задач, и до сих пор для метрического случая неизвестны эффективные алгоритмы с более хорошей гарантией точности