Differences

This shows you the differences between two versions of the page.

--- 전산물리학:열풀림_시늉 [2026/01/09 14:52] – admin
+++ 전산물리학:열풀림_시늉 [2026/01/09 15:18] (current) – admin
@@ Line 16: / Line 16: @@
 {{:전산물리학:maxcut2.png?400|}}
-그림처럼 다시금 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를 해주면 될 것처럼 보인다.
+그림처럼 다시금 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=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로 갱신한다.
+  * 그렇지 않고 다른 쪽에 있다가 만나는 것이라면 chg[v] += 2*w로 갱신한다.
 {{:전산물리학:maxcut3.png?400|}}
-$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이 된다. 이 값들은 모두 옳다.
+그림처럼 $k=3$을 골라서 다시 왼쪽으로 보냈다고 하고 (obj=2) 위의 규칙대로 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이 된다. 이 값들은 모두 옳다.
+위 규칙을 코드로 구현하고 열풀림 시늉으로 풀어본 결과는 아래와 같다.
+<code:python>
+from numpy import zeros, array, ones
+from numpy.random import randint, uniform
+from math import exp
+n = G.number_of_nodes()
+m = G.number_of_edges()
+chg = zeros(n, int)
+for a, b, data in G.edges(data=True):
+  u = int(a)-1
+  v = int(b)-1
+  w = int(data.get('weight'))
+  chg[u] += w
+  chg[v] += w
+side = ones(n, int)
+obj = 0
+best = 0
+beta = 0.0
+betamax = 10
+dbeta = 10**(-5)
+blist = []
+while beta<betamax:
+  k = randint(n)
+  if chg[k]>=0 or uniform() < exp(beta*chg[k]):
+    obj += chg[k]
+    side[k] *= -1
+    chg[k] *= -1
+    for origin, destination, data in G.edges(str(k+1), data=True):
+      u = int(origin) - 1
+      v = int(destination) - 1
+      vw = int(data.get('weight'))
+      chg[v] += vw * (2 - 4 *(side[k] != side[v]))
+    if obj > best:
+      for i in range(n):
+        best = obj
+  beta += dbeta
+  blist.append(best)
+plt.plot(blist)
+plt.show()
+print(side)
+print(best)
+</code>
 ======참고문헌======