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

    Итоги январской математической сессии РЦ «Альтаир» для педагогов

    Завершилась III сессия математической программы для педагогов, проводимая Региональным центром "Альтаир" с 22 по 24 января. На сессии приняли участие 20 педагогов с Новосибирской области.  Программа мероприятия включала тренинг «Решение психологических кейсов» и лекции «Исследовательская работа со школьниками» и «Опыт различных математических школ России».
    384
  • 06/03/2016

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

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

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

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

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

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

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

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

    Академгородок 2.0 – приобретения и потери: мнения экспертов

    Что удалось сделать для развития Новосибирского научного центра за последние годы и какие задачи остаются нерешенными? Три известных российских ученых инвентаризируют достижения и проблемы в статье, написанной для «Континента Сибирь»*.
    1008
  • 29/10/2019

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

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

    Математический марафон СУНЦ НГУ открывает юбилейный сезон

    Этой весной СУНЦ НГУ проводит юбилейный Математический марафон для школьников. Собрать команду и стать участниками марафона могут ученики любой российской школы, увлеченные математикой. Марафон проходит в дистанционном формате.
    255
  • 28/10/2020

    Академик РАН Михаил Федорук: примеры успешного участия вузов в прорывных научных исследованиях

    «Университет должен создавать высокотехнологичную, инновационную систему своего региона. Так что решения по итогам Госсовета в этой сфере правильны и своевременны», – сказал газете "Взгляд" ректор Новосибирского госуниверситета Михаил Федорук, комментируя поручения президента, направленные на проведение прорывных научных исследований и создание новых технологий и материалов.
    411