https://gall.dcinside.com/mgallery/board/view/?id=ps&no=15740


문제 : https://www.acmicpc.net/problem/18789

샘플 코드 : https://gist.github.com/Weisstrieb/37224700948d493c2fc7e6d71ba5f51a


골자는 시간복잡도가 너무 높아 풀기 어려운 문제의 최적해를 구하기 위해선 무엇을 해야하는가? 를 묻는 문제인뎅


저는 일단 먼저 랜덤으로 테이블을 만들고, 적절히 점수가 높아지는 쪽으로 변이시키는 휴리스틱, 랜덤으로 점수를 일부 낮추는 휴리스틱을 혼용하여 국소 최적해를 구한다는 접근이에요 (너무나도 유명한 simulated annealing)


이 simulated annealing은 휴리스틱 적용 전과 적용 후의 점수 차를 확률로 반영하여 점수를 개선시키는 방향은 100%로 채택하고, 점수를 낮추는 방향은 점수차에 지수적으로 반비례하는 확률에 따라 채택해요




.. 사실 여기까진 그냥 누구나 아는 형식적인 알고리즘이고, 최종 보스는 휴리스틱, 그리고 변이 로직을 어떻게 구성하는가, 그리고 얼마만큼의 컴퓨팅 파워와 인내심을 쏟을 수 있는가.. 겠죠?



* 개인적인 자잘한 팁들 *

1. simulated annealing에서 점수를 낮추는(안좋은) 방향으로 변이될 확률을 계산하는 실제 공식은 인데(k는 상수, t는 온도), 이 공식은 이 문제에 적용하기엔 점점 점수 스케일이 커질수록 두 점수의 차도 커져서 변이 확률이 엄청 작아진다는 문제가 있어요


그래서 개인적으로 전 이 문제를 풀 때 공식을 적용해서 적절히 정규화시켜줬는데, 각자의 방식대로 적절한 점수 차의 정규화가 필요한 거 같아요



2. simulated annealing은 기본적으로 '국소 최적해'를 찾는데 특화되어있어요. 즉 그게 요구치(위 문제에선 8천점)를 넘지 않을 가능성도 매우 다분하다는 거예요


그래서 변이 점수차가 그렇게 크지 않게끔 국소해로 수렴했는데 점수가 기대치보다 낮으면 다시 annealing을 돌려서 (온도를 초기값으로 재설정) 다시 돌리는 과정을 반복했어요



3. 그렇게 했음에도 한 구간에 계속 수렴하려는 성질을 떨치진 못해서 다른 국소해를 찾으려면 크게 점수를 떨궈야 할 필요가 있어요 (백트래킹 비슷하게)


그래서 위 공식에서 원래 k가 기존 공식에선 볼츠만 '상수'였던 걸, k(s)란 함수로 재구성했어요. 이 s는 변이 전의 점수가 얼마나 계속 일정 구간에서 벗어나지 못하고 수렴하는지에 대한 걸 알려주는 stationary란 변수에요


이건 (t는 민감도 수치이며, 1에 가깝게) 이란 누적 평균?을 계속 루프마다 적용시켜서 계속 루프때마다 계속 점수를 갱신하지 못하고 구간에 머무르는지 확인하고, 계속 머무르게 되면 s의 값을 점점 올려요


바로 지수부의 분모에 있는 란 함수는 s에 일정 수준으로 비례해서 증가하게 되고, 그러면 점수를 많이 낮추는 변이를 채택할 확률도 그만큼 증가하게끔 설정해놨어요

(단, 점수를 갱신하거나 구간에서 벗어나면 빠른 속도로 0으로 줄어들게끔도 설정, 이때 k(0)은 초기에 설정한 볼츠만 상수값)



그렇게 열심히 때려박아서 어찌어찌 근성 노가다로 풀린 고 같아요