담금질 기법

2024.06.27 23:07

담금질 기법은 기본적으로 문제 공간에서 무작위 방향 중 에너지를 최소화하는 경향으로 상태를 확률적으로 바꾸며 해를 탐색한다. 마치 금속을 담금질하는 것과 비슷한 원리라고 해서 Simulated Annealing(모의 담금질) 이라는 이름이 붙었다.

이를 구현하는 방식은 다양하겠지만, 시뮬레이티드 어닐링은 다음과 같이 행동한다.

현재 상태와 인접한 상태를 하나 구한다.
그 상태로 변할 때 얼마만큼 이득인지/손해인지를 판단한다.
얻을 이득과 손해의 정도에 따라 확률적으로 그 상태로 이동한다.

여기서 인접한 상태란, 현재의 상태를 국소적으로 바꾸어서 만들 수 있는 상태이다. 담금질 알고리즘은 이 과정을 반복함을 통해서 최적해를 향해 나아가고, 와중에 더 나빠지는 해에 대해서도 가끔씩은 탐색을 해보면서 지역 최적점을 피해가려 노력한다.

대략적인 과정은 아래와 같이 이뤄진다.

while ( k > 임계 온도 ){
    E1 = 현재 상태의 에너지
    E2 = 랜덤하게 생성한 새로운 상태의 에너지
    p = exp((E1-E2)/(k*T));
    if (p > rand()) {
        현재 상태를 새로운 상태로 바꿈
    }
    k *= 온도 감률 (보통 0.95 ~ 0.9999 정도)
}

동전 뒤집기 2

담금질 기법을 사용하는 대표적인 백준 문제 중 하나로 동전 뒤집기 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;
}

참고

알고리즘N Queen 알고리즘Range GCD 알고리즘가장 가까운 두 점 알고리즘볼록 껍질과 회전하는 캘리퍼스 알고리즘오일러 경로 테크닉 알고리즘왜판원순회