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

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

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

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

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

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

Источники

Ученые НГУ исследовали историю открытия известного алгоритма для задачи коммивояжера
Новосибирский государственный университет (nsu.ru), 29/05/2020
Ученые НГУ исследовали историю открытия известного алгоритма для задачи коммивояжера
Искусственный интеллект ИТ новости (ai-news.ru), 30/05/2020

Похожие новости

  • 21/11/2018

    В АлтГУ представили результаты исследований ученых СО РАН в области математического моделирования генных процессов

    ​Опорный Алтайский государственный университет подводит итоги V Ломоносовских чтений, прошедших в рамках осенней сессии Дней молодежной науки. Одним из постоянных участников и ключевых докладчиков научного форума стал Владимир Петрович Голубятников – математик с мировым именем, профессор НГУ, главный научный сотрудник Института математики им.
    2219
  • 04/09/2019

    В России создаются Международные математические центры мирового уровня

    ​Совет по государственной поддержке создания и развития математических центров мирового уровня под председательством вице-премьера Татьяны Голиковой определил четыре такие структуры. Среди них и совместный проект Новосибирского государственного университета и Института математики имени С.
    611
  • 13/01/2015

    Академик Искандер Асанович Тайманов - об основных тенденциях математики

    ​Заведующий лабораторией динамических систем Института математики им. С.Л. Соболева академик Искандер Асанович Тайманов рассказал редакции "Науки в Сибири" об основных тенденциях этой точной науки.
    2522
  • 17/01/2018

    Международная молодёжная школа-конференция «Алгоритмические вопросы теории групп и смежных областей»

    ​С 25 июля по 5 августа 2016 года в Новосибирской области на территории базы отдыха «Оазис» пройдет международная школа «Алгоритмические вопросы теории групп и смежных областей». Организаторами конференции являются Институт математики им.
    2358
  • 27/02/2020

    Ирина Молокова: мы бы хотели, чтобы наука, сосредоточенная в Академгородке, пришла к нам

    ​В прошлом году стартовал проект «Опорные школы РАН». Его цель — создать условия для выявления и обучения талантливых детей, а также мотивировать их на построение успешной карьеры в области науки и высоких технологий.
    617
  • 22/11/2017

    Конференция «Декабрьские чтения»

    ​Конференция «Декабрьские чтения» состоится в Институте математики им. С.Л. Соболева СО РАН 21-23 декабря 2017 года.  Планируются часовые пленарные доклады.  Программный комитет:  А.
    1880
  • 30/12/2019

    «Академгородок 2.0» в 2019 году

    На последнем в 2019 году заседании Президиума СО РАН главный ученый секретарь Сибирского отделения академик Дмитрий Маркович Маркович рассказал о том, что было сделано за год в рамках воплощения программы «Академгородок 2.
    1309
  • 14/08/2018

    Академик Юрий Ершов: цифровой экономике без математиков не обойтись

    Академик РАН Юрий Леонидович Ершов известен далеко за пределами Академгородка. Руководитель сибирской школы алгебры и логики, директор Института математики СО РАН (2002-2011 гг.), ректор НГУ (1985-1993 гг.
    1409
  • 02/09/2019

    Где и зачем откроют математические центры мирового уровня

    ​Чем российская математика похожа на французскую и не похожа на американскую, чем займутся математические центры мирового уровня, почему в число победителей конкурса на их создание вошли не только авторы сильнейших заявок, на что можно тратить выигранные деньги, и есть ли надежда, что четырьмя центрами дело не ограничится, — читайте в материале Indicator.
    1137
  • 06/03/2016

    Академику Александру Алексеевичу Боровкову - 85 лет!

    ​​​Александр Алексеевич Боровков родился 6 марта 1931 года в г. Москве. В 1954 году окончил Механико-математический факультет Московского государственного университета. С 1960 года работает в Институте математики СО РАН.
    3463