Проблема с китайским почтальоном

В теории графов , разделе математики и информатики , проблема маршрута Гуаня , проблема китайского почтальона , задача обхода почтальона или задача проверки маршрута состоит в том, чтобы найти кратчайший замкнутый путь или цепь, которая посещает каждое ребро (связного) неориентированного графа хотя бы один раз. . Когда граф имеет эйлерову схему (замкнутый обход, охватывающий каждое ребро один раз), эта схема является оптимальным решением. В противном случае задача оптимизации состоит в том, чтобы найти наименьшее количество дублируемых ребер графа (или подмножество ребер с минимально возможным общим весом), чтобы полученный мультиграф действительно имел эйлерову схему. ^{[ 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 -объединение (если оно существует) обязательно состоит из ${\tfrac {1}{2}}|T|$ пути, которые соединяют вершины T попарно. Пути будут такими, чтобы общая длина или общий вес всех них была как можно меньше. В оптимальном решении никакие два из этих путей не будут иметь общего ребра, но они могут иметь общие вершины. Минимальное T -соединение можно получить, построив полный граф на вершинах T с ребрами, представляющими кратчайшие пути в данном входном графе, а затем найдя идеальное паросочетание минимального веса в этом полном графе. Ребра этого паросочетания представляют собой пути в исходном графе, объединение которых образует желаемое T -объединение. Как построение полного графа, так и последующий поиск в нем паросочетания можно выполнить за O( n ³) вычислительные шаги.

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

Направленное решение

В ориентированном графе применимы те же общие идеи, но необходимо использовать другие методы. Если ориентированный граф эйлеров, достаточно найти цикл Эйлера. Если это не так, необходимо найти T -соединения, что в данном случае влечет за собой поиск путей от вершин с входной степенью, большей, чем их исходящая степень, к вершинам, у которых исходящая степень больше, чем их входная степень , так, чтобы они входная степень каждой вершины равна ее исходящей степени. Это можно решить как пример задачи о потоке с минимальными затратами , в которой на каждую единицу избыточной степени поступления приходится одна единица предложения, а на каждую единицу избыточной степени выхода — одна единица спроса. Таким образом, она разрешима за O(| V | ²| Е |) время. Решение существует тогда и только тогда, когда данный граф сильно связен . ^{[ 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 , Documenta Mathematica Series, Extra: 43–50, doi : 10.4171/дмс/6/10 , ISBN 978-3-936609-58-5 , МР 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
СМИ, связанные с проблемой проверки маршрута , на Викискладе?

[1] Робертс, Фред С.; Тесман, Барри (2009), Прикладная комбинаторика (2-е изд.), CRC Press, стр. 640–642, ISBN 9781420099829

[EdmondsJohnson-2] Перейти обратно: ^а ^б ^с Эдмондс, Дж.; Джонсон, Э.Л. (1973), «Сопоставление туров Эйлера и задача китайского почтальона» (PDF) , Mathematical Programming , 5 : 88–124, doi : 10.1007/bf01580113 , S2CID 15249924

[3] «Задача коммивояжера» (PDF) .

[4] Кван, Мей-ко (1960), «Графическое программирование с использованием нечетных или четных точек», Acta Mathematica Sinica (на китайском языке), 10 : 263–266, MR 0162630 . Переведено на китайскую математику 1 : 273–277, 1962.

[5] Питерс, Вреда; Блэк, Пол Э., ред. (2 сентября 2014 г.), «Проблема китайского почтальона» , Словарь алгоритмов и структур данных , Национальный институт стандартов и технологий , получено 26 апреля 2016 г.

[6] Гретшель, Мартин ; Юань, Я-сян (2012), «Эйлер, Мэй-Ко Кван, Кенигсберг и китайский почтальон» (PDF) , Истории оптимизации: 21-й Международный симпозиум по математическому программированию, Берлин, 19–24 августа 2012 г., Documenta Mathematica , Documenta Mathematica Series, Extra: 43–50, doi : 10.4171/дмс/6/10 , ISBN 978-3-936609-58-5 , МР 2991468 .

[7] Лоулер, Э. Л. (1976), Комбинаторная оптимизация: сети и матроиды , Холт, Райнхарт и Уинстон.

[8] Эйзельт, штат Ха; Жендо, Мишель; Лапорт, Гилберт (1995), «Проблемы маршрутизации дуги, Часть 1: Проблема китайского почтальона», Operations Research , 43 (2): 231–242, doi : 10.1287/opre.43.2.231 , hdl : 11059/14013

[9] А. Шрийвер, Комбинаторная оптимизация, многогранники и эффективность, том A, Springer. (2002).

[10] Крещенци, П.; Канн, В.; Халлдорссон, М.; Карпински, М .; Воегингер, Г. , Сборник задач оптимизации NP , KTH NADA, Стокгольм , получено 22 октября 2008 г.

[11] Гуань, Мейгу (1984), «О проблеме ветреного почтальона», Discrete Applied Mathematics , 9 (1): 41–46, doi : 10.1016/0166-218X(84)90089-1 , MR 0754427 .

[Complexity-12] Перейти обратно: ^а ^б Ленстра, Дж. К.; Риннуй Кан, AHG (1981), «Сложность задач маршрутизации и планирования транспортных средств» (PDF) , Networks , 11 (2): 221–227, doi : 10.1002/net.3230110211

[13] Робертс, Фред С.; Тесман, Барри (2009), Прикладная комбинаторика (2-е изд.), CRC Press, стр. 642–645, ISBN 9781420099829

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]