중국집배원 혼혈문제

이 기사는 대부분의 독자들이 이해하기에는 너무 기술적인 것일 수 있습니다. 기술적인 세부사항을 삭제하지 않고 비전문가도 이해할 수 있도록 개선을 도와주시기 바랍니다.(2022년 5월) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

혼합 중국 우체부 문제(MCPP 또는 MCP)는 정점 V 집합, 양의 유리 가중치를 갖는 무방향 에지 E 집합 및 최소 비용으로 각 에지 또는 아크를 적어도 한 번 커버하는 양의 유리 가중치를 갖는 방향 호 A 집합으로 그래프의 최단 횡단을 검색하는 것입니다.^[1]이 문제는 파파디미트리우(Papadimitriou)에 의해 NP-완전한 것으로 증명되었습니다.^[2]혼합된 중국 우체부 문제는 제설기와 같은 호 경로 문제에서 종종 발생하는데, 일부 거리는 너무 좁아서 양방향으로 횡단할 수 없는 반면 다른 거리는 양방향으로 경작할 수 있습니다.그래프가 강하게 연결되어 있는지 확인하면 혼합 그래프에 크기에 상관없이 우체부 투어가 있는지 쉽게 확인할 수 있습니다.문제는 사라고사 마르티네스가 증명한 것처럼 우체부 투어가 각 호를 정확히 한 번만 횡단하도록 제한하거나 각 호를 정확히 한 번만 횡단하도록 제한하는 경우 NP hard입니다.^[3][4]

수학적 정의

수학적 정의는 다음과 같습니다.

입력: 강하게 연결된 혼합 그래프 $G$ = ${\displaystyle (V,}$ $,$ A) ${\displaystyle$ G = ($V$, E, A)}, 모든 에지 ⊂ E ∪ A {\displaystyle c(e)\geq 0}, 최대 비용 c $x$ {\displaystyle c_{max}의 ≥입니다.

질문: $E{\displaystyle }$ ${\displaystyle E}$의 모든 모서리와 $A$ ${\displaystyle A}$의 모든 호를 한 번 이상$$ 횡단하고 ${\displaystyle {\mathrm{최대}}_{}}$ ${\$의 비용이 드는 (방향) 투어가 있습니까$?$^[5]

계산 복잡도

혼합 중국 우체부 문제를 해결하는 데 있어 가장 큰 어려움은 여행 예산이 빠듯하고 각 가장자리를 한 번만 횡단할 수 있는 여유가 있을 때 (방향이 없는) 가장자리에 대한 방향을 선택하는 것입니다.그런 다음 방향 오일러 그래프, 즉 모든 정점이 균형을 이루도록 하기 위해 가장자리를 정렬하고 호를 추가해야 합니다.하나의 꼭짓점에 여러 개의 모서리가 결합되어 있는 경우 각 모서리의 올바른 방향을 결정하는 것은 쉬운 작업이 아닙니다.^[6]수학자 파파디미트리우는 이 문제를 더 많은 제약을 가하며 분석했습니다. "혼합된 중국 포스트맨은 NP-완전이며, 입력 그래프가 평면이라고 해도 각 정점은 많아야 3개의 차수를 가지며,^[7] 각 모서리와 호는 1개의 비용이 듭니다.

오일러 그래프

혼합 그래프가 오일러인지 확인하는 과정은 혼합 중국 우체부 문제를 해결하기 위한 알고리즘을 만드는 데 중요합니다.혼합 그래프 G의 정도는 오일러 사이클을 가지려면 짝수여야 하지만 충분하지 않습니다.^[8]

근사

혼합 중국 우편집배원이 NP-hard라는 사실은 최적해를 합리적인 임계값에 접근하는 다항식 시간 알고리즘을 찾게 만들었습니다.Frederickson은 평면 그래프에 적용할 수 있는 인자 3/2의 방법을 개발하였고,^[9] Raghavachari와 Veerasamy는 평면일 필요가 없는 방법을 발견하였습니다.^[10]그러나 다항식 시간은 막다른 골목에 도달하기 위해 눈 쟁기를 사용하거나 도로에 도달하기 위해 도로 청소부를 사용하는 비용을 찾을 수 없습니다.^[11][12]

형식적 정의

Given a strongly connected mixed graph ${\displaystyle G=(V,E,A)}$ with a vertex set ${\displaystyle V}$, and edge set ${\displaystyle E}$, an arc set ${\displaystyle A}$ and a nonnegative cost ${\displaystyle c_{e}}$ for each ${\displaystyle e\in E\cup A}$,MCPP는 각 $링크$∪ ${\displaystyle E}$ ∈ A ${\displaystyle$ e\$in$ E\cup A}를 최소 1회 이상 통과하는 최소 비용 투어를 찾는 것으로 구성됩니다.

Given ${\displaystyle S\subset V}$, ${\displaystyle \delta ^{+}(S)=\{(i,j)\in A:i\in S,j\in V\backslash S\}}$, ${\displaystyle \delta ^{-}(S)=\{(i,j)\in A:i\in V\backslash S,j\in S\}}$, ${\displaystyle \delta (S)}$ denotes the set of edges with exactly one endpoint in ${\displaystyle S}$, and ${\displaystyle \delta ^{\star }=\delta (S)\cup \delta ^{+}(S)\cup \delta ^{-}}$. Given a vertex ${\textstyle i}$, ${\displaystyle d_{i}^{-}}$(indegree) denotes the number of arcs enter ${\displaystyle i}$, ${\displaystyle d_{i}^{+}}$(outdegree) is thenumber of arcs leaving ${\textstyle i}$, and ${\displaystyle d_{i}}$ (degree) is the number of links incident with ${\displaystyle i}$.^[13] Note that ${\displaystyle d_{i}= \delta ^{\star }(\{{i}\}) }$. A mixed graph ${\displaystyle G=(V,E,A)}$ is called even if all of its vertices have even degree, it is called symmetric if ${\displaystyle d_{i}^{-}=d_{i}^{+}}$ for each vertex ${\textstyle i}$, and it is said to be balanced if, given any subset ${\displaystyle S}$ of vertices, the difference between the number of arcs directed from ${\displaystyle S}$ to ${\displaystyle V\backslash S}$, ${\displaystyle \delta ^{+}(S) }$, and thenumber of arcs directed from ${\displaystyle V\backslash S}$ to ${\displaystyle S}$, ${\displaystyle \delta ^{-}(S) }$, is no greater than the number of undirected edges joining ${\displaystyle S}$ and ${\displaystyle V\backslash S}$, ${\displaystyle \delta (S) }$.

$G{\displaystyle }$ ${\displaystyle G}$이(가) 균등하고 균형이 잡힌 경우에만 혼합 그래프 $G{\displaystyle }$ ${\displaystyle$ G$}$가 오일러라는$$ 것은 잘 알려진 사실입니다.^[14]$G{\displaystyle }$ ${\displaystyle G}$가 짝수이고 대칭이면 G도 균형을 이루게 됩니다(그리고 오일러).또한, ${\displaystyle G}$ ${\displaystyle G}$가 짝수이면, MCPP$${\$displaystyle MCPP}$는 $정확히{\displaystyle }$ 다항 시간 내에 해결될 수 있습니다$$.^[15]

짝수 MCPP 알고리즘

1. 균등하고 강하게 연결된 혼합 그래프 $G$ =${\displaystyle }$(${\displaystyle V,}$E$,$ A) ${\displaystyle$ G = (V, E, A)}가 주어졌을 때, Ai {\displaystyle A_{i}를 E {\displaystyle E}의 가장자리에 동일한 비용으로 임의로 방향을 할당한 호 집합이라고 합니다.Compute ${\displaystyle s_{i}=d_{j}^{-}-d_{i}^{+}}$ for each vertex i in the directed graph ${\displaystyle (V,A\cup A_{1})}$. A vertex ${\textstyle i}$ with ${\displaystyle s_{i}>0(s_{i}<0)}$ will be considered as a source (sink) with supply demand ${\displaystyle s_{i}(-s_{i})}$. N$G{\displaystyle }$ ${\displaystyle G}$가 짝수 그래프이므로 모든 공급 및 수요는 짝수입니다(0은 짝수로 간주됨).
2. $A{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$를 $A$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$에 있는 것과 반대$$ 방향의 호 집합으로 하고 해당 가장자리의 비용을 ${\displaystyle {포함}_{}}$하여 A 3 ${\$를 A ${\displaystyle {2\mathrm{}}_{}}$ ${\$에 평행한 호 집합으로 하고$$ 비용을 0으로 합니다$$.
3. To satisfy the demands ${\displaystyle s_{i}}$ of all the vertices, solve a minimum cost flow problem in the graph ${\displaystyle (V,A\cup A_{1}\cup A_{2}\cup A_{3})}$, in which each arc in ${\displaystyle A\cup A_{1}\cup A_{2}}$ has infinite capacity and each arc in ${\displaystyle A_{3}}$ has capacity 2.${\displaystyle {\mathrm{xij}}_{}}$ ${\$을(를) 최적 흐름이라고 합니다$$.
4. For each arc ${\displaystyle (i,j)}$ in ${\displaystyle A_{3}}$ do: If ${\displaystyle x_{ij}=2}$, then orient the corresponding edge in ${\displaystyle G}$ from ${\displaystyle i}$ to ${\displaystyle j}$ (the direction, from ${\displaystyle j}$ to ${\displaystyle i}$, assigned to the associated edge in step 1 was "wrong"); if ${\displaystyle x_{}}$${\displaystyle i_{}}$ ${\displaystyle j_{}}$ = ${\displaystyle 0}$ ${\$$displaystyle$ x_{i${\displaystyle j_{}}$}=0}인 다음 G의 해당 가장자리를 j {\displaystyle j}에서 i {\displaystyle i}(이 경우 1단계의 방향은 "오른쪽"이었습니다)로 향합니다.${\displaystyle {경우}_{}}$ ${\displaystyle x_{}}$ i$$j = 1 {\displaystyle x_{ij$}$=${\displaystyle 1}$}은(는) 불가능합니다. A 3 {\displaystyle A_{3}}의 호를 통한 모든 흐름 값은 짝수입니다.
5. ${\displaystyle {}_{}}$ ${\displaystyle A_{}}$의 각 $호의$ ${\displaystyle {\mathrm{xij}}_{}}$ ${\displaystyle x_{ij}$를 추가하여 G ${\displaystyle$ G$}$를 ∪ A1$$∪ $A2 {\displaystyle A_$1}\$cup$ A_{2}.결과 그래프는 균등하고 대칭적입니다.

휴리스틱 알고리즘

혼합 그래프가 짝수가 아니고 노드가 모두 짝수가 아닌 경우 그래프를 짝수 그래프로 변환할 수 있습니다.

• $G$ =${\displaystyle }${${\displaystyle \mathrm{V},}$E, A } {\displaystyle \mathrm {G=\{V,E,A\}}을(를) 강하게 연결된 혼합 그래프라고 합니다.아크 방향을 무시하여 홀수 차수 노드를 찾고 최소 비용 매칭을 구합니다.최소 비용 매칭의 에지로 그래프를 확대하여 짝수 그래프 $G$ =${\displaystyle }${$',$ E', A' } {\displaystyle {G'=\{V',E',A'}를 생성합니다.
• 그래프는 짝수이지만 대칭이 아니며 오일러 혼합 그래프는 짝수 및 대칭입니다.$G{\displaystyle {\text{'}}^{}}$ ${\$$displaystyle$ $G'}$에서 최소 비용 흐름 문제를 해결하여 $G$ ″ {\$displaystyle$G'}이(가) 아닐 수 있는 대칭 그래프를 구합니다.
• 마지막 단계는 대칭 그래프 $G$″ {\$displaystyle$ G`}을(를) 균등하게 하는 것입니다.Label the odd degree nodes ${\displaystyle V_{O}}$. Find cycles that alternate between lines in the arc set ${\displaystyle A''\backslash A}$ and lines in the edge set ${\displaystyle E''}$ that start and end at points in ${\displaystyle V_{O}}$. The arcs in ${\displaystyle A''\backslash A}$ should be considered as undirected지시된 호가 아닌 에지입니다.

유전 알고리즘

Hua Jiang et al. 이 발표한 논문은 인구를 대상으로 조작하여 중국 우체부 혼혈 문제를 해결하는 유전 알고리즘을 제시했습니다.알고리즘은 MCPP의 다른 근사 알고리즘에 비해 성능이 뛰어났습니다.^[16]

참고 항목

• 정전식 아크 라우팅 문제

참고문헌