휴리스틱

휴리스틱은 문제를 받아 쓸 만한 답을 빨리 찾아 줍니다. 그 답이 가장 좋은 답이라고 장담하지는 않습니다. 후보가 너무 많아 전부 볼 수 없을 때 씁니다. 넓게는 경험에서 나온 판단 요령을 두루 가리킵니다. 이 문서는 알고리즘에서 쓰는 뜻을 다룹니다.

상세

휴리스틱(heuristic)은 「찾아낸다」는 뜻의 그리스어에서 온 말입니다. 우리말로는 발견법이나 어림법이라고 옮기기도 합니다. 알고리즘에서는 가장 좋은 답을 장담하지 않는 대신 빨리 끝나는 풀이 방법을 가리킵니다.

낯선 동네에서 지도 없이 목적지를 찾아가는 사람을 떠올려 보겠습니다. 목적지 근처의 높은 탑이 보이면 그쪽으로 걷습니다. 골목을 전부 따져 보지 않아도 대개 도착합니다. 그 길이 가장 짧은 길이었는지는 알 수 없습니다.

이 절은 먼저 휴리스틱이 왜 필요한지를 후보 수로 셉니다. 이어서 휴리스틱이 답을 처음부터 만드는 방식과 고쳐 나가는 방식을 코드와 그림으로 봅니다. 그다음 탐색 순서를 이끄는 휴리스틱 함수와 백엔드에서 만나는 휴리스틱을 봅니다. 끝으로 언제 쓰고 언제 안 쓰는지, 알고리즘 밖에서는 이 낱말을 어떻게 쓰는지 짚습니다.

다 볼 수 없는 문제

여러 답 가운데 가장 좋은 것을 고르는 문제를 최적화 문제라고 합니다. 가장 짧은 배송 경로를 찾거나 가장 적은 서버에 작업을 나눠 담는 문제가 그렇습니다. 답이 좋다는 것은 경로 길이나 서버 수처럼 문제가 정한 값이 더 작다는 뜻입니다. 그 값이 가장 작은 답을 최적해라고 부릅니다.

후보를 하나도 빼지 않고 전부 보면 최적해를 반드시 찾습니다. 이 방식이 완전 탐색입니다. 걸림돌은 후보의 수입니다.

외판원 순회가 대표적인 예입니다. 도시를 한 번씩 들러 처음 도시로 돌아오는 가장 짧은 경로를 찾는 문제입니다. 도시가 n 곳이면 첫 도시는 n 곳 중 하나를 고르고, 다음 도시는 남은 n−1 곳 중 하나를 고릅니다. 이렇게 끝까지 고르면 도는 순서는 n × (n−1) × … × 1 가지입니다.

이 곱을 n! 로 적고 팩토리얼이라고 읽습니다. 도시 수에 따라 후보가 얼마나 되는지 보면 아래와 같습니다.

도시가 10 곳에서 20 곳으로 두 배가 되는 동안 후보는 수천억 배로 불어났습니다. 1초에 10억 개를 확인해도 20 곳의 후보를 다 보려면 70년이 넘게 걸립니다. 입력이 조금 커졌을 뿐인데 후보가 다 볼 수 없을 만큼 불어나는 현상을 조합 폭발이라고 부릅니다.

후보를 덜 보면서도 최적해를 장담하는 빠른 방법이 있으면 좋겠습니다. 그런데 외판원 순회 같은 문제는 그런 방법이 지금까지 하나도 알려지지 않았습니다. 이런 문제 무리를 NP-난해라고 부릅니다.

여기서 빠르다는 말은 다항 시간에 끝난다는 뜻입니다. 다항 시간은 입력 크기가 n 일 때 걸리는 시간이 n², n³ 처럼 n 의 거듭제곱으로 늘어나는 것을 말합니다. 완전 탐색의 n! 보다 훨씬 느리게 늘어납니다.

NP 는 Nondeterministic Polynomial time(비결정적 다항 시간)의 줄임말입니다. 문제의 어려움을 나누는 분류 이름의 하나입니다. 「비결정적」이 무슨 뜻인지는 이 문서에서 다루지 않습니다.

이런 문제 앞에서 고를 길은 둘입니다. 입력을 작게 묶어 완전 탐색으로 끝까지 보거나, 최적해라는 장담을 내려놓고 빨리 끝내는 것입니다. 휴리스틱은 뒤쪽 길입니다.

휴리스틱이 내려놓는 것

최적해를 내려놓는 방법은 휴리스틱 말고도 있습니다. 근사 알고리즘은 최적해를 장담하지 않지만 「최적해의 두 배를 넘지 않는다」처럼 얼마나 멀어질 수 있는지를 증명해 둡니다. 휴리스틱에는 그런 증명이 없습니다.

세 방법을 답의 질과 걸리는 시간으로 견주면 아래와 같습니다.

휴리스틱의 「대개 좋다」는 경험에서 나온 말입니다. 여러 입력에 돌려 보니 좋은 답이 나왔다는 뜻입니다. 모든 입력에서 그렇다는 증명은 아닙니다.

그래서 휴리스틱은 요령이 안 맞는 입력을 만나면 나쁜 답을 냅니다. 대신 대부분의 입력에서 근사 알고리즘보다 좋은 답을 내는 휴리스틱도 흔합니다. 증명이 없다는 것과 답이 나쁘다는 것은 다른 이야기입니다.

답을 처음부터 만드는 휴리스틱

빈손에서 출발해 답을 한 조각씩 쌓는 휴리스틱이 있습니다. 가장 흔한 요령은 매 단계에서 지금 가장 좋아 보이는 조각 하나를 고르는 것입니다. 앞날을 따지지 않고 눈앞의 이득만 보므로 그리디 알고리즘이라고 부릅니다.

외판원 순회에서는 최근접 이웃 알고리즘이 그렇습니다. 지금 도시에서 아직 안 들른 가장 가까운 도시로 가는 일을 끝까지 되풀이합니다. 도시마다 남은 도시를 한 번씩 훑으면 되므로 걸리는 일이 n² 에 비례합니다. 후보가 n! 인 완전 탐색과 견주면 아주 빨리 끝납니다.

같은 요령을 거스름돈에 써 보겠습니다. 동전 종류와 금액을 받아 동전 개수가 가장 적게 거슬러 주는 문제입니다. 그리디 요령은 큰 동전부터 넣을 수 있는 만큼 넣습니다.

아래 파이썬 함수가 그 요령입니다. 동전을 큰 것부터 보면서 남은 금액이 그 동전보다 크거나 같으면 계속 넣습니다.

def change(coins, amount):
    picked = []
    for c in sorted(coins, reverse=True):
        while amount >= c:
            amount -= c
            picked.append(c)
    return picked

change([10, 5, 1], 17)  # [10, 5, 1, 1]
change([4, 3, 1], 6)    # [4, 1, 1]

첫 호출은 17 을 동전 네 개로 거슬러 줍니다. 이 동전 종류로는 이보다 적게 거슬러 줄 수 없습니다. 요령이 최적해를 낸 경우입니다.

둘째 호출은 6 을 동전 세 개로 거슬러 줍니다. 3 짜리 두 개면 동전 두 개로 끝나는데 이것을 놓쳤습니다. 맨 처음 4 를 넣는 순간 3 두 개라는 길이 막혔기 때문입니다.

같은 요령이 동전 종류에 따라 최적해를 내기도 하고 놓치기도 합니다. 10원·50원·100원·500원 동전으로는 이 요령이 언제나 가장 적은 개수를 냅니다. 휴리스틱을 쓸 때는 요령이 맞는 입력인지를 따로 따져야 합니다.

답을 고쳐 나가는 휴리스틱

이미 있는 답을 조금씩 고쳐 더 좋게 만드는 휴리스틱도 있습니다. 처음 답은 그리디 요령으로 만들어도 되고 아무렇게나 골라도 됩니다. 이 방식을 지역 탐색(local search)이라고 부릅니다.

지역 탐색은 지금 답을 조금만 바꾼 답들을 만들어 봅니다. 이렇게 한 번의 작은 변경으로 닿는 답을 이웃 답이라고 합니다. 이웃 답이 지금 답보다 좋으면 그쪽으로 옮겨 갑니다.

외판원 순회의 경로는 두 도시를 잇는 구간이 줄줄이 이어진 모양입니다. 이 구간 하나를 간선이라고 합니다.

2-opt는 경로에서 간선 두 개를 끊고 끊긴 끝을 엇바꿔 다시 잇는 변경입니다. 경로가 A → B → … → C → D 로 돈다면 간선 A-B 와 C-D 를 끊고 A-C 와 B-D 로 잇습니다. 그러면 B 와 C 사이 구간을 거꾸로 도는 경로가 됩니다. 최근접 이웃이 만든 경로를 다듬을 때 흔히 씁니다.

지역 탐색이 한 번 도는 흐름은 아래와 같습니다. 더 좋은 이웃 답이 하나도 없으면 멈춥니다.

flowchart TD
    A["처음 답을 하나 만든다"] --> B["이웃 답을 하나 만든다"]
    B --> C{"이웃 답이 더 좋나"}
    C -->|예| D["이웃 답으로 옮겨 간다"]
    D --> B
    C -->|아니오| E{"아직 안 본 이웃 답이 있나"}
    E -->|예| B
    E -->|아니오| F["멈추고 지금 답을 돌려준다"]

지역 최적해

지역 탐색이 멈춘 답은 둘레의 어느 이웃 답보다도 좋습니다. 그래도 최적해라는 보장은 없습니다. 이웃 답보다만 좋고 전체에서 가장 좋지는 않은 답이 지역 최적해입니다.

안개 낀 산에서 오르막으로만 걷는 등산객을 떠올리면 됩니다. 더 오를 데가 없으면 멈춥니다. 그곳이 산에서 가장 높은 봉우리인지 옆의 작은 봉우리인지는 안개 때문에 모릅니다. 그래서 더 좋은 쪽으로만 옮기는 지역 탐색을 언덕 오르기(hill climbing)라고도 부릅니다.

작은 봉우리에서 빠져나오게 해 주는 틀도 여럿 있습니다. 어느 한 문제에 묶이지 않고 여러 문제에 두루 씌울 수 있게 다듬은 휴리스틱의 틀을 메타휴리스틱이라고 부릅니다. 아래 셋이 대표적인 메타휴리스틱입니다.

셋 다 지역 최적해에 덜 갇히게 해 줍니다. 그래도 최적해를 장담하지는 않습니다. 셋 다 휴리스틱이기 때문입니다.

탐색 순서를 이끄는 휴리스틱 함수

휴리스틱이 답을 직접 만들지 않고 어디부터 볼지만 정하는 경우도 있습니다. 지도에서 가장 짧은 길을 찾는 문제로 보겠습니다.

다익스트라 알고리즘은 출발점에서 여기까지 온 거리가 짧은 곳부터 사방으로 넓혀 가며 길을 찾습니다. 도착점이 어느 쪽에 있는지는 따지지 않습니다. 그래서 도착점 반대쪽 길도 꼼꼼히 봅니다.

A* 알고리즘은 볼 곳마다 두 값을 더합니다. 하나는 출발점에서 여기까지 온 거리입니다. 다른 하나는 여기서 도착점까지 남은 거리를 어림한 값입니다. 이 합이 작은 곳부터 보므로 도착점 쪽으로 난 길을 먼저 보게 됩니다.

남은 거리의 어림값을 내는 함수가 휴리스틱 함수입니다. 지도에서는 두 지점 사이의 직선 거리를 흔히 씁니다.

어림값이 남은 거리를 실제보다 크게 잡지 않으면 A* 는 여전히 가장 짧은 길을 찾습니다. 직선 거리는 어떤 길보다도 짧거나 같으므로 이 조건을 지킵니다. 이런 휴리스틱 함수를 허용 가능 휴리스틱(admissible heuristic)이라고 부릅니다.

이 경우 휴리스틱은 최적해를 내려놓지 않습니다. 볼 곳의 순서만 바꿔 덜 보고 끝나게 합니다. 휴리스틱이라는 이름이 붙었다고 늘 답의 질을 잃는 것은 아닙니다.

백엔드에서 만나는 휴리스틱

백엔드 개발자가 매일 쓰는 도구 안에도 휴리스틱이 들어 있습니다.

첫째는 데이터베이스의 쿼리 옵티마이저입니다. 쿼리 옵티마이저는 SQL(Structured Query Language, 구조화 질의 언어) 문을 어떤 순서와 방법으로 실행할지 고르는 부분입니다. 테이블 여러 개를 행끼리 이어 붙이는 일을 조인이라고 합니다. 조인할 테이블이 여럿이면 어느 테이블부터 이을지 순서를 골라야 합니다.

테이블이 n 개면 잇는 순서의 후보도 팩토리얼로 불어납니다. 옵티마이저는 각 순서의 비용을 어림해 견줍니다. 테이블이 많으면 후보를 다 견줄 수 없으니 어느 순서를 견줄지 고르는 규칙을 둡니다. 이 규칙이 휴리스틱입니다.

PostgreSQL 은 조인할 테이블이 정해 둔 개수를 넘으면 순서를 전부 견주지 않습니다. 앞에서 본 유전 알고리즘으로 순서를 일부만 골라 견줍니다.

둘째는 캐시의 축출입니다. 축출은 캐시가 가득 찼을 때 항목 하나를 골라 내보내는 일입니다. 가장 좋은 선택은 앞으로 가장 늦게 다시 쓸 항목을 내보내는 것입니다. 하지만 캐시는 앞으로 무엇을 쓸지 모릅니다.

LRU(Least Recently Used, 가장 오래전에 쓴 것)는 「오래 안 쓴 항목은 앞으로도 한동안 안 쓴다」는 요령으로 고릅니다. 대개 잘 맞습니다. 큰 테이블을 처음부터 끝까지 한 번 훑는 작업처럼 요령이 안 맞는 경우에는 자주 쓰던 항목까지 밀려납니다.

휴리스틱을 쓰는 경우와 안 쓰는 경우

휴리스틱이 맞는 경우는 셋이 겹칠 때입니다. 입력이 커서 완전 탐색이 안 끝납니다. 최적해를 빨리 구하는 방법이 알려지지 않았습니다. 답이 조금 나빠도 손해가 작습니다.

반대로 입력이 작아 완전 탐색이 시간 안에 끝나면 휴리스틱을 쓸 까닭이 없습니다. 정렬이나 최단 경로처럼 빠르고 정확한 알고리즘이 이미 있는 문제도 그렇습니다. 최적해가 아니면 안 되는 문제라면 시간이 더 들어도 분기 한정 같은 정확한 방법으로 갑니다.

휴리스틱을 고른 뒤에는 답이 얼마나 좋은지 재 봐야 합니다. 작은 입력에서는 완전 탐색의 답과 견줍니다. 큰 입력에서는 「최적해가 이 값보다 좋을 수는 없다」는 값과 견줍니다. 이 값을 하한이라고 부릅니다. 휴리스틱의 답이 하한에 가까우면 최적해에도 가깝습니다.

알고리즘 밖의 휴리스틱

다른 분야에서도 같은 낱말을 씁니다. 가리키는 일은 달라도 「정답을 장담하지 않고 대개 통하는 규칙으로 빨리 정한다」는 뜻은 같습니다.

아래 표의 HTTP 는 HyperText Transfer Protocol(하이퍼텍스트 전송 프로토콜)의 줄임말입니다. 웹에서 요청과 응답을 주고받는 규칙입니다.

HTTP 캐시가 유효 기간을 어림하는 방법은 휴리스틱 신선도가 따로 다룹니다. 응답이 마지막으로 바뀐 때가 오래전일수록 앞으로도 한동안 안 바뀔 것이라고 보는 식입니다.

관련 항목

휴리스틱과 나란히 쓰는 설계 기법

완전 탐색 · 그리디 알고리즘 · 근사 알고리즘 · 분기 한정 · 동적 계획법 · 재귀 백트래킹 · 분할 정복

휴리스틱이 답을 만들고 고치는 방법

최근접 이웃 · 지역 탐색 · 언덕 오르기 · 무작위 재시작 · 2-opt · 3-opt · 린-커니핸 휴리스틱

휴리스틱을 여러 문제에 씌우는 틀

메타휴리스틱 · 담금질 기법 · 유전 알고리즘 · 타부 탐색 · 개미 군집 최적화

휴리스틱 함수로 탐색 순서를 정하는 알고리즘

A* 알고리즘 · 최상 우선 탐색 · 허용 가능 휴리스틱 · 일관된 휴리스틱 · 다익스트라 알고리즘

휴리스틱으로 푸는 대표 문제

외판원 순회 · 배낭 문제 · 빈 패킹 문제 · 거스름돈 문제 · 작업 스케줄링 · 그래프 색칠

휴리스틱이 필요해지는 까닭을 재는 도구

조합 폭발 · NP-난해 · 다항 시간 · 지수 시간 · 복잡도 클래스 · 시간 복잡도 · 팩토리얼

휴리스틱이 내는 답을 가리키는 이름

최적해 · 지역 최적해 · 전역 최적해 · 실행 가능해 · 하한

휴리스틱을 안에 품은 백엔드 도구

쿼리 옵티마이저 · 조인 · 축출 · LRU · 휴리스틱 신선도 · HTTP 캐시

휴리스틱이 속하는 상위 분류

알고리즘 · 알고리즘 설계 기법 · 최적화 문제 · 조합 최적화 · 인공지능