В задаче китайского почтальона нужно найти кратчайший обход всех ребер графа:
Ее так назвали, потому что, по всей видимости, впервые ее изучал китайский математик Квон Мэй-Ко в 1960 году. Только в начале 1970-х годов ею также занялись математики на Западе и в Новосибирске. Авторы статьи заведующий лабораторией алгоритмики Механико-математического факультета НГУ Рене ван Беверн, младший научный сотрудник лаборатории алгоритмики ММФ Оксана Цидулко и студент ММФ НГУ Всеволод Афанасьев занимались задачей китайского почтальона с иерархиями, в которой ребра разбиты на классы и между классами есть ограничения предшествования: ребро можно пройти лишь тогда, когда пройдены все ребра в классах, предшествующих классу этого ребра. Статья опубликована
в Operations Research Letters, который входит в Q2 по Scopus.
— Вообще, все началось с разбора статьи по данной задаче. Потом Рене предложил рассмотреть определенную ее версию и процесс пошел. Мы читали статьи по теме и строили и проверяли какие-то гипотезы, а потом раз в 1–2 недели собирались и устраивали мозговой штурм по конкретным темам (например, придумывали приближенные алгоритмы, т. е. алгоритмы, которые в каком-то смысле «меняют точность на скорость работы» для определенных постановок задачи). После этого основные полученные результаты мы оформили в статью, — рассказал об исследовании студент ММФ Всеволод Афанасьев.
Условно говоря, требуется кратчайший маршрут для уборки снега, но сначала нужно убрать главные дороги. На самом деле, более подходящий пример — резка металла. Допустим, требуется вырезать букву О из листа металла. Нужно сначала вырезать внутренний круг (дырку), потом внешний. Если сначала вырезать внешний круг, то из листа выпадет вырезанный диск и вырезать дырку в нем мы уже не сможем.
— Варианты задачи китайского почтальона интересны тем, что они на грани между легко и трудно решаемыми задачами. Это их отличает от задачи коммивояжера, в которой нужно найти кратчайший обход вершин (а не ребер) графа: она практически всегда сложна. Например, задача китайского почтальона, в которой нужно найти кратчайший обход всех ребер (а не вершин) графа, легко решается. А если требуется обойти лишь заданное подмножество ребер? Тогда она называется задачей деревенского почтальона, и она вдруг NP-трудна, значит, для нее нет эффективных алгоритмов, если не P=NP. Но если ребра в этом подмножестве распадаются на малое число несвязных компонент? Тогда задача опять эффективно решается, — уточнил Рене ван Беверн. — В 2014 году я участвовал в написании книги о задачах кратчайшего обхода ребер — обзора вычислительной сложности таких задач. Мы тогда выявили много открытых вопросов. С тех пор активно над закрытием этих пробелов независимо друг от друга работали мы и команда в Лондоне. Что касается задачи о китайском почтальоне с иерархиями, то по ней было известно лишь то, что она эффективно решается, если ребра в каждом классе образуют связный подграф и классы упорядочены линейно, то есть сначала нужно обойти все ребра уровня 1, потом уровня 2, потом уровня 3 и так далее. Также было известно, что задача NP-трудна, если классы не связаны.
С одной стороны, ученые получили несколько удивительный результат, что малейшее отступление от линейного упорядочения классов приведет к NP-трудной задаче. Допустим, ребра в каждом классе связанные, но помимо линейно упорядоченных классов есть еще один класс ребер таких, что их можно проходить, когда угодно. В этом случае задача оказалась NP-трудна! С другой стороны, получили и положительные результаты: если классы линейно упорядочены, то в принципе не так уж страшно отказаться от связности ребер в каждом классе. Во-первых, авторы статьи доказали, что в этом случае можно эффективно найти хотя бы хорошие приближенные решения. Во-вторых, доказали, что если ребра в каждом классе образуют малое число несвязных компонент, то задача все же эффективно решается.
— На самом деле для получения положительных результатов мы доказали намного более общий результат: на задачу китайского почтальона с линейно упорядоченными (но не обязательно связанными) классами переносятся все алгоритмы для точного решения задачи деревенского почтальона. А про деревенского почтальона мы уже знаем почти все. К сожалению, с одним открытым вопросом нам все же не удалось разобраться: задача китайского почтальона с тремя связанными классами эффективно решается или NP-трудна? Мы до сих пор не знаем, — подытожил Рене ван Беверн.
