담금질 기법은 기본적으로 문제 공간에서 무작위 방향 중 에너지를 최소화하는 경향으로 상태를 확률적으로 바꾸며 해를 탐색한다. 마치 금속을 담금질하는 것과 비슷한 원리라고 해서 Simulated Annealing(모의 담금질) 이라는 이름이 붙었다.
이를 구현하는 방식은 다양하겠지만, 시뮬레이티드 어닐링은 다음과 같이 행동한다.
- 현재 상태와 인접한 상태를 하나 구한다.
- 그 상태로 변할 때 얼마만큼 이득인지/손해인지를 판단한다.
- 얻을 이득과 손해의 정도에 따라 확률적으로 그 상태로 이동한다.
여기서 인접한 상태란, 현재의 상태를 국소적으로 바꾸어서 만들 수 있는 상태이다. 담금질 알고리즘은 이 과정을 반복함을 통해서 최적해를 향해 나아가고, 와중에 더 나빠지는 해에 대해서도 가끔씩은 탐색을 해보면서 지역 최적점을 피해가려 노력한다.
대략적인 과정은 아래와 같이 이뤄진다.
while ( k > 임계 온도 ){
E1 = 현재 상태의 에너지
E2 = 랜덤하게 생성한 새로운 상태의 에너지
p = exp((E1-E2)/(k*T));
if (p > rand()) {
현재 상태를 새로운 상태로 바꿈
}
k *= 온도 감률 (보통 0.95 ~ 0.9999 정도)
}담금질 기법을 사용하는 대표적인 백준 문제 중 하나로 동전 뒤집기 2가 있다.
mt19937는 랜덤 값을 생성하기 위해 사용한다.
#include <bits/stdc++.h>
using namespace std;
int n;
long long arr[33];
int main(){
mt19937 rd = mt19937((unsigned) chrono::steady_clock::now().time_since_epoch().count());
cin>>n;
uniform_int_distribution<int> ran(0, n-1);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
char c;
cin>>c;
arr[i] <<= 1;
if(c=='H') arr[i] |= 1;
}
}
int ans=n*n;
int a=0, b=0;
int prv=n*n;
double t=1.0, k=2.5;
for(int i=0;i<10101;i++){
b = a^(1<<ran(rd));
int now=0;
for(int j=0;j<n;j++){
int t=__builtin_popcount(arr[j]^b);
now+=min(t, n-t);
}
double nowP = exp((prv-now)/(k*t));
if(nowP > (double)ran(rd)/(n-1)){
a=b;
prv=now;
}
ans=min(ans, prv);
k*=0.9999;
}
cout << ans;
}참고