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

Задача китайского почтальона (англ. Chinese postman problem, CPP) — это задача из теории графов и комбинаторной оптимизации, заключающаяся в поиске кратчайшего замкнутого маршрута (цикла), который проходит по каждому ребру взвешенного неориентированного графа как минимум один раз и возвращается в исходную вершину. Задача названа в честь китайского математика Гуань Мэйгу (Mei-Ko Kwan), который впервые сформулировал её в 1960 году, рассматривая проблему оптимизации маршрута почтальона, доставляющего корреспонденцию по всем улицам района. В западной литературе задача также известна как «маршрут почтальона» (Route Inspection Problem). Задача китайского почтальона является NP-трудной для ориентированных и смешанных графов, но для неориентированных графов решается за полиномиальное время.

Формальная постановка

Пусть задан связный неориентированный взвешенный граф \( G = (V, E) \) с множеством вершин \( V \) и множеством рёбер \( E \), каждому ребру \( e \in E \) приписана неотрицательная длина (вес) \( w(e) \). Требуется найти замкнутый маршрут (цикл), начинающийся и заканчивающийся в одной и той же вершине, который проходит по каждому ребру графа хотя бы один раз, при этом суммарная длина пройденных рёбер минимальна. Допускается прохождение по одному и тому же ребру несколько раз.

История

В 1960 году китайский математик Гуань Мэйгу, работавший в Шаньдунском университете, опубликовал статью «Graphic programming using odd or even points» в китайском журнале «Acta Mathematica Sinica». В ней он рассмотрел практическую задачу почтальона, который должен обойти все улицы своего участка, минимизируя общий путь. Гуань Мэйгу показал, что если граф улиц является эйлеровым (то есть все вершины имеют чётную степень), то оптимальный маршрут — это эйлеров цикл, проходящий по каждому ребру ровно один раз. В противном случае необходимо добавить некоторые рёбра (пройти их повторно), чтобы сделать граф эйлеровым.

В 1962 году американский математик Джек Эдмондс (Jack Edmonds) независимо переоткрыл задачу и дал ей название «Chinese postman problem» в честь её первооткрывателя. В 1973 году Эдмондс совместно с Эллисом Джонсоном (Ellis L. Johnson) опубликовал фундаментальную работу, в которой предложил эффективный алгоритм решения для неориентированных графов, основанный на сведении к задаче о паросочетании минимального веса.

Связь с эйлеровыми графами

Задача китайского почтальона тесно связана с понятием эйлерова графа. Граф называется эйлеровым, если существует цикл, проходящий по каждому ребру ровно один раз. Согласно теореме Эйлера, связный неориентированный граф является эйлеровым тогда и только тогда, когда все его вершины имеют чётную степень.

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

Алгоритм решения для неориентированных графов

Для неориентированных графов задача китайского почтальона решается за полиномиальное время с помощью следующего алгоритма, предложенного Эдмондсом и Джонсоном:

1. Выделение вершин нечётной степени. Найти в графе \( G \) все вершины, степень которых нечётна. Обозначим их множество \( O \). Количество таких вершин чётно.

1. Вычисление кратчайших путей. Для каждой пары вершин из \( O \) вычислить кратчайшее расстояние (сумму весов рёбер) между ними в исходном графе \( G \) с помощью алгоритма Флойда — Уоршелла или алгоритма Дейкстры (для каждого источника). Получается полный граф на множестве \( O \), где вес ребра равен кратчайшему расстоянию между соответствующими вершинами.

1. Поиск минимального совершенного паросочетания. На полном графе, построенном на множестве \( O \), найти совершенное паросочетание минимального суммарного веса. Это означает, что все вершины нечётной степени разбиваются на пары, и для каждой пары выбирается кратчайший путь между ними. Задача о минимальном совершенном паросочетании на полном графе с чётным числом вершин решается за полиномиальное время, например, алгоритмом Эдмондса (Blossom algorithm).

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

1. Поиск эйлерова цикла. В полученном эйлеровом мультиграфе \( G' \) найти эйлеров цикл, например, с помощью алгоритма Флёри или алгоритма Хирхольцера. Этот цикл является оптимальным решением задачи китайского почтальона.

Суммарная длина оптимального маршрута равна сумме весов всех рёбер исходного графа плюс суммарный вес добавленных рёбер (кратчайших путей между парами вершин нечётной степени).

Варианты задачи

Ориентированные графы

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

Смешанные графы

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

Задача с несколькими почтальонами

Существует обобщение задачи, известное как «задача нескольких почтальонов» (k-Chinese postman problem), где требуется найти k замкнутых маршрутов, которые вместе покрывают все рёбра графа, минимизируя суммарную или максимальную длину маршрута. Эта задача также является NP-трудной.

Применение

Задача китайского почтальона имеет широкий спектр практических приложений:

• Логистика и транспорт: оптимизация маршрутов доставки почты, уборки улиц, вывоза мусора, патрулирования территорий, инспекции дорог и линий электропередач.
• Робототехника: планирование маршрутов роботов-уборщиков, газонокосилок, дронов для инспекции объектов.
• Компьютерные сети: маршрутизация пакетов в сетях с гарантированной доставкой, тестирование сетевых соединений.
• Биоинформатика: анализ последовательностей ДНК, сборка геномов.
• Проектирование печатных плат: оптимизация трассировки дорожек.

Пример

Рассмотрим простой граф с четырьмя вершинами (A, B, C, D) и четырьмя рёбрами: AB (вес 2), BC (вес 3), CD (вес 4), DA (вес 5). Степени вершин: A — 2 (чётная), B — 2 (чётная), C — 2 (чётная), D — 2 (чётная). Граф является эйлеровым (цикл A-B-C-D-A). Оптимальный маршрут — пройти по каждому ребру один раз, суммарная длина 2+3+4+5 = 14.

Если добавить ребро AC (вес 6), то степени станут: A — 3 (нечётная), B — 2 (чётная), C — 3 (нечётная), D — 2 (чётная). Вершины нечётной степени — A и C. Кратчайший путь между ними — прямое ребро AC (вес 6). Добавляем его, получаем эйлеров граф. Оптимальный маршрут будет проходить по всем рёбрам, включая повторное прохождение AC, суммарная длина 2+3+4+5+6 = 20.

Критика и ограничения

Основным ограничением классической задачи китайского почтальона является предположение, что все рёбра графа должны быть пройдены хотя бы один раз, что не всегда соответствует реальности (например, если некоторые улицы не требуют обслуживания). Кроме того, задача не учитывает временные окна, ограничения на скорость движения, одностороннее движение (кроме ориентированных вариантов) и динамические изменения в сети. На практике часто используются эвристические алгоритмы и методы приближённого решения, особенно для крупных графов.

Интересные факты

• Задача китайского почтальона является одной из первых задач комбинаторной оптимизации, для которой был разработан эффективный алгоритм, основанный на теории паросочетаний.
• В 1970-х годах задача активно изучалась в СССР в рамках исследования проблем транспортной логистики.
• Существует версия задачи, называемая «задача сельского почтальона» (Rural postman problem), где требуется пройти только подмножество рёбер графа; она является NP-трудной.

Источники

• Kwan, Mei-Ko. «Graphic programming using odd or even points.» Chinese Mathematics, 1 (1960), 273–277.
• Edmonds, J., Johnson, E.L. «Matching, Euler tours and the Chinese postman.» Mathematical Programming, 5 (1973), 88–124.
• Lawler, E.L. «Combinatorial Optimization: Networks and Matroids.» Holt, Rinehart and Winston, 1976.
• Ahuja, R.K., Magnanti, T.L., Orlin, J.B. «Network Flows: Theory, Algorithms, and Applications.» Prentice Hall, 1993.