휴리스틱 알고리즘 차이 - hyuliseutig algolijeum chai

* 이 글은 "알고리즘 문제 해결 전략(종만북)" 中 11장 조합 탐색에 나온 내용을 바탕으로 작성하였습니다.

우리가 문제 해결 시 흔히 사용하는 동적 계획법(DP) 또는 분할 정복과 같은 완전 탐색에 기초한 디자인 패러다임은

사실 실생활에서 쓰기엔 매우 한정적이다. 

예를 들어, 인공지능 체스 프로그램을 알고리즘으로 짠다고 할 때 우리가 가장 먼저 떠올릴 수 있는 것은

브루트 포스(brute force) 방식이다. 즉, 가능한 모든 말의 움직임을 다 해보는 것이다.

하지만 이 방식은 어림도 없는게 움직일 수 있는 말과 이동 가능한 칸이 너무 많기 때문에 만약 이 방식으로 프로그램을 개발했다고 하면, 죽을 때까지 게임이 끝나지 않을 것이다. (경우의 수가 10^120 가지라고 합니다.)

그렇다고 해서 분할 정복 기법을 사용하자니 적절한 분할 방법이 생각나질 않고

동적 계획법을 사용하자니 메모리가 턱없이 모자르다.

결국 우리는 모든 경우의 수를 확인하지 않고도 답을 찾아낼 수 있는 방식을 사용해야 한다.

(주의 - 이분 탐색은 당연히 모두 확인하지 않아도 되는 것이지만 휴리스틱은 모두 확인해야 정확하게 찾을 수 있는데 안 하는 것입니다!)

* 위에서 극단적인 예시로 체스 프로그램을 예로 들었지만 실제 문제 풀이에서는 체스처럼 엄청 큰 입력이 들어오진 않고 동적 계획법으로 최적화가 되지 않을 정도의 입력이 들어오는 것으로 알고 있습니다!

휴리스틱 알고리즘이란?

* 휴리스틱(heuristics)이란 불충분한 시간이나 정보로 인하여 합리적인 판단을 할 수 없거나, 체계적이면서 합리적인 판단이 굳이 필요하지 않은 상황에서 사람들이 빠르게 사용할 수 있게 보다 용이하게 구성된 간편 추론의 방법이다.

(출처 : 위키백과 - 휴리스틱 이론)

휴리스틱 알고리즘은 기본적으로 모두 최적해가 될 가능성이 없는 답들을 탐색하는 것을 방지하여 만들어 봐야 할 답의 수를 줄이는 것을 목표로 한다.

하지만 어떠한 방법으로 경우의 수를 최적화할지는 매우 어렵고 실제로 고수분들도 문제 풀이에 대해 확신하지 못하기 때문에 가장 나중에 풀거나, 부분 점수를 노리는 경우가 많다고 한다.

휴리스틱 관련 이론

• 가지치기(pruning) 기법
• Simulated Annealing (담금질 기법)
• Genetic Algorithms (유전 알고리즘)

휴리스틱이라고 할 수 있는 기법들은 보통 이 정도인 것 같다. 

여기서 담금질과 유전은 머신러닝에서 자주 등장하는 걸로 알고 있는데

휴리스틱 관련 문제에 대한 해답을 찾던 중 볼츠만 상수와 온도 감률을 정해 simulated annealing로 푸시는 구사과님의 풀이를 보고는 역시 여기는 내 길이 아니구나 싶었다... (https://koosaga.com/3)

하지만 좌절하지 말고 이번 scpc에서 휴리스틱이 나오면 10점이라도 얻어가기 위해 가지치기만 살펴보자!

가지치기(pruning) 기법

가지치기 기법은 탐색 과정에서 최적해로 연결될 가능성이 없는 부분들을 잘라낸다.

예를 들어 길이가 10인 경로를 이미 찾았는데, 이후 다른 경우의 수를 구하는 과정에서 도착점에 도착하기도 전에

길이가 10이 넘어가면 마저 탐색하지 않고 종료해버리는 방법이 될 수도 있고

중간까지 와서 목적지까지 경로를 어림짐작했는데 지금까지 구한 최단 거리보다 먼 경우 종료해버릴 수도 있다.

이 방법을 사용하면 존재하는 답 중 일부는 아예 만들지 않기 때문에 프로그램의 동작 속도가 빨라지게 된다.

효율성을 극대화하기 위해선 가장 좋은 답의 상한을 빨리 찾아내서 얼토당토않는 경우를 탐색 초기에 종료해버려야 한다.

외판원 순회(TSP)에서의 가지치기

종만북에서는 외판원 순회 문제를 휴리스틱을 이용해 도시의 수가 20개일 때 3초 만에 해결할 수 있게 만들어 준다.

이 과정을 모두 설명할 수는 없고, 그중 단순한 가지치기 기법에 대해 살펴보자.

외판원 순회에서 가지치기는 '어림짐작' 기법을 이용한다.

즉, 한 상태가 주어질 때 아직 남은 도시들을 방문하기 위한 경로가 얼마나 길지를 적당히 '어림짐작' 하는 것이다.

이 결괏값은 항상 정확할 필요는 없고, '적당히 그럴 듯' 해 보여야 한다.

예를 들어 6개의 도시가 있을 때 어떤 한 도시에서 출발하여 모든 도시를 거쳐 다시 출발지로 돌아오는 최단 경로를 계산하는 TSP 문제가 주어졌고 우린 이미 1-2-5-6-4-3-1로 이동하는 거리 11인 답을 발견한 상태라고 해보자.

하지만 아직 답이 확정되지 않았기 때문에 우리는 다른 경로도 조사해봐야 한다.

우리가 이용해볼 방법은 아직 방문하지 않은 도시들에 대해 인접한 간선 중 가장 짧은 간선의 길이를 더하는 것이다.

아직 방문하지 않은 도시를 방문하려면 인접한 간선 중 하나를 타고 가야 하므로, 이들 중 가장 짧은 간선의 길이들을

모두 더하면 실제 최단 경로 이하의 값이 될 수밖에 없기 때문이다.

만약 5-3 또는 3-5로 이동했을 때 아직 방문하지 않은 도시들에 대해 인접한 간선 중 가장 짧은 간선의 길이들을 더 해보면 총 5의 거리가 산출된다.

(노드 1 = 1, 노드 2 = 1, 노드 4 = 1, 노드 6 = 2 -> 총 5)

하지만 이미 우린 10만큼을 이동했고, 거기에 5를 더하면 지금까지 구한 최단 거리인 11보다 크게 된다.

즉, 5-3 또는 3-5를 거치는 답은 절대 나오지 않는다는 것이니 가지치기가 가능하게 된다.

실제로 종만북에서는 MST 등 다양한 알고리즘을 휴리스틱 기법으로 해석해 TSP 문제 해결 시간을 줄여나가니 궁금하면

종만북을 통해 보는 것을 추천한다.

관련 문제

• 백준 2582 동전 뒤집기 - https://www.acmicpc.net/problem/2582
• 2018 scpc 1차 예선 4번 선형배치
• 2019 scpc 1차 예선 4번 파이프
• 2019 scpc 2차 예선 4번 폭격

scpc 문제는 코드그라운드(https://www.codeground.org/) 에서 확인 가능합니다.

결론

휴리스틱 알고리즘은 구글링해도 자료가 거의 없을 정도로 글로 설명하기 어려운 알고리즘인 것 같다.

명확한 답이나 해결 방법이 존재하는 것도 아니고, 관련 문제가 많지도 않다.

하지만 휴리스틱 문제는 보통 "이 중 몇 개의 테스트 케이스를 통과하면"이나 "정답 범위 안으로 출력 시" 등 

항상 최적해를 구할 수 없다는 것에 대한 힌트가 문제에 주어지거나 (백준에서)

완전 탐색이나 dp로 풀지 못하는 입력 조건이 있고, 어찌 저찌~ 잘 배치해라 ~ 라는 문제가 주로 나온다.

나와 비슷한 수준의 분들이 이런 문제를 보셨다면

최대한 가지치기를 해보던지 아니면 입력 범위보다 모자라게 dp를 사용하여 부분 점수라도 얻어가는 편이 좋아 보인다.