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

Пресса/СМИ: Новостная публикация

Описание

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

Предмет

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

Период29 мая 2020 → 1 июн 2020

Охват СМИ

2

Охват СМИ

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

Материалы СМИ

1

Материалы СМИ

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