휴리스틱 알고리즘 (Heuristic Algorithm)

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

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

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

그렇다고 해서 분할 정복 기법을 사용하자니 적절한 분할 방법이 생각나질 않고 동적 계획법을 사용하자니 메모리가 턱없이 모자르다. 결국 우리는 모든 경우의 수를 확인하지 않고도 답을 찾아낼 수 있는 방식을 사용해야 한다.

휴리스틱 알고리즘이란?

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

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

 

휴리스틱 알고리즘은 기본적으로 모두 최적해가 될 가능성이 없는 답들을 탐색하는 것을 방지하여 만들어 봐야 할 답의 수를 줄이는 것을 목표로 하지만 어떠한 방법으로 경우의 수를 최적화할지는 매우 어렵고 실제로 고수분들도 문제 풀이에 대해 확신하지 못하기 때문에 가장 나중에 풀거나, 부분 점수를 노리는 경우가 많다고 한다.

관련 이론

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

가지치기(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 문제 해결 시간을 줄여나가니 궁금하면

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

 

 

https://kau-algorithm.tistory.com/7