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

задача.jpg 

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

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

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

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


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

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

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

  • 08/10/2019

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

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

    Более 2 500 человек освоили новые IT-профессии в Академии Яндекса в этом году

    ​Образовательные проекты компании помогают людям найти свой путь в IT и выпускают сильных специалистов для цифровой экономики. Академия Яндекса помогает школьникам и студентам, которые увлекаются технологиями, освоить востребованные IT-профессии по программам, разработанным экспертами компании.
    280
  • 28/06/2021

    Дистанционная летняя смена для участников олимпиад проходит в СУНЦ НГУ

    ​В СУНЦ НГУ на этой неделе началась дистанционная летняя смена олимпиадной подготовки для старшеклассников, увлеченных точными и естественными науками. Летняя смена олимпиадной подготовки (ЛСОП) – это двухнедельное погружение, направленное на интенсивную подготовку учеников 8–10 классов к участию в олимпиадах по математике, физике, химии, информатике.
    364
  • 15/10/2020

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

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

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

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

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

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

    В НГУ состоялся заключительный этап Всероссийского химического турнира школьников

    XVII Всероссийский химический турнир школьников, который последние 3 года проходит на площадке НГУ, завершился. Это командное соревнование по решению творческих научных задач, позволяющее участникам расширять научный кругозор, научиться презентовать свои научные проекты, вступать в полемику и отстаивать свое мнение, применять научные знания для решения прикладных и теоретических задач.
    725
  • 26/04/2021

    Ученик СУНЦ НГУ стал призером Всероссийской олимпиады по двум предметам

    В Тюмени завершился заключительный этап Всероссийской олимпиады по математике. Одним из призеров стал ученик 10 класса СУНЦ НГУ Никита Барыкин.  Олимпиада проходила с 16 по 22 апреля. Состязание включало два теоретических тура по решению задач из различных разделов математики.
    734
  • 23/07/2021

    Большая математическая мастерская приурочена к Году науки и технологий

    ​С 12 по 16 июля 2021 года прошла первая неделя Большой математической мастерской (БММ), приуроченной к году науки и технологий. Четыре площадки — Международный математический институт им. Леонарда Эйлера (г.
    710
  • 11/08/2020

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

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