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

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

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

— Когда я приехал в Новосибирск, оказалось, что коллеги в Институте математики называют «алгоритмом Кристофидеса-Сердюкова» тот алгоритм, который во всех учебниках по алгоритмике называется «алгоритмом Кристофидеса». И как раз в кабинете Института математики, в котором я тогда работал, стоял выпуск журнала «Управляемые системы» 1978 года с соответствующей статьей Сердюкова. Я удивился, что в ней действительно был предложен в точности тот же самый алгоритм Кристофидеса. В статье указана дата поступления статьи в редакцию — январь 1976 года, что всего на месяц опережает результат Кристофидеса. Я тогда задался вопросом, как возможна такая случайность и почему за пределами Института математики мало кто знает о результате Сердюкова? Спустя пять лет, я обратился к своему знакомому историку, Виктории Слугиной, и мы начали исследование: нашли ранние работы Сердюкова, искали следы результата Кристофидеса, — рассказал Рене ван Беверн.

В статье ученых НГУ отражено, что алгоритм Кристофидеса предложен им в феврале 1976 года, но технический отчет, в котором описывается алгоритм, вплоть до 1978 года был малоизвестен. Первое полное описание алгоритма Кристофидеса с доказательством корректности было опубликовано только в 1979 году в популярном учебнике Гарея и Джонсона по трудно решаемым задачам комбинаторной оптимизации.

Сердюков же построил алгоритм, будучи молодым аспирантом Института математики СО АН СССР. Еще в 1973–1974 годах он и Кристофидес независимо друг от друга работали над смежными задачами маршрутизации транспорта. Однако, утверждают авторы исследования, по работам Сердюкова видно, что он вплоть до 1974 года не знал о важнейшем ингредиенте своего алгоритма для задачи коммивояжера: полиномиальном алгоритме для нахождения максимального паросочетания в графе, опубликованном в США еще в 1965 году. В своей статье о коммивояжере он, используя этот алгоритм, ссылается на книгу, опубликованную в СССР лишь в 1976 году. Этим самым и объясняется временное совпадение результатов Сердюкова и Кристофидеса: первый не мог получить результат намного раньше второго, не зная об алгоритме для нахождения максимального паросочетания.

— Рассмотренный нами сюжет истории открытия одного алгоритма, с одной стороны, показывает высокий уровень кадрового состава новосибирского Академгородка и актуальность исследовательских тематик, которые разрабатывались в институтах СО АН СССР. С другой стороны, отсутствие в то время единых международных баз знаний и затрудненность академической мобильности советских специалистов приводили к тому, что многие их результаты не могли быть доступны широкому кругу западных исследователей, и, наоборот, результаты европейских и американских авторов также оказывались неизвестны, либо доходили до советских ученых с опозданием, — отметила Виктория Слугина.

Комментарии: