루트 인스펙션 문제

Route inspection problem

그래프 이론에서, 수학과 컴퓨터 과학, 관의 경로 문제, 중국의 우체부 문제, 우체부 여행 또는 경로 검사 문제는 (연결된) 무방향 그래프의 모든 모서리를 방문하는 최단 폐쇄 경로 또는 회로를 찾는 것입니다.그래프에 오일러 회로(모든 에지를 한 번 커버하는 폐쇄형 워크)가 있는 경우 해당 회로가 최적의 솔루션입니다.그렇지 않은 경우, 최적화 문제는 복제할 그래프 에지의 최소 수(또는 가능한 최소 총 가중치를 가진 에지의 서브셋)를 찾아서 결과 멀티그래프가 오일러 [1]회로를 갖도록 하는 것입니다.그것은 다항식 [2]시간에 풀 수 있다.

이 문제는 원래 1960년 중국의 수학자 관메이코가 연구했는데,[3] 그의 중국어 논문은 1962년에 영어로 번역되었다."Chinese postman problem"이라는 원래 이름은 그를 기리기 위해 만들어졌다; 다른 출처는 그 당시 [4][5]미국 국가표준국에 있던 Alan J. Goldman이나 Jack Edmonds의 것으로 보고 있다.

일반화는 홀수도의 정점이 정확히 T의 정점인 그래프에서 모서리 세트로 결합되는 균등하게 많은 정점의 집합 T를 선택하는 것이다.이런 세트를 T-join이라고 합니다.이 문제, T-join 문제 또한 우체부 문제를 해결하는 것과 같은 접근방식으로 다항식 시간 내에 해결할 수 있습니다.

무방향 솔루션 및 T-join

무방향 루트 검사 문제는 T-join 개념에 기초한 알고리즘으로 다항식 시간에 해결할 수 있습니다.T를 그래프의 꼭지점 집합이라고 합니다.J에 홀수 수의 입사 에지가 있는 정점의 집합이 정확히 T인 경우 엣지 집합 J를 T 결합이라고 합니다. 그래프의 연결된 모든 구성요소가 T에 짝수 개의 정점을 포함할 때마다 T 결합이 존재합니다.T-join 문제는 가능한 최소 에지 수 또는 최소 총 무게를 가진 T-join을 찾는 것입니다.

모든 T에 대해 최소 T-join(존재하는 경우)은 반드시 T의 정점을 쌍으로 연결하는 로 됩니다.경로는 모든 경로의 총 길이 또는 총 중량이 가능한 한 작도록 해야 합니다.최적의 솔루션에서는 이들 경로 중 어느 것도 엣지를 공유하지 않지만 공유 정점이 있을 수 있습니다.최소 T-join은 주어진 입력 그래프에서 최단 경로를 나타내는 에지를 가진 T의 정점에 완전 그래프를 구성하고 이 완전 그래프에서 최소 무게 완전 일치를 구함으로써 얻을 수 있다.이 일치의 가장자리는 원하는 T-join을 형성하는 결합을 형성하는 원래 그래프의 경로를 나타냅니다.완전한 그래프를 구성하고 그 그래프에서 일치하는 그래프를 찾는 것은 모두 O(n3) 계산 단계에서 수행할 수 있습니다.

루트 인스펙션의 문제의 경우 홀수도의 모든 정점의 세트로 T를 선택해야 합니다.문제의 가정에 따라 그래프 전체가 연결되어 있고(그렇지 않으면 투어가 존재하지 않으며), 핸드쉐이크 보조법에 의해 홀수 정점이 짝수이므로 T-join은 항상 존재합니다.T-join의 모서리를 두 배로 하면 주어진 그래프가 오일러식 멀티그래프(모든 정점이 짝수 도를 갖는 연결 그래프)가 되고, 그 결과 멀티그래프의 각 모서리를 정확히 한 번 방문하는 투어인 오일러 투어가 있게 됩니다.이 투어는 루트인스펙션 [6][2]문제에 대한 최적의 해결책이 됩니다.

다이렉트 솔루션

유향 그래프에서는 동일한 일반적인 아이디어가 적용되지만 다른 기법을 사용해야 합니다.만약 유향 그래프가 오일러식이라면, 오일러 사이클만 찾으면 된다.그렇지 않으면 T-joins를 찾아야 합니다.T-joins는 이 경우 각 정점의 도수가 도수보다 큰 도수를 가진 정점에서 도수보다 큰 도수를 가진 정점까지의 경로를 찾아야 합니다.이 문제는 최소 비용 흐름 문제의 예로서 해결할 수 있습니다. 즉, 과잉 인도의 단위당 공급 단위가 1개이고 과잉 아웃도의 단위당 수요 단위가 1개입니다.따라서 O(V) 시간 내에 해결할 수 있습니다.주어진 그래프가 강하게 [2][7]연결된 경우에만 솔루션이 존재합니다.

적용들

평면 그래프에서 최대 컷을 찾고 [8]무방향 그래프에서 최소 평균 길이 회로를 찾는 것을 포함하여 다양한 조합 문제가 Chinese Postman 문제로 축소되었습니다.

변종

중국 우체국 문제의 몇 가지 변종이 연구되어 [9]NP-완전성이 입증되었다.

  • 윈디 우체국 문제는 루트 검사 문제의 변형입니다.입력된 그래프는 무방향 그래프이지만, 각 엣지는 한쪽 방향으로 그것을 통과하는 비용과 다른 방향으로 그것을 통과하는 비용이 다를 수 있습니다.방향 및 무방향 그래프의 솔루션과는 달리 NP-완전이다.[10][11]
  • 중국 우체부 혼재 문제: 이 문제에서는 일부 가장자리가 방향을 향하고 있기 때문에 한 방향에서만 볼 수 있습니다.이 문제로 인해 디그래프(또는 멀티그래프)의 최소한의 횡단이 필요할 경우 "뉴욕 스트리트 스위퍼 문제"[12]로 알려져 있습니다.
  • k-중국어 우체부 문제: 각 가장자리가 최소 한 사이클로 횡단되도록 지정된 위치에서 시작하는 k 사이클을 모두 찾습니다.목표는 가장 비용이 많이 드는 사이클의 비용을 최소화하는 것입니다.
  • "농촌 집배원 문제": [11]일부 모서리가 필요하지 않은 문제를 해결합니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Roberts, Fred S.; Tesman, Barry (2009), Applied Combinatorics (2nd ed.), CRC Press, pp. 640–642, ISBN 9781420099829
  2. ^ a b c Edmonds, J.; Johnson, E.L. (1973), "Matching Euler tours and the Chinese postman problem" (PDF), Mathematical Programming, 5: 88–124, doi:10.1007/bf01580113, S2CID 15249924
  3. ^ Kwan, Mei-ko (1960), "Graphic programming using odd or even points", Acta Mathematica Sinica (in Chinese), 10: 263–266, MR 0162630. 중국어 수학 1로 번역: 273~277, 1962.
  4. ^ Pieterse, Vreda; Black, Paul E., eds. (September 2, 2014), "Chinese postman problem", Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology, retrieved 2016-04-26
  5. ^ 를 클릭합니다Grötschel, Martin; Yuan, Ya-xiang (2012), "Euler, Mei-Ko Kwan, Königsberg, and a Chinese postman" (PDF), Optimization stories: 21st International Symposium on Mathematical Programming, Berlin, August 19–24, 2012, Documenta Mathematica, Extra: 43–50, MR 2991468.
  6. ^ Lawler, E.L. (1976), Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston
  7. ^ Eiselt, H. A.; Gendeaeu, Michel; Laporte, Gilbert (1995), "Arc Routing Problems, Part 1: The Chinese Postman Problem", Operations Research, 43 (2): 231–242, doi:10.1287/opre.43.2.231
  8. ^ A. 슈라이버, 조합 최적화, 다면체와 효율성, A권, 스프링거.(2002).
  9. ^ Crescenzi, P.; Kann, V.; Halldórsson, M.; Karpinski, M.; Woeginger, G, A compendium of NP optimization problems, KTH NADA, Stockholm, retrieved 2008-10-22
  10. ^ 를 클릭합니다Guan, Meigu (1984), "On the windy postman problem", Discrete Applied Mathematics, 9 (1): 41–46, doi:10.1016/0166-218X(84)90089-1, MR 0754427.
  11. ^ a b Lenstra, J.K.; Rinnooy Kan, A.H.G. (1981), "Complexity of vehicle routing and scheduling problems" (PDF), Networks, 11 (2): 221–227, doi:10.1002/net.3230110211
  12. ^ Roberts, Fred S.; Tesman, Barry (2009), Applied Combinatorics (2nd ed.), CRC Press, pp. 642–645, ISBN 9781420099829

외부 링크