​​​В задаче китайского почтальона нужно найти кратчайший обход всех ребер графа. 

задача.jpg 

 
Ее так назвали, потому что, по всей видимости, впервые ее изучал китайский математик Квон Мэй-Ко в 1960 году. Только в начале 1970-х годов ею также занялись математики на Западе и в Новосибирске. Авторы статьи заведующий лабораторией алгоритмики Механико-математического факультета НГУ Рене ван Беверн, младший научный сотрудник лаборатории алгоритмики ММФОксана Цидулко и студент ММФ НГУ Всеволод Афанасьев занимались задачей китайского почтальона с иерархиями, в которой ребра разбиты на классы и между классами есть ограничения предшествования: ребро можно пройти лишь тогда, когда пройдены все ребра в классах, предшествующих классу этого ребра. Статья опубликована в Operations Research Letters, который входит в Q2 по Scopus. 

 
— Вообще, все началось с разбора статьи по данной задаче. Потом Рене предложил рассмотреть определенную ее версию и процесс пошел. Мы читали статьи по теме и строили и проверяли какие-то гипотезы, а потом раз в 1–2 недели собирались и устраивали мозговой штурм по конкретным темам (например, придумывали приближенные алгоритмы, т. е. алгоритмы, которые в каком-то смысле «меняют точность на скорость работы» для определенных постановок задачи). После этого основные полученные результаты мы оформили в статью, — рассказал об исследовании студент ММФ Всеволод Афанасьев.​​

Условно говоря, требуется кратчайший маршрут для уборки снега, но сначала нужно убрать главные дороги. На самом деле, более подходящий пример — резка металла. Допустим, требуется вырезать букву О из листа металла. Нужно сначала вырезать внутренний круг (дырку), потом внешний. Если сначала вырезать внешний круг, то из листа выпадет вырезанный диск и вырезать дырку в нем мы уже не сможем. 

 
— Варианты задачи китайского почтальона интересны тем, что они на грани между легко и трудно решаемыми задачами. Это их отличает от задачи коммивояжера, в которой нужно найти кратчайший обход вершин (а не ребер) графа: она практически всегда сложна. Например, задача китайского почтальона, в которой нужно найти кратчайший обход всех ребер (а не вершин) графа, легко решается. А если требуется обойти лишь заданное подмножество ребер? Тогда она называется задачей деревенского почтальона, и она вдруг NP-трудна, значит, для нее нет эффективных алгоритмов, если не P=NP. Но если ребра в этом подмножестве распадаются на малое число несвязных компонент? Тогда задача опять эффективно решается, — уточнил Рене ван Беверн. — В 2014 году я участвовал в написании книги о задачах кратчайшего обхода ребер — обзора вычислительной сложности таких задач. Мы тогда выявили много открытых вопросов. С тех пор активно над закрытием этих пробелов независимо друг от друга работали мы и команда в Лондоне. Что касается задачи о китайском почтальоне с иерархиями, то по ней было известно лишь то, что она эффективно решается, если ребра в каждом классе образуют связный подграф и классы упорядочены линейно, то есть сначала нужно обойти все ребра уровня 1, потом уровня 2, потом уровня 3 и так далее. Также было известно, что задача NP-трудна, если классы не связаны.​


С одной стороны, ученые получили несколько удивительный результат, что малейшее отступление от линейного упорядочения классов приведет к NP-трудной задаче. Допустим, ребра в каждом классе связанные, но помимо линейно упорядоченных классов есть еще один класс ребер таких, что их можно проходить, когда угодно. В этом случае задача оказалась NP-трудна! С другой стороны, получили и положительные результаты: если классы линейно упорядочены, то в принципе не так уж страшно отказаться от связности ребер в каждом классе. Во-первых, авторы статьи доказали, что в этом случае можно эффективно найти хотя бы хорошие приближенные решения. Во-вторых, доказали, что если ребра в каждом классе образуют малое число несвязных компонент, то задача все же эффективно решается. 

 
— На самом деле для получения положительных результатов мы доказали намного более общий результат: на задачу китайского почтальона с линейно упорядоченными (но не обязательно связанными) классами переносятся все алгоритмы для точного решения задачи деревенского почтальона. А про деревенского почтальона мы уже знаем почти все. К сожалению, с одним открытым вопросом нам все же не удалось разобраться: задача китайского почтальона с тремя связанными классами эффективно решается или NP-трудна? Мы до сих пор не знаем, — подытожил Рене ван Беверн.

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

  • 15/03/2021

    Профессия аналитик данных

    ​​Данные — очень важная информация для любой компании. По ним можно предсказать поведение клиентов, отследить спрос на определенный товар, улучшить сервис и повысить продажи. Обработка значений и показателей сформировала целую профессию — аналитик данных​.
    277
  • 14/02/2019

    Международная конференция «Актуальные проблемы вычислительной и прикладной математики 2019» (АПВПМ-19)

    С 1 по 5 июля 2019 года в Новосибирском Академгородке в рамках "Марчуковских научных чтений" состоится Международная конференция "Актуальные проблемы вычислительной и прикладной математики - 2019.
    2207
  • 15/10/2020

    Директор математического центра ТГУ победил в конкурсе фонда «Базис»

    ​Руководитель Регионального научно-образовательного математического центра (НОМЦ) ТГУ, доктор физико-математических наук, член-корреспондент РАН Андрей Веснин стал одним из семи победителей конкурса Leader («Ведущий ученый») по фундаментальной математике.
    850
  • 11/11/2020

    Автоматическая блинная печь и калькулятор генов: учащиеся инженерных курсов СУНЦ НГУ представили новые проекты

    ​​В Лаборатории инженерного конструирования СУНЦ НГУ прошел дистанционный семинар, на котором учащиеся представили темы своих проектов и рассказали об их реализации. Лучшие проекты весной будут представлены на школьной секции Международной научной студенческой конференции (МНСК).
    651
  • 11/11/2020

    Город учёных посреди сибирской тайги: фоторепортаж об Академгородке Новосибирска

    Новосибирский Академгородок известен далеко за пределами самого Новосибирска. Основанный в 1957, город ученых собрал на своей территории десятки научно-исследовательских институтов, за что одна из его улиц – проспект Академика Лаврентьева – внесена в Книгу рекордов Гиннеса как «самая умная улица в мире».
    2682
  • 08/10/2019

    Десять студентов и аспирантов НГУ получат стипендии Президента и Правительства Российской Федерации

    Стипендия Президента и Правительства Российской Федерации назначается студентам и аспирантам, осваивающим образовательные программы высшего образования. Для получения стипендии необходимо иметь отличные успехи в учебе и научных исследованиях, быть победителем всероссийских и международных олимпиад, творческих конкурсов, фестивалей или являться автором открытий и научных статей.
    1553
  • 08/02/2021

    Двадцатая Международная конференция по криптографии SIBECRYPT

    ​SIBECRYPT — одна из ведущих конференций по криптографии и компьютерной безопасности в России, ежегодно проходящая в разных городах Сибири. Её цель — обсуждение фундаментальных математических проблем криптографии и защиты информации в компьютерных системах и сетях, обмен научными результатами по развитию теоретических основ и созданию программно-аппаратных средств компьютерной безопасности.
    389
  • 30/11/2020

    Директор специализированного учебно-научного центра России Яворский покинул пост

    ​Директор Специализированного учебно-научного центра России (СУНЦ) - физико-математической школы им. М. А. Лаврентьева при Новосибирском государственном университете Николай Яворский, занимавший эту должность 15 лет, покинул свой пост.
    559
  • 13/01/2021

    Академику Анатолию Николаевичу Коновалову 85 лет

    ​Анатолий Николаевич Коновалов родился 13 января 1936 года в Ростове-на-Дону.В 1958 году окончил с отличием Уральский государственный университет им. А.М. Горького (г. Свердловск). Один год учился в очной аспирантуре, затем перевелся в заочную аспирантуру и поступил на работу во Всесоюзный НИИ технической физики (п/я 150, г.
    416
  • 11/08/2020

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

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