Проблема с китайским почтальоном
| 1 | Каждую улицу необходимо пересечь хотя бы один раз, начиная и заканчивая почтовым отделением в пункте А. |
|---|---|
| 2 | На эквивалентном графе найдены четыре вершины нечетной степени (оранжевые). |
| 3 | Находится пара с наименьшей общей длиной. |
| 4 | После добавления соответствующих ребер (красные) находится длина эйлеровой схемы. |
В теории графов , разделе математики и информатики , проблема маршрута Гуаня , проблема китайского почтальона , задача обхода почтальона или задача проверки маршрута состоит в том, чтобы найти кратчайший замкнутый путь или цепь, которая посещает каждое ребро (связного) неориентированного графа хотя бы один раз. . Когда граф имеет эйлерову схему (замкнутый обход, охватывающий каждое ребро один раз), эта схема является оптимальным решением. В противном случае задача оптимизации состоит в том, чтобы найти наименьшее количество дублируемых ребер графа (или подмножество ребер с минимально возможным общим весом), чтобы полученный мультиграф действительно имел эйлерову схему. [1] Решить ее можно за полиномиальное время . [2] в отличие от задачи коммивояжера, которая является NP-трудной . [3] Она отличается от задачи коммивояжера тем, что коммивояжер не может повторять посещенные узлы.
Первоначально проблему изучал китайский математик Кван Мэй-Ко в 1960 году, чья китайская статья была переведена на английский язык в 1962 году. [4] Первоначальное название «Задача китайского почтальона» было придумано в его честь; разные источники приписывают чеканку либо Алану Дж. Голдману , либо Джеку Эдмондсу , оба из которых работали в Национальном бюро стандартов США . в то время [5] [6]
Обобщение состоит в том, чтобы выбрать любое множество T из четного числа вершин, которые должны быть соединены множеством ребер в графе, вершины нечетной степени которого в точности совпадают с вершинами T . Такое множество называется T -объединением. Эта проблема, проблема T -объединения , также разрешима за полиномиальное время с помощью того же подхода, который решает проблему почтальона.
Ненаправленное решение и T -объединения [ править ]
Задача ненаправленной проверки маршрута может быть решена за полиномиальное время с помощью алгоритма, основанного на концепции T -объединения.Пусть T — множество вершин графа. Множество ребер J называется T -объединением если совокупность вершин, имеющих нечетное число инцидентных ребер в J, в точности равна множеству T. , T - когда каждый компонент связности графа содержит четное количество вершин из T. объединение существует , Задача T -объединения состоит в том, чтобы найти T -объединение с минимально возможным количеством ребер или минимально возможным общим весом.
Для любого T наименьшее T -объединение (если оно существует) обязательно состоит из пути, которые соединяют вершины T попарно. Пути будут такими, чтобы общая длина или общий вес всех них была как можно меньше. В оптимальном решении никакие два из этих путей не будут иметь общего ребра, но они могут иметь общие вершины. Минимальное T -соединение можно получить, построив полный граф на вершинах T с ребрами, представляющими кратчайшие пути в данном входном графе, а затем найдя идеальное паросочетание минимального веса в этом полном графе. Ребра этого паросочетания представляют собой пути в исходном графе, объединение которых образует желаемое T -объединение.Как построение полного графа, так и поиск в нем паросочетания можно выполнить за O( n 3 ) вычислительные шаги.
Для задачи проверки маршрута T следует выбрать как набор всех вершин нечетной степени. По условиям задачи весь граф связен (иначе никакого обхода не существует), а по лемме о установлении связи он имеет четное число нечетных вершин, поэтому T -объединение всегда существует. Удвоение ребер T -объединения приводит к тому, что данный граф становится эйлеровым мультиграфом (связным графом, в котором каждая вершина имеет четную степень), из чего следует, что он имеет эйлеров тур — тур, который посещает каждое ребро мультиграфа. ровно один раз. Этот тур станет оптимальным решением проблемы осмотра маршрута. [7] [2]
Направленное решение [ править ]
В ориентированном графе применимы те же общие идеи, но необходимо использовать другие методы. Если ориентированный граф эйлеров, достаточно найти цикл Эйлера. Если это не так, необходимо найти T -соединения, что в данном случае влечет за собой поиск путей от вершин с входной степенью, большей, чем их исходящая степень, к вершинам, у которых исходящая степень больше, чем их входная степень , так, чтобы они входная степень каждой вершины равна ее исходящей степени. Это можно решить как пример задачи о потоке с минимальными затратами , в которой на каждую единицу избыточной степени поступления приходится одна единица предложения, а на каждую единицу избыточной степени выхода — одна единица спроса. Таким образом, она разрешима за O(| V | 2 | Е |) время. Решение существует тогда и только тогда, когда данный граф сильно связен . [2] [8]
Приложения [ править ]
Различные комбинаторные задачи были сведены к задаче китайского почтальона, включая поиск максимального разреза в плоском графе. и схема минимальной средней длины в неориентированном графе. [9]
Варианты [ править ]
Несколько вариантов китайской проблемы почтальона были изучены и оказались NP-полными . [10]
- Задача ветренного почтальона — это вариант задачи проверки маршрута, в которой входными данными является неориентированный граф, но где каждое ребро может иметь разную стоимость прохождения его в одном направлении и стоимость прохождения в другом направлении. В отличие от решений для ориентированных и неориентированных графов оно NP-полное . [11] [12]
- Задача смешанного китайского почтальона : в этой задаче некоторые ребра могут быть направленными и, следовательно, их можно посетить только с одного направления. Когда задача требует минимального обхода орграфа (или мультидиграфа), она известна как «задача подметателя улиц Нью-Йорка». [13]
- Задача k -китайского почтальона: найти k циклов, начинающихся в указанном месте, так, что каждое ребро пересекается хотя бы одним циклом. Цель состоит в том, чтобы минимизировать стоимость самого дорогого цикла.
- «Задача сельского почтальона»: решить задачу, в которой некоторые ребра не нужны. [12]
См. также [ править ]
Ссылки [ править ]
- ^ Робертс, Фред С.; Тесман, Барри (2009), Прикладная комбинаторика (2-е изд.), CRC Press, стр. 640–642, ISBN 9781420099829
- ↑ Перейти обратно: Перейти обратно: а б с Эдмондс, Дж.; Джонсон, Э.Л. (1973), «Сопоставление туров Эйлера и задача китайского почтальона» (PDF) , Mathematical Programming , 5 : 88–124, doi : 10.1007/bf01580113 , S2CID 15249924
- ^ «Задача коммивояжера» (PDF) .
- ^ Кван, Мей-ко (1960), «Графическое программирование с использованием нечетных или четных точек», Acta Mathematica Sinica (на китайском языке), 10 : 263–266, MR 0162630 . Переведено на китайскую математику 1 : 273–277, 1962.
- ^ Питерс, Вреда; Блэк, Пол Э., ред. (2 сентября 2014 г.), «Проблема китайского почтальона» , Словарь алгоритмов и структур данных , Национальный институт стандартов и технологий , получено 26 апреля 2016 г.
- ^ Гретшель, Мартин ; Юань, Я-сян (2012), «Эйлер, Мэй-Ко Кван, Кенигсберг и китайский почтальон» (PDF) , Истории оптимизации: 21-й Международный симпозиум по математическому программированию, Берлин, 19–24 августа 2012 г., Documenta Mathematica , Экстра: 43–50, МР 2991468 .
- ^ Лоулер, Э. Л. (1976), Комбинаторная оптимизация: сети и матроиды , Холт, Райнхарт и Уинстон.
- ^ Эйзельт, штат Ха; Жендо, Мишель; Лапорт, Гилберт (1995), «Проблемы маршрутизации дуги, Часть 1: Проблема китайского почтальона», Operations Research , 43 (2): 231–242, doi : 10.1287/opre.43.2.231 , hdl : 11059/14013
- ^ А. Шрийвер, Комбинаторная оптимизация, многогранники и эффективность, том A, Springer. (2002).
- ^ Крещенци, П.; Канн, В.; Халлдорссон, М.; Карпински, М .; Воегингер, Г. , Сборник задач оптимизации NP , KTH NADA, Стокгольм , получено 22 октября 2008 г.
- ^ Гуань, Мейгу (1984), «О проблеме ветреного почтальона», Discrete Applied Mathematics , 9 (1): 41–46, doi : 10.1016/0166-218X(84)90089-1 , MR 0754427 .
- ↑ Перейти обратно: Перейти обратно: а б Ленстра, Дж. К.; Риннуй Кан, AHG (1981), «Сложность задач маршрутизации и планирования транспортных средств» (PDF) , Networks , 11 (2): 221–227, doi : 10.1002/net.3230110211
- ^ Робертс, Фред С.; Тесман, Барри (2009), Прикладная комбинаторика (2-е изд.), CRC Press, стр. 642–645, ISBN 9781420099829
Внешние ссылки [ править ]
- Вайсштейн, Эрик В. , «Задача о китайском почтальоне» , MathWorld
СМИ, связанные с проблемой проверки маршрута , на Викискладе?
