최단 시간에 도로를 포장하십시오.

당신은 마을 동사무소의 토목과 직원입니다.

비포장의 도로 네트워크를 (인손 부족이므로) 혼자 포장해야 합니다.

마지막으로 작업 시작 지점으로 돌아가야합니다.

가능한 한 빨리 작업을 완료하고 싶습니다.

사고방식

모든 변(도로)을 따라가는 폐로(일주해서 돌아오는 경로)를 구하는 문제를, 중국인 우편 배달 문제라고 합니다.
워셜 플로이드 방법을 이용하여 다항식 시간으로 계산할 수 있습니다만, 여기서는 조합 최적화 의 혼합 정수 최적화 문제라고 파악해 풀기로 합니다.
연결 그래프의 모든 점의 차수(점에 접속하고 있는 변의 수)가 짝수이면, 폐로가 존재하는 것이 알려져 있습니다. 차수가 홀수일 때는 같은 도로 위를 왕복하여 짝수가 되도록 하면 됩니다.

정책으로서는, 도로를 왕복할지 어떨지를 요구하기로 합니다.
(차수가 모두 짝수인 그래프의 폐로는 비교적 간단하게 구해지므로, 여기서는 생략합니다.)

공식화

최소화
$\sum_i{x_i}$
왕복하는 도로

변수
$x_i\in\{0, 1\} ~\forall i\in 도로$
왕복할지 여부

$y_j\ge 0,\in 정수 ~\forall j\in 점$
점 차수의 절반

제약
$\sum_{i\in 점 j에 연결된 변}{~~~~~~~~~~~~ x_i + 점 j의 차수} = 2 y_j\forall j\in 점$
차수가 짝수

(이 공식화는 그다지 좋지 않으므로 실제로는 다른 방법이 좋습니다.)

파이썬에서 실행

임의의 그래프를 만듭니다.

python3

%matplotlib inline
import networkx as nx
from pulp import *
g = nx.random_graphs.fast_gnp_random_graph(8, 0.3, 11)
pos = nx.spring_layout(g)
nx.draw_networkx_nodes(g, pos=pos, node_size=600, node_color='w')
nx.draw_networkx_edges(g, pos=pos)
nx.draw_networkx_labels(g, pos=pos, font_size=20)
print([i for i, l in enumerate(g.adjacency_list()) if len(l)%2])
>>>
[0, 2, 3, 6]

점 0, 2, 3, 6의 차수가 홀수이므로, 이들 사이를 묶으면 좋은 것을 알 수 있습니다.

공식화하고 풀어 보겠습니다.

python3

m = LpProblem()
xs, ys = [], []
for i, j in g.edges():
    g.edge[i][j]['x'] = x = LpVariable('x%d_%d'%(i,j), cat=LpBinary)
    xs.append(x)
m += lpSum(xs)
for i, ad in enumerate(g.adjacency_list()):
    y = LpVariable(
'y%d'%i, cat=LpInteger)
    m += lpSum(g.edge[i][j]['x'] for j in ad) + len(ad) == 2 * y
    ys.append(y)
m.solve()
print([g.edges()[i] for i, x in enumerate(xs) if value(x)])
>>>
[(0, 2), (1, 3), (1, 6)]

가장 짧고 점 0, 2, 3, 6이 연결되어 있음을 알 수 있습니다.

이상