Differences

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

--- 전산물리학:열풀림_시늉 [2026/01/09 14:59] – admin
+++ 전산물리학:열풀림_시늉 [2026/01/09 15:18] (current) – admin
@@ Line 27: / Line 27: @@
 {{:전산물리학:maxcut3.png?400|}}
-그림처럼 $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이 된다. 이 값들은 모두 옳다.
+그림처럼 $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>
 ======참고문헌======