가끔, 어떤 문제를 정해의 방식대로 푸는 것보다 휴리스틱을 통해 푸는 것이 훨씬 직관적이고 간단한 경우가 있다. 그러한 문제들은 내가 적절히 포스팅을 해두었기 때문에 참조하면 좋을 것이다. 휴리스틱의 종류에는 여러가지가 있다고 할 수 있는데, 대표적으로 Simulated Annealing과 Diversified Late Acceptance Search가 있다. 전자는 대체로 SA라고 부르며, 일반적으로 휴리스틱중에선 널리 알려진 편에 속하는 것 같다. 그러나, 본 포스팅에서 소개할 기법인 DLAS는 일반적으로 SA보다도 더욱 강력한 효과를 발휘하는 것으로 알려져 있다.
DLAS의 정확한 이론과 작동원리, 증명에 대해서는 지식이 부족해서 설명할 수 없지만, DLAS가 어떠한 방식으로 작동하는지는 설명이 가능하다.
1. 우선 어떤 문제가 존재한다면, 그 때의 어떤 해의 상태를 생각하자. 또한, 각 상태에서 약간 변형을 랜덤하게 가하는 함수를 f라 하고, 어떤 상태가 우리가 원하는 것과 가까운지(만약 어떤 조건을 만족시키는 해를 찾는게 목적이라면 얼마나 그 목적에 부합하는지, 최적해를 구하는 것이라면 그 해의 답이 얼마인지)에 따라 더욱 큰 값을 가지도록 하는 함수 g(일반적으로 평가함수라고 부른다.)를 정의해야 한다.
또한, C라는 배열을 그러한 점수들의 배열이라고 정의하겠다.
2. 처음에는 아무런 상태를 하나 잡는다. 이 상태를 a라고 하자. 또한, 이 시행이 k번째 시행이라고 하자. 이제, b=f(a)라고 정의하자. x,y의 값을 각각 a,b의 f값으로 초기화하자. 이제, 다음과 같은 시행을 진행하고 다시 k+1번째 시행을 진행한다:
2-1. 만약 x==y이거나, y가 C 배열의 모든 값보다 더 크다면 x=y로 설정하고, a=b로 설정한다.
2-2. 만약 (x가 기존의 값보다 커졌으며, x가 C[k%5]보다 크다)이거나, (x가 C[k%5]보다 작다)를 만족할 경우, C[k%5]=5로 설정한다.
3. 이러한 과정을 충분히 많이 진행하면 우리가 원하는 값에 상당히 가깝거나, 혹은 원하는 것 자체를 얻을 수 있게 된다. 다만, 해가 잘못 수렴할 경우를 대비하여 모든 해를 전부 초기화한 상태에서 10번정도 돌려보는 것을 추천한다.
이러한 알고리즘이 작동하는 것을 나는 잘 설명할 수 없지만, 한가지 확실한 것은 이 알고리즘이 매우 잘 작동한다는 것이다. 예를 들면 19702 친구 문제나, 23575 squid game등이 있다. 이 둘은 전부 까다로운 아이디어를 내는 것이 풀이의 정해이지만, dlas를 사요하면 매우 간단하고 직관적으로 해결이 가능하다(다만 squid game의 경우에는 약간 애매한 부분이 존재하는 것이, 단순힌 랜덤으로도 시간초과가 나타나긴 하지만, 유의미한 시간 내에 해결이 됨을 확인했다). 구체적인 구현방법은 다음과 같다.
b=f(a);
y=g(b);
w=x;
if(t<y)
{
t=y;
d=b;
}
if(x==y||y>*min_element(o,o+5))
{
a=b;
x=y;
}
if(x<o[k%5]||(x>o[k%5]&&x>w))
{
o[k%5]=x;
}이는 단지 반복 부분만을 가져온 것으로, a,b,x,y는 동일한 변수명을 사용했으며, t와 d가 현재까지 나온 최댓값을 저장하는 역할을 하고 있다. C라는 배열의 역할을 o가 진행하고 있다.
814-2도 dlas를 통해 해결 가능한 좋은 문제중 하나이므로, 한번 시도해보는 것도 좋을 것이다.