​​​
Заведующий лабораторией алгоритмики Механико-математического факультета НГУ Рене ван Беверн и заместитель директора Гуманитарного института по научной работе Виктория Слугина провели исследование происхождения алгоритма для одной из классических задач комбинаторной оптимизации. В своей статье сотрудники университета доказывают, что всемирно известный «алгоритм Кристофидеса», предложенный для задачи коммивояжера, независимо построил советский ученый новосибирского Института математики Анатолий Иванович Сердюков, и предложил он его к публикации даже раньше, чем это сделал Кристофидес. Исследования ученых НГУ были опубликованы на сайте официального журнала международной комиссии по истории математики Международного союза истории и философии науки 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 Ломоносовских чтений, прошедших в рамках осенней сессии Дней молодежной науки. Одним из постоянных участников и ключевых докладчиков научного форума стал Владимир Петрович Голубятников – математик с мировым именем, профессор НГУ, главный научный сотрудник Института математики им.
    2220
  • 25/02/2020

    Ежегодная конференция «Динамика в Сибири»

    ​24 февраля начала работу международная конференция «Динамика в Сибири». Конференция проходит ежегодно в новосибирском Академгородке, её программа традиционно включает доклады по проблемам теории динамических систем, геометрии и смежных областей.
    668
  • 17/08/2016

    В Новосибирске пройдет Вторая международная конференция «Математическая гидродинамика»

    Новосибирский государственный университет совместно с Институтом гидродинамики СО РАН (зеркальная лаборатория нелинейных процессов в гидродинамических системах) проводят 22–27 августа вторую Международную конференцию «Математическая гидродинамика».
    3664
  • 29/06/2018

    В Новосибирске проходит международная конференция молодых математиков

    Региональный математический центр НГУ и Институт математики им. С. Л. Соболева СО РАН проводят международную конференцию по математическому анализу. Целью мероприятия является объединение молодых исследователей со всего мира с общим интересом к функциональным пространствам и геометрическому анализу.
    1823
  • 29/10/2019

    Выделен грант на создание «Математического центра в Академгородке»

    ​Математический центр в Академгородке, который появится на базе Новосибирского государственного университета и Института математики, до конца 2019 года получит 80 миллионов рублей. Распоряжение об этом опубликовано на сайте правовой информации 25 октября.
    755
  • 29/06/2020

    Михаил Федорук: «Мы должны сделать Академгородок лучшим местом для жизни»

    Интервью с ректором Новосибирского государственного университета академиком Михаилом Петровичем Федоруком о том, почему программа «Академгородок 2.0» должна быть комплексным решением, что такое университет мирового класса и какова роль НГУ в нацпроекте «Наука».
    457
  • 06/03/2016

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

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

    Сотрудник ИМ СО РАН расскажет, как была решена самая знаменитая математическая задача ХХ века

    ​4 февраля известный популяризатор математики Александр Гутман расскажет, как была решена знаменитая математическая задача XX в. — «Проблема континуума»». «Проблема континуума интересна в том отношении, что это вопрос, родившийся в процессе изучения человеческого мышления.
    635
  • 17/06/2019

    НГУ проведет Летнюю криптографическую школу

    Криптографический центр НГУ, лаборатория криптографии JetBrains Research, организаторы международной олимпиады NSUCRYPTO, факультет информационных технологий и механико-математический факультет объявляют о наборе студентов бакалавриата и магистратуры ФИТ, ММФ и ФФ на Летнюю школу "Криптография и информационная безопасность", которая пройдёт в НГУ с 1 по 19 июля 2019 года.
    613
  • 26/06/2019

    В НГУ прошла VI Российско-Китайская конференция по теории узлов и смежным вопросам

    ​В этом году c 17 по 21 июня конференцию проводили Лаборатория топологии и динамики Новосибирского государственного университета и Институт математики им. С. Л. Соболева СО РАН.
    1142