Смешанная задача китайского почтальона

Смешанная задача китайского почтальона (MCPP или MCP) — это поиск кратчайшего обхода графа с набором вершин V, набором неориентированных ребер E с положительными рациональными весами и набором направленных дуг A с положительными рациональными весами, которые охватывает каждое ребро или дугу хотя бы один раз с минимальными затратами. ^[1] доказал, что проблема -полна Пападимитриу NP . ^[2] Смешанная задача китайского почтальона часто возникает в задачах дуговой маршрутизации , таких как расчистка снега, когда некоторые улицы слишком узки, чтобы двигаться в обоих направлениях, в то время как другие улицы являются двунаправленными и могут быть расчищены в обоих направлениях. Легко проверить, имеет ли смешанный граф обход почтальона любого размера, проверив, является ли граф сильно связным. Проблема будет NP-сложной, если мы ограничим обход почтальона прохождением каждой дуги ровно один раз или если мы ограничим его прохождением каждого ребра ровно один раз, как доказал Сарагоса Мартинес. ^[3]^[4]

Математическое определение

Математическое определение:

Входные данные: сильно связный смешанный граф. $G=(V,E,A)$ со стоимостью $c(e)\geq 0$ для каждого края $e\subset E\cup A$ и максимальная стоимость $c_{max}$ .

Вопрос: существует ли (направленный) тур, проходящий через все ребра в $E$ и каждая дуга в $A$ хотя бы один раз и стоило не более $c_{max}$ ? ^[5]

Вычислительная сложность

Основная трудность в решении задачи «Смешанный китайский почтальон» заключается в выборе ориентации (ненаправленных) ребер, когда у нас ограниченный бюджет на обход и мы можем позволить себе пересечь каждое ребро только один раз. Затем нам нужно сориентировать ребра и добавить еще несколько дуг, чтобы получить ориентированный эйлеров граф, то есть сделать каждую вершину сбалансированной. Если к одной вершине инцидентны несколько ребер, определить правильную ориентацию каждого ребра непросто. ^[6] Математик Пападимитриу проанализировал эту проблему с большим количеством ограничений; «Смешанный китайский почтальон является NP-полным, даже если входной граф плоский, каждая вершина имеет степень не более трех, а каждое ребро и дуга имеют стоимость один». ^[7]

Эйлеров граф

Процесс проверки того, является ли смешанный граф эйлеровым, важен для создания алгоритма решения задачи смешанного китайского почтальона. Чтобы иметь эйлеров цикл, степени смешанного графа G должны быть четными, но этого недостаточно. ^[8]

Приближение

Тот факт, что смешанный китайский почтальон является NP-сложным, привел к поиску алгоритмов с полиномиальным временем, которые приближают оптимальное решение к разумному порогу. Фредериксон разработал метод с коэффициентом 3/2, который можно было применить к плоским графам. ^[9] а Рагхавачари и Вирасами нашли метод, который не обязательно должен быть плоским. ^[10] Однако полиномиальное время не позволяет определить стоимость снегохода, время, необходимое снегоочистителю, чтобы добраться до улиц, которые он вспахивает, или времени, которое требуется дворнику, чтобы добраться до улиц, которые он подметает. ^[11]^[12]

Формальное определение

Учитывая сильно связный смешанный граф $G=(V,E,A)$ с набором вершин $V$ и набор ребер $E$ , набор дуг $A$ и неотрицательная стоимость $c_{e}$ для каждого $e\in E\cup A$ MCPP заключается в поиске тура с минимальной стоимостью, проходящего через каждое звено $e\in E\cup A$ хотя бы один раз.

Данный $S\subset V$ , $\delta ^{+}(S)=\{(i,j)\in A:i\in S,j\in V\backslash S\}$ , $\delta ^{-}(S)=\{(i,j)\in A:i\in V\backslash S,j\in S\}$ , $\delta (S)$ обозначает множество ребер, имеющих ровно одну конечную точку в $S$ , и $\delta ^{\star }=\delta (S)\cup \delta ^{+}(S)\cup \delta ^{-}$ . Дана вершина ${\textstyle i}$ , $d_{i}^{-}$ (инградус) обозначает количество входящих дуг $i$ , $d_{i}^{+}$ (выходная степень) — количество дуг, выходящих из ${\textstyle i}$ , и $d_{i}$ (степень) — количество ссылок, инцидентных с $i$ . ^[13] Обратите внимание, что $d_{i}=|\delta ^{\star }(\{{i}\})|$ . Смешанный график $G=(V,E,A)$ называется четным, если все его вершины имеют четную степень, называется симметричным, если $d_{i}^{-}=d_{i}^{+}$ для каждой вершины ${\textstyle i}$ , и оно называется сбалансированным, если для любого подмножества $S$ вершин, разница между числом дуг, направленных из $S$ к $V\backslash S$ , $|\delta ^{+}(S)|$ , а количество дуг, направленных от $V\backslash S$ к $S$ , $|\delta ^{-}(S)|$ , не превышает числа ненаправленных ребер, соединяющих $S$ и $V\backslash S$ , $|\delta (S)|$ .

Хорошо известен тот факт, что смешанный граф $G$ является эйлеровым тогда и только тогда, когда $G$ ровный и сбалансированный. ^[14] Обратите внимание, что если $G$ четно и симметрично, то G также сбалансирована (и эйлерова). Более того, если $G$ четный, $MCPP$ может быть решена точно за полиномиальное время. ^[15]

Даже алгоритм MCPP

Дан четный и сильно связный смешанный граф. $G=(V,E,A)$ , позволять $A_{1}$ — набор дуг, полученный путем случайного присвоения направления ребрам в $E$ и с теми же затратами. Вычислить $s_{i}=d_{i}^{-}-d_{i}^{+}$ для каждой вершины i в ориентированном графе $(V,A\cup A_{1})$ . Вершина ${\textstyle i}$ с $s_{i}>0(s_{i}<0)$ будет рассматриваться как источник (приемник) со спросом на предложение $s_{i}(-s_{i})$ . Обратите внимание, что как $G$ представляет собой четный график, все предложения и потребности представляют собой четные числа (ноль считается четным числом).
Позволять $A_{2}$ быть набором дуг в направлении, противоположном дугам в $A_{1}$ и со стоимостью соответствующих ребер, и пусть $A_{3}$ - набор дуг, параллельных $A_{2}$ по нулевой стоимости.
Чтобы удовлетворить требования $s_{i}$ всех вершин решить задачу о потоке минимальной стоимости в графе $(V,A\cup A_{1}\cup A_{2}\cup A_{3})$ , в котором каждая дуга в $A\cup A_{1}\cup A_{2}$ имеет бесконечную емкость, и каждая дуга в $A_{3}$ имеет емкость 2. Пусть $x_{ij}$ быть оптимальным потоком.
Для каждой дуги $(i,j)$ в $A_{3}$ сделать: если $x_{ij}=2$ , затем ориентируем соответствующее ребро в $G$ от $i$ к $j$ (направление, от $j$ к $i$ , назначенный связанному ребру на шаге 1, был «неправильным»); если $x_{ij}=0$ , затем ориентируем соответствующее ребро в $G$ от $j$ к $i$ (в данном случае ориентация на шаге 1 была «правильной»). Обратите внимание на случай $x_{ij}=1$ невозможно, так как все значения перетекают через дуги в $A_{3}$ являются четными числами.
Дополнить $G$ добавив $x_{ij}$ копии каждой дуги в $A\cup A_{1}\cup A_{2}$ . Полученный граф четный и симметричный.

Эвристические алгоритмы

Когда смешанный граф нечетный и не все узлы имеют четную степень, граф можно преобразовать в четный граф.

Позволять $\mathrm {G=\{V,E,A\}}$ быть смешанным графом, который сильно связен . Найдите узлы нечетной степени, игнорируя направления дуг, и получите сопоставление с минимальной стоимостью. Дополните граф ребрами из сопоставления минимальной стоимости, чтобы создать четный граф. $\mathrm {G'=\{V',E',A'\}}$ .
Граф четный, но не симметричный, а смешанный эйлеров граф четный и симметричный. Решите задачу о потоке минимальных затрат в $G'$ чтобы получить симметричный граф, который может быть не четным $G''$ .
Последний шаг включает в себя создание симметричного графа $G''$ даже. Обозначьте узлы нечетной степени $V_{O}$ . Найдите циклы, которые чередуются между линиями в наборе дуг. $A''\backslash A$ и линии в наборе ребер $E''$ которые начинаются и заканчиваются в точках $V_{O}$ . Дуги в $A''\backslash A$ следует рассматривать как ненаправленные ребра, а не как направленные дуги.

Генетический алгоритм

Статья, опубликованная Hua Jiang et. Эл разработал генетический алгоритм для решения смешанной задачи китайского почтальона, оперируя популяцией. Алгоритм показал хорошие результаты по сравнению с другими алгоритмами аппроксимации для MCPP. ^[16]

См. также

Проблема с трассировкой емкостной дуги

Ссылки

^ Миниека, Эдвард (июль 1979 г.). «Задача китайского почтальона для смешанных сетей» . Наука управления . 25 (7): 643–648. дои : 10.1287/mnsc.25.7.643 . ISSN 0025-1909 .
^ Пападимитриу, Христос Х. (июль 1976 г.). «О сложности обхода ребер» . Журнал АКМ . 23 (3): 544–554. дои : 10.1145/321958.321974 . ISSN 0004-5411 . S2CID 8625996 .
^ Сарагоса Мартинес, Франциско (сентябрь 2006 г.). «Сложность смешанной задачи почтальона с ограничениями на дуги» . 2006 г. 3-я Международная конференция по электротехнике и электронике . IEEE. стр. 1–4. дои : 10.1109/iceee.2006.251877 . ISBN 1-4244-0402-9 .
^ Сарагоса Мартинес, Франциско (2006). «Сложность смешанной задачи почтальона с ограничениями на краях» . 2006 г. Седьмая Мексиканская международная конференция по информатике . IEEE. стр. 3–10. дои : 10.1109/enc.2006.9 . ISBN 0-7695-2666-7 . S2CID 17176905 .
^ Эдмондс, Джек; Джонсон, Эллис Л. (декабрь 1973 г.). «Сопоставление, туры Эйлера и китайский почтальон» . Математическое программирование . 5 (1): 88–124. дои : 10.1007/bf01580113 . ISSN 0025-5610 . S2CID 15249924 .
^ Корберан, Анхель (2015). Дуговая трассировка: проблемы, методы и приложения . ISBN 978-1-61197-366-2 .
^ Пападимитриу, Христос Х. (июль 1976 г.). «О сложности обхода ребер» . Журнал АКМ . 23 (3): 544–554. дои : 10.1145/321958.321974 . ISSN 0004-5411 . S2CID 8625996 .
^ Рэндольф, Форд, Лестер (2016). Потоки в сетях . Издательство Принстонского университета. ISBN 978-1-4008-7518-4 . OCLC 954124517 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Фредериксон, Грег Н. (июль 1979 г.). «Алгоритмы аппроксимации некоторых задач почтальона» . Журнал АКМ . 26 (3): 538–554. дои : 10.1145/322139.322150 . ISSN 0004-5411 . S2CID 16149998 .
^ Рагхавачари, Баладжи; Вирасами, Джеякесаван (январь 1999 г.). «Алгоритм приближения 3/2 для смешанной задачи почтальона» . SIAM Journal по дискретной математике . 12 (4): 425–433. дои : 10.1137/s0895480197331454 . ISSN 0895-4801 .
^ Сарагоса Мартинес, Франциско (2006). «Сложность смешанной задачи почтальона с ограничениями на краях» . 2006 г. Седьмая Мексиканская международная конференция по информатике . IEEE. стр. 3–10. дои : 10.1109/enc.2006.9 . ISBN 0-7695-2666-7 . S2CID 17176905 .
^ Сарагоса Мартинес, Франциско (сентябрь 2006 г.). «Сложность смешанной задачи почтальона с ограничениями на дуги» . 2006 г. 3-я Международная конференция по электротехнике и электронике . IEEE. стр. 1–4. дои : 10.1109/iceee.2006.251877 . ISBN 1-4244-0402-9 .
^ Корберан, Анхель (2015). Дуговая трассировка: проблемы, методы и приложения . ISBN 978-1-61197-366-2 .
^ Форд, ЛР (1962). Потоки в сетях . Принстон, Нью-Джерси: Издательство Принстонского университета.
^ Эдмондс, Джек; Джонсон, Эллис Л. (декабрь 1973 г.). «Сопоставление, туры Эйлера и китайский почтальон» . Математическое программирование . 5 (1): 88–124. дои : 10.1007/bf01580113 . ISSN 0025-5610 . S2CID 15249924 .
^ Цзян, Хуа; Канг, Лишань; Чжан, Шуци; Чжу, Фэй (2010), Цай, Чжихуа; Ху, Чэнъюй; Кан, Чжо; Лю, Юн (ред.), «Генетический алгоритм для смешанной задачи китайского почтальона» , «Достижения в области вычислений и интеллекта» , конспекты лекций по информатике, том. 6382, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 193–199, doi : 10.1007/978-3-642-16493-4_20 , ISBN 978-3-642-16492-7 , получено 25 октября 2022 г.

[1] Миниека, Эдвард (июль 1979 г.). «Задача китайского почтальона для смешанных сетей» . Наука управления . 25 (7): 643–648. дои : 10.1287/mnsc.25.7.643 . ISSN 0025-1909 .

[2] Пападимитриу, Христос Х. (июль 1976 г.). «О сложности обхода ребер» . Журнал АКМ . 23 (3): 544–554. дои : 10.1145/321958.321974 . ISSN 0004-5411 . S2CID 8625996 .

[3] Сарагоса Мартинес, Франциско (сентябрь 2006 г.). «Сложность смешанной задачи почтальона с ограничениями на дуги» . 2006 г. 3-я Международная конференция по электротехнике и электронике . IEEE. стр. 1–4. дои : 10.1109/iceee.2006.251877 . ISBN 1-4244-0402-9 .

[4] Сарагоса Мартинес, Франциско (2006). «Сложность смешанной задачи почтальона с ограничениями на краях» . 2006 г. Седьмая Мексиканская международная конференция по информатике . IEEE. стр. 3–10. дои : 10.1109/enc.2006.9 . ISBN 0-7695-2666-7 . S2CID 17176905 .

[5] Эдмондс, Джек; Джонсон, Эллис Л. (декабрь 1973 г.). «Сопоставление, туры Эйлера и китайский почтальон» . Математическое программирование . 5 (1): 88–124. дои : 10.1007/bf01580113 . ISSN 0025-5610 . S2CID 15249924 .

[6] Корберан, Анхель (2015). Дуговая трассировка: проблемы, методы и приложения . ISBN 978-1-61197-366-2 .

[7] Пападимитриу, Христос Х. (июль 1976 г.). «О сложности обхода ребер» . Журнал АКМ . 23 (3): 544–554. дои : 10.1145/321958.321974 . ISSN 0004-5411 . S2CID 8625996 .

[8] Рэндольф, Форд, Лестер (2016). Потоки в сетях . Издательство Принстонского университета. ISBN 978-1-4008-7518-4 . OCLC 954124517 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )

[9] Фредериксон, Грег Н. (июль 1979 г.). «Алгоритмы аппроксимации некоторых задач почтальона» . Журнал АКМ . 26 (3): 538–554. дои : 10.1145/322139.322150 . ISSN 0004-5411 . S2CID 16149998 .

[10] Рагхавачари, Баладжи; Вирасами, Джеякесаван (январь 1999 г.). «Алгоритм приближения 3/2 для смешанной задачи почтальона» . SIAM Journal по дискретной математике . 12 (4): 425–433. дои : 10.1137/s0895480197331454 . ISSN 0895-4801 .

[11] Сарагоса Мартинес, Франциско (2006). «Сложность смешанной задачи почтальона с ограничениями на краях» . 2006 г. Седьмая Мексиканская международная конференция по информатике . IEEE. стр. 3–10. дои : 10.1109/enc.2006.9 . ISBN 0-7695-2666-7 . S2CID 17176905 .

[12] Сарагоса Мартинес, Франциско (сентябрь 2006 г.). «Сложность смешанной задачи почтальона с ограничениями на дуги» . 2006 г. 3-я Международная конференция по электротехнике и электронике . IEEE. стр. 1–4. дои : 10.1109/iceee.2006.251877 . ISBN 1-4244-0402-9 .

[13] Корберан, Анхель (2015). Дуговая трассировка: проблемы, методы и приложения . ISBN 978-1-61197-366-2 .

[14] Форд, ЛР (1962). Потоки в сетях . Принстон, Нью-Джерси: Издательство Принстонского университета.

[15] Эдмондс, Джек; Джонсон, Эллис Л. (декабрь 1973 г.). «Сопоставление, туры Эйлера и китайский почтальон» . Математическое программирование . 5 (1): 88–124. дои : 10.1007/bf01580113 . ISSN 0025-5610 . S2CID 15249924 .

[16] Цзян, Хуа; Канг, Лишань; Чжан, Шуци; Чжу, Фэй (2010), Цай, Чжихуа; Ху, Чэнъюй; Кан, Чжо; Лю, Юн (ред.), «Генетический алгоритм для смешанной задачи китайского почтальона» , «Достижения в области вычислений и интеллекта» , конспекты лекций по информатике, том. 6382, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 193–199, doi : 10.1007/978-3-642-16493-4_20 , ISBN 978-3-642-16492-7 , получено 25 октября 2022 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]