Задача китайского почтальона

Перейти к навигацииПерейти к поиску

Задача китайского почтальона (англ. Chinese postman problem, CPP), маршрут почтальона или задача инспекции дорог заключается в поиске кратчайшего замкнутого пути или цикла, который проходит через каждое ребро (связного) взвешенного неориентированного графа. Если граф имеет эйлеров цикл (замкнутый маршрут, который проходит любое ребро ровно один раз), тогда этот цикл служит оптимальным решением. В противном случае задачей оптимизации является поиск наименьшего числа рёбер графа с повторными проходами (или подмножество рёбер с минимальным возможным общим весом), так что получающийся мультиграф имеет эйлеров цикл[1]. Эта задача может быть решена за полиномиальное время[2].

Задачу первоначально изучал в 1960 году китайский математик Гуань Мэйгу[кит.], отсюда и её название — задача китайского почтальона[3]. Статья Гуань Мэйгу была переведена с китайского на английский в 1962 году[4]. Различные источники приписывают это название либо Алану Дж. Голдману, либо Джеку Эдмондсу, которые работали в Национальном институте стандартов и технологий в то время[5][6].

Неориентированное решение

Неориентированная задача инспекции дорог может быть решена за полиномиальное время с помощью алгоритма, основанного на концепции T-соединении. Пусть T будет подмножеством множества вершин графа. Множество рёбер J называется T-соединением, если коллекция вершин, которые имеют нечётное число рёбер из J, соединяющих вершину с соседями, в точности совпадет с множеством T. T-соединение существует, если любая связная компонента графа содержит чётное число вершин из T. Задача T-соединения заключается в поиске T-соединения с наименьшим числом рёбер или наименьшим общим весом.

Для любого T наименьшее T-соединение (если существует) необходимо содержит путей, которые соединяют вершины T в пары. Пути будут такими, что полная длина или полный вес настолько малы, насколько возможно. В оптимальном решении никакие два из этих путей не будут иметь общие рёбра, но они могут иметь общие вершины. Наименьшее T-соединение может быть получено путём построения полного графа на вершинах из T с рёбрами, представляющими кратчайшие пути в заданном входном графе, а затем нахождение совершенного паросочетания наименьшего веса в этом полном графе. Рёбра паросочетания представляют пути в исходном графе, объединение которых образует желаемое T-соединение. Построение полного графа, а затем нахождения паросочетания в нём, может быть выполнено за шагов.

Для задачи инспекции дорог в качестве T следует выбирать множество всех вершин нечётной степени. По условиям задачи весь граф должен быть связен (иначе не существует обхода), а по лемме о рукопожатиях он имеет чётное число нечётных вершин, так что T-соединение всегда существует. Удвоение рёбер T-соединения приводит к тому, что данный граф становится эйлеровым мультиграфом (связным графом, в котором каждая вершина имеет чётную степень), откуда следует, что он имеет эйлеров цикл, маршрут, который посещает каждое ребро мультиграфа ровно раз. Этот маршрут будет оптимальным решением задачи инспекции дорог[7][2].

Ориентированное решение

На ориентированном графе применимы те же самые основные идеи, но должна быть использована другая техника. Если граф Эйлеров, нужно найти Эйлеров цикл. Если нет, нужно найти T-соединения, что подразумевает поиск путей из вершин с полустепенью входа большей её полустепени исхода в вершину, в которой полустепень исхода больше её полустепени входа, с целью сделать равной полустепень входа с полустепенью исхода для каждой вершины графа. Это можно решить как экземпляр задачи о потоке минимальной стоимости, в которой существует источник, равный полустепени входа, и потребитель, равный полустепени исхода. Такая задача решается за время . Решение существует тогда и только тогда, когда заданный граф сильно связен[2][8].

Задача почтальона с ветром

Задача почтальона с ветром является вариантом задачи инспекции дорог, в которой входом служит неориентированный граф, но в котором каждое ребро имеет разную цену для прохода в разных направлениях. В отличие о решений для ориентированных и неориентированных графов, задача NP-полна[9][10].

Приложения

Многочисленные комбинаторные задачи сводятся к задаче китайского почтальона, включая нахождение максимального сечения в планарном графе и цикла минимальной средней длины в неориентированном графе[11].

Варианты

Были изучены несколько вариантов задачи китайского почтальона и была показана их NP-полнота[12]

  • Минимизация задачи китайского почтальона для смешанных графов: в этой задаче некоторые из рёбер могут быть ориентированными и могут, поэтому, быть пройдены только в одном направлении. Если задача заключается в минимизации прохода орграфа (или мультиорграфа), она называется как «Задача очистки улиц Нью Йорка»[13].
  • Минимизация k-задачи китайского почтальона: найти k циклов, начинающихся в выбранном месте, таких, что каждое ребро проходится по меньшей мере в одном цикле. Целью является минимизация цены наиболее дорогого цикла.
  • Минимизация «задачи сельского почтальона»: решить задачу с необязательным проходом некоторых рёбер[10].

См. также

Примечания

  1. ↑ Roberts, Tesman, 2009, с. 640–642.
  2. ↑ 1 2 3 Edmonds, Johnson, 1973, с. 88–124.
  3. ↑ 陈琳. 中国邮递员问题 (кит.). Большая китайская энциклопедия, 3-е изд., онлайн. Дата обращения: 6 ноября 2022. Архивировано 6 ноября 2022 года.
  4. ↑ Kwan, 1960, с. 263–266.
  5. ↑ Pieterse, Black, 2014.
  6. ↑ Grötschel, Yuan, 2012, с. 43–50.
  7. ↑ Lawler, 1976.
  8. ↑ Eiselt, Gendeaeu, Laporte, 1995, с. 231–242.
  9. ↑ Guan, 1984, с. 41–46.
  10. ↑ 1 2 Lenstra, Rinnooy, 1981, с. 221–227.
  11. ↑ Schrijver, 2002.
  12. ↑ Crescenzi, Kann, 2000.
  13. ↑ Roberts, Tesman, 2009, с. 642–645.

Литература

  • Fred S. Roberts, Barry Tesman. Applied Combinatorics. — 2nd. — CRC Press, 2009. — ISBN 9781420099829.
  • Mei-ko Kwan. Graphic programming using odd or even points (Chinese) // Acta Mathematica Sinica. — 1960. — Т. 10. — С. 263–266.. Перевод в Chinese Mathematics 1: 273—277, 1962
  • Chinese postman problem // Dictionary of Algorithms and Data Structures / Vreda Pieterse, Paul E. Black. — National Institute of Standards and Technology, 2014.
  • Martin Grötschel, Ya-xiang Yuan. Euler, Mei-Ko Kwan, Königsberg, and a Chinese postman // Documenta Mathematica. — 2012. — Т. Extra. — С. 43–50. Архивировано 8 августа 2016 года.
  • Lawler E.L. Combinatorial Optimization: Networks and Matroids. — Holt, Rinehart and Winston, 1976.
  • Edmonds J., Johnson E.L. Matching Euler tours and the Chinese postman problem // Mathematical Programming. — 1973. — Т. 5. — doi:10.1007/bf01580113.
  • Schrijver A. Combinatorial Optimization, Polyhedra and Efficiency. — Springer, 2002. — Т. Volume A.
  • Eiselt H. A., Michel Gendeaeu, Gilbert Laporte. Arc Routing Problems, Part 1: The Chinese Postman Problem // Operations Research. — INFORMS, 1995. — Т. 43, вып. 2. — doi:10.1287/opre.43.2.231.
  • Meigu Guan. On the windy postman problem // Discrete Applied Mathematics. — 1984. — Т. 9, вып. 1. — С. 41–46. — doi:10.1016/0166-218X(84)90089-1.
  • Lenstra J.K., Rinnooy Kan A.H.G. Complexity of vehicle routing and scheduling problems // Networks. — 1981. — Т. 11, вып. 2. — doi:10.1002/net.3230110211.
  • A compendium of NP optimization problems / Crescenzi P., Kann V., Halldórsson M., Karpinski M., Woeginger G.. — KTH NADA, Stockholm, 2000.
  • Fred S. Roberts, Barry Tesman. Applied Combinatorics. — CRC Press, 2009. — ISBN 9781420099829.

Ссылки