This is an old revision of the document!
최대 절단(max-cut) 문제
모든 노드가 한쪽에 몰려 있는 상황에서 시작해보자. 즉 모든 노드 $k$에 대해 side[k]=+1이다. 이때 목적함수의 값은 obj=0에서 출발한다. 노드 사이의 실선은 +1의 가중치, 점선은 -1의 가중치를 의미한다.
노드 하나를 무작위로 골라서 반대편으로 보낸다. $k=3$가 선택되었다고 하자.
side[k]=-1이 되고, 목적함수의 값은 obj=1로 변할 것이다. 그런데 이것은 원래 $k=3$이 가지고 있었던 링크들의 가중치를 모두 더한 것에 불과하다. 따라서 애초에 chg[1]=1+1=2, chg[2]=1-1-1=-1, chg[3]=1+1-1=1, 그리고 chg[4]=-1+1=0을 미리 계산해두었더라면 그 중 하나를 옮겼을 때 obj가 얼마나 변할지 바로 알 수 있었다. 즉 obj += chg[k]이다.
위에서처럼 이미 $k=3$이 옮겨진 상황에서, 하나를 골라서 다른 쪽으로 보낸다면 obj가 얼마가 변할지도 미리 알 수 있을까? 다시 $k=3$이 선택된다면 답은 쉽다. 제자리로 돌아가는 것이므로 chg[3]은 조금 전에 자신이 가지던 값에서 부호만을 바꾼 것이다. $k=1$이 선택된다면?
그림처럼 다시금 obj=1이므로 chg[1]=0일 것이다. 이는 다음처럼 이해할 수 있다. 노드 1을 옮기면 1과 3이 같은 쪽에 속하므로 그 사이의 연결은 obj에 세어지지 않고, 1과 2 사이의 연결이 obj에 셈해진다. 노드 1이 가지는 연결 중 하나는 +1의 기여를 하고 다른 하나는 -1의 기여를 하므로 chg[1]=0이다. 그런데 1과 2 사이의 연결은 처음에 chg[1]을 계산할 때 이미 한번 더해졌던 것이기 때문에, $k=3$을 옮길 때에 1과 3 사이 연결이 가지는 가중치가 반대의 역할을 하게 되리라는 것만 고려해주어도 된다. 즉 $k=3$을 옮겼을 때에 chg[1] += (-2)*1로 갱신해주었으면 된다. 마찬가지 논리로 $k=3$을 옮겼을 때 미리 chg[2] += (-2)*(-1)와 chg[4] += (-2)*1로 갱신해주도록 하자. 정리해보면, $k$를 옮기면서 $k$에 연결된 노드 $v$들을 찾고, $v$와 $k$ 사이 연결의 가중치 $w$를 찾아서 chg[v] += (-2)*w를 해주면 될 것처럼 보인다.
이제 $k=1$을 옮겼으므로 방금 우리가 추측한 것처럼 $k=1$이 넘어간 그 순간에 chg의 값들을 갱신해보도록 하자. chg[1]이 -chg[1]으로 주어져 0임은 자명하다. $k=1$은 2와 3에 연결되어 있고 둘 모두 +1의 가중치로 연결되어 있다. 그러면 chg[2] += (-2)*1로서 chg[2]=-1이 된다. 이 값은 옳다. chg[3]도 chg[3] += (-2)*1로서 -3이 될까? 그렇지 않다. 옳은 값은 chg[3] += 2*1로서 chg[3]이 +1이 되는 것이다. 왜냐하면 노드 1과 3이 같은 편에 있었으므로 1이 다시 왼쪽으로 넘어갈 때 둘 사이의 가중치는 +의 역할을 하는 것이다. 따라서 옳은 규칙은 다음과 같다.
- 반대쪽으로 옮길 노드 $k$를 고른다.
- $k$에 연결된 노드 $v$들을 찾는다.
- $v$와 $k$가 원래 같은 쪽에 있다가 헤어지는 것이라면 둘 사이의 연결의 가중치 $w$를 찾아서 chg[v] += (-2)*w로 갱신한다.
- 그렇지 않고 다른 쪽에 있었다면 chg[v] += 2*w로 갱신한다.
$k=3$을 골라서 다시 왼쪽으로 보냈다고 하고 위의 규칙대로 chg의 값들을 갱신해보자. chg[3]은 부호만 뒤집으면 되므로 chg[3]=-1이다. chg[1]+=(-2)*1로서 chg[1]=-2가 된다. chg[2]+=2*(-1)로서 chg[2]=-3이 된다. chg[4]+=2*1로서 chg[4]=0이 된다. 이 값들은 모두 옳다.
참고문헌
- Aarts and Korst, Simulated Annealing and Boltzmann Machines (Wiley, Chichester, 1989).