문제 파악하기

문제에서 요구하는 것은 다음과 같이 요약할 수 있다.

• 점수는 사람마다 매기는 것이 아니라 전체로 따진다.
• i번 사람은 A[i] 또는 B[i]에서 최대 한 개를 선택할 수 있고, 선택한 것을 점수로 얻는다.
• i번 사람과 j번 사람이 하나씩 골랐고 다른 것을 선택했다면, H[i, j]만큼 점수를 감점 당한다.
• 전체 점수가 최대가 되도록 골라주자.

문제 조건 표현하기

수식으로 적어보자. 우선 수식으로 표현하기 위해 다음과 같이 정의하자.

$$\begin{align} \mathbf{U} &:= \left\{\texttt{1번부터 N번까지의 사람들 번호}\right\} \\ \mathbb{A} &:= \left\{i | i\texttt{번째 사람이 }A[i]\texttt{를 선택했다.} \right\} \\ \mathbb{B} &:= \left\{i | i\texttt{번째 사람이 }B[i]\texttt{를 선택했다.} \right\} \end{align}$$

그리고 다음을 만족해야 한다.

$$(\mathbb{A} \cup \mathbb{B}) \subset \mathbf{U} \\ (\mathbb{A} \cap \mathbb{B}) = \phi$$

전체 점수는 다음과 같이 표현할 수 있고, 등식이 성립한다.

$$\begin{align} S = & \sum_{i \in \mathcal{A}}{A[i]} + \sum_{i \in \mathcal{B}}{B[i]} - \sum_{i \in \mathbb{A}} \sum_{j \in \mathbb{B}} H[i, j] \\ = & \sum_{i \in \mathbf{U}}{A[i] + B[i]} - \sum_{i \in \mathcal{A}^{\textrm{C}}}{A[i]} - \sum_{i \in \mathcal{B}^{\textrm{C}}}{B[i]} - \sum_{i \in \mathcal{A}} \sum_{j \in \mathcal{B}} H[i, j] \\ = & \underbrace{\sum_{i \in \mathbf{U}}{\left(A[i] + B[i]\right)}}_{\textrm{상수(constant)}} - \underbrace{\left\{\sum_{i \in \mathcal{A}^{\textrm{C}}}{A[i]} + \sum_{i \in \mathcal{B}^{\textrm{C}}}{B[i]} + \sum_{i \in \mathcal{A}} \sum_{j \in \mathcal{B}} H[i, j]\right\}}_{\ast} \end{align}$$

최적화 문제에서 선택에 따라 변하는 부분에서 뺄셈을 없애고 \ast$\ast$처럼 덧셈으로만 이뤄지도록 만들어내는 기술은 자주 쓰이는 기술이므로 눈여겨 보자.

문제 풀이

우리가 하고자 하는 것은 S$S$를 최대화 하는 것이다. 그렇다면 위 식의 \ast$\ast$ 부분을 최소화 하는 문제로 여길 수 있다. \ast$\ast$ 부분의 식을 해석해보자. 선택되지 않은 것들의 가치가 더해지고, 선택된 것 사이에서는 H[i, j]가 더해진다.

network flow 관련 모델링을 자주 해본 사람이면 여기서 벌써 방법을 생각해냈을 것이다. bipartite graph에 sink와 source가 양쪽에 붙어 있는 모양의 그래프에서 min cut을 하면 된다. 이분 그래프의 양쪽에 N개의 노드를 놓자. source 쪽에 있는 N개의 노드는 A[i]를 선택했는지의 여부를 담당하고, sink 쪽에 있는 노드는 B[i]를 선택했는지의 여부를 담당한다고 해보자. \ast$\ast$에서 A[i]가 선택이 되지 않으면 A[i] 값이 더해지므로 선택되지 않으면 끊어진다고 하자. 마찬가지로 B[i]가 선택이 되지 않으면 해당 노드가 끊어진다고 하자. 끊어지지 않은 것 사이에 있는 간선은 반드시 끊어져야 graph의 cut이 될 수 있으므로, 끊어지지 않은(=선택된) 것 사이의 간선은 모두 끊어진다. 따라서 간선 가중치를 H[i, j]로 하면 된다. 그리고 같은 i에 대해 A[i]와 B[i]가 모두 끊어지지 않으면(= 둘 다 선택하면) 안되므로, 둘 중 하나는 끊어지도록 두 정점 사이에 절대로 끊어지지 않는 간선을 추가한다. graph의 cut이 되기 위해서는 둘 중 한 점은 끊어질 것이다.

[그림]

일반적인 수식 모델링 방법 알아보기 (선택 사항)

만약 위와 같은 모델이 직관적으로 떠오르지 않는다면 다음과 같은 수식 전개를 통해 minimum cut임을 유도할 수도 있다.

$$\forall i \in \mathbf{U} \; \left(F_i, G_i \in \left\{ 0, 1 \right\} \right)$$

인 변수 F$F$와 G$G$를 추가하자. F_i = 1$F_i = 1$ \textrm{iff}$\textrm{iff}$ i \in \mathcal{A}$i \in \mathcal{A}$, G_i = 0$G_i = 0$ \textrm{iff}$\textrm{iff}$ i \in \mathcal{B}$i \in \mathcal{B}$라고 하면 \ast$\ast$를 다음과 같이 쓸 수 있다. (\sum$\sum$에서 i$i$와 j$j$의 소속 집합이 사라졌음에 주목하라)

$$\sum_i \left((1-F_i) \times A[i] \right) + \sum_i \left(G_i \times B[i] \right) + \sum_i\sum_j{(F_i-G_j) \times H[i,j]}$$

(\mathbb{A} \cap \mathbb{B}) = \phi$(\mathbb{A} \cap \mathbb{B}) = \phi$ 조건에 의해 \mathcal{A}$\mathcal{A}$와 \mathcal{B}$\mathcal{B}$에 i가 모두 속할 순 없으므로, 다음도 성립해야 한다.

$$\forall i \in \mathbf{U} \; (F_i \le G_i)$$

이 조건을 암시적으로 성립하게 하려면 식을 다음과 같이 변형하면 된다. \mathscr{L}$\mathscr{L}$은 매우 큰 수이다.

$$\sum_i \left((1-F_i) \times A[i] \right) + \sum_i \left(G_i \times B[i] \right) + \sum_i\sum_j{(F_i-G_j) \times H[i,j]} \\+ \sum_i \left( \max \{F_i - G_i, 0\} \times \mathscr{L} \right) \ $$

min cut의 LP 버전의 형태를 알고 있으면 다음과 같은 치환을 쉽게 떠올릴 수 있다. 최적화 대상인 위 식은 굳이 다시 적지 않겠다.

$$\begin{align} d_{x y} &\ge 0 \\ d_{s i_0} &\ge 1 - F_i \\ d_{i_1 t} &\ge G_i - 0 \\ d_{i_0 j_1} &\ge F_i - G_i (\textrm{if } i \neq j)\\ d_{i_0 i_1} &\ge \max\{F_{i} - G_{i}, 0\} \ge F_i - G_i\\ p_{i_0} &= F_i \\ p_{i_1} &= G_i \\ \end{align}$$

이 치환은 mincut의 Linear Programming 부등식들이다. 그렇다면 최적화 결과에서 얻어지는 d$d$의 값은 정수값으로 제약할 수 있고, F$F$와 G$G$ 값이 0 또는 1이라는 가정을 만족시킬 수 있다. 결국 min cut 문제로 변환하는 것에 성공한 것이다.
이러한 치환을 떠올리려면 0과 1, 그리고 변수들의 차를 잘 살펴볼 필요가 있다. 그 차이값에 어떤 음이 아닌 수를 곱한다면 그것은 최적화 대상 식과 같은 형태가 된다.

얻어낸 모형 증명하기

직관적으로 올바르다고 여겨지는 모델링을 얻었다고 안심하고 쓸 수는 없다. 실제로 최적해를 얻음을 증명해야 한다.
증명)
작업중