Проблема проверки маршрута - Route inspection problem

В теория графов, филиал математика и Информатика, то Проблема китайского почтальона, почтальон тур или проблема проверки маршрута состоит в том, чтобы найти кратчайший замкнутый путь или схему, которая посещает каждое ребро неориентированный граф. Когда на графике есть Контур Эйлера (закрытый обход, который охватывает каждое ребро один раз), эта схема является оптимальным решением. В противном случае задача оптимизации состоит в том, чтобы найти наименьшее количество ребер графа для дублирования (или подмножество ребер с минимально возможным общим весом) так, чтобы результирующий мультиграф имеет эйлерову схему.^[1] Это можно решить в полиномиальное время.^[2]

Первоначально проблема была изучена китайским математиком. Кван Мей-Ко в 1960 г., чья китайская статья была переведена на английский в 1962 г.^[3] Первоначальное название «Проблема китайского почтальона» было придумано в его честь; разные источники приписывают чеканку либо Алан Дж. Голдман или Джек Эдмондс, оба были в Национальное бюро стандартов США в то время.^[4][5]

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

Ненаправленное решение и Т-соединяется

Проблема ненаправленного осмотра маршрута может быть решена в полиномиальное время по алгоритм основанный на концепции Т-join.Let Т - множество вершин графа. Набор кромок J называется Т-присоединиться если набор вершин с нечетным числом инцидентных ребер в J это точно набор Т. А Т-соединение существует всякий раз, когда каждая связная компонента графа содержит четное число вершин в Т. В Т-соединиться проблема найти Т-соединить с минимально возможным количеством ребер или минимально возможным общим весом.

Для любого Т, самый маленький Т-соединение (если оно существует) обязательно состоит из ${\displaystyle {\tfrac {1}{2}}|T|}$ пути, соединяющие вершины Т в парах. Дорожки должны быть такими, чтобы общая длина или общий вес всех из них был как можно меньше. В оптимальном решении никакие два из этих путей не будут иметь общих ребер, но у них могут быть общие вершины. Минимум Т-соединение можно получить, построив полный график на вершинах Т, с ребрами, которые представляют кратчайшие пути в данном входном графе, а затем нахождение минимальный вес идеальное соответствие в этом полном графике. Ребра этого сопоставления представляют собой пути в исходном графе, объединение которых образует желаемый ТКак построение полного графа, так и поиск в нем сопоставления можно выполнить за O (п³) вычислительные шаги.

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

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

К ориентированному графу применимы те же общие идеи, но должны использоваться разные методы. Если ориентированный граф эйлеров, достаточно найти эйлеров цикл. Если это не так, нужно найти Т-соединения, что в данном случае влечет за собой нахождение путей из вершин с входомстепень больше, чем их выходстепень тем, у кого есть выходстепень больше, чем их в-степень так, чтобы они делали входящую степень каждой вершины равной ее исходящей степени. Это может быть решено как пример проблема минимальных затрат в котором есть одна единица предложения на каждую единицу избыточного внутреннего градуса и одну единицу спроса на каждую единицу избыточного исходящего градуса. Как таковая, она разрешима в O (|V|²|E|) время. Решение существует тогда и только тогда, когда данный граф сильно связанный.^[2][7]

Проблема ветреного почтальона

В проблема ветреного почтальона - это вариант задачи проверки маршрута, в которой входом является неориентированный граф, но каждое ребро может иметь разные затраты на прохождение по нему в одном направлении, чем за обход в другом направлении. В отличие от решений для направленного и неориентированного графики, это НП-полный.^[8][9]

Приложения

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

Варианты

Несколько вариантов задачи китайского почтальона были изучены и показали, что НП-полный.^[11]

• Задача китайского почтальона для смешанных графов: в этой задаче некоторые ребра могут быть направлены и, следовательно, могут быть посещены только с одного направления. Когда проблема требует минимального обхода орграфа (или мультидиграфа), она известна как «проблема New York Street Sweeper».^[12]
• В k-Китайский почтальон проблема: найти k все циклы начинаются в назначенном месте, так что каждое ребро проходит по крайней мере за один цикл. Цель - минимизировать стоимость самого дорогостоящего цикла.
• «Задача сельского почтальона»: решить задачу с некоторыми ненужными краями. ^[9]

Смотрите также

• Проблема коммивояжера

использованная литература

1. Робертс, Фред С .; Тесман, Барри (2009), Прикладная комбинаторика (2-е изд.), CRC Press, стр. 640–642, ISBN  9781420099829
2. Эдмондс, Дж .; Джонсон, Э. (1973), «Соответствие туров Эйлера и проблема китайского почтальона» (PDF), Математическое программирование, 5: 88–124, Дои:10.1007 / bf01580113, S2CID  15249924
3. Кван, Мэй-ко (1960), «Графическое программирование с использованием нечетных или четных точек», Acta Mathematica Sinica (на китайском), 10: 263–266, Г-Н  0162630. Переведено на Китайская математика 1: 273–277, 1962.
4. Питерс, Вреда; Блэк, Пол Э., ред. (2 сентября 2014 г.), "Проблема китайского почтальона", Словарь алгоритмов и структур данных, Национальный институт стандартов и технологий, получено 2016-04-26
5. Грётшель, Мартин; Юань, Я-сян (2012), «Эйлер, Мей-Ко Кван, Кенигсберг и китайский почтальон» (PDF), Истории оптимизации: 21-й Международный симпозиум по математическому программированию, Берлин, 19–24 августа 2012 г., Documenta Mathematica, Экстра: 43–50, Г-Н  2991468.
6. Лоулер, Э. (1976), Комбинаторная оптимизация: сети и матроиды, Холт, Райнхарт и Уинстон
7. Eiselt, H.A .; Gendeaeu, Michel; Лапорт, Гилберт (1995). «Проблемы трассировки дуги, часть 1: проблема китайского почтальона». Исследование операций. ИНФОРМАЦИЯ. 43 (2): 231–242. Дои:10.1287 / opre.43.2.231.
8. Гуань, Мейгу (1984), «О ветреной проблеме почтальона», Дискретная прикладная математика, 9 (1): 41–46, Дои:10.1016 / 0166-218X (84) 90089-1, Г-Н  0754427.
9. Lenstra, J.K .; Ринноой Кан, A.H.G. (1981), «Сложность определения маршрута и расписания транспортных средств» (PDF), Сети, 11 (2): 221–227, Дои:10.1002 / нетто.3230110211
10. А. Шрайвер, Комбинаторная оптимизация, многогранники и эффективность, том A, Springer. (2002).
11. Crescenzi, P .; Канн, В .; Halldórsson, M .; Карпинский, М.; Woeginger, G. «Сборник задач оптимизации НП». KTH NADA, Стокгольм. Получено 2008-10-22.
12. Робертс, Фред С .; Тесман, Барри (2009), Прикладная комбинаторика (2-е изд.), CRC Press, стр. 642–645, ISBN  9781420099829

внешняя ссылка

• Вайсштейн, Эрик В. "Проблема китайского почтальона". MathWorld.
• СМИ, связанные с Проблема проверки маршрута в Wikimedia Commons