백트래킹 알고리즘 (backtracking algorithm)
쉽게 풀면
백트래킹은 미로를 탐험하다 막다른 길을 만나면 갈림길로 되돌아가 다른 길을 시도하는 것과 비슷한 방식이다. 가능한 모든 경우를 하나씩 시도하되, 이미 조건을 만족할 수 없다고 판단되는 경로는 일찌감치 포기하고 되돌아감으로써 불필요한 탐색을 줄인다. N-퀸 문제, 스도쿠 풀이, 부분집합의 합 문제 등에 널리 쓰인다.
왜 중요한가
백트래킹은 제약 만족 문제(CSP), 조합 최적화, 자동 정리 증명, 컴파일러의 파싱 등 폭넓은 영역에서 등장하는 기본적인 완전 탐색 뼈대다. 많은 NP-난해 문제의 실용적 해법이 결국 백트래킹에 가지치기 규칙을 얼마나 잘 결합하느냐로 귀결되기 때문에, 새로운 가지치기 기법이나 탐색 순서 전략을 제안하는 논문에서 비교 기준(baseline)이나 설계의 출발점으로 자주 언급된다. 또한 SAT 솔버, 스케줄링, 회로 설계 등 실무 시스템의 내부 알고리즘을 설명할 때도 핵심 개념으로 다뤄진다.
어떤 절차인가
- 해를 조금씩 키워 가는 부분 후보를 만듭니다(예: 앞의 k개 행에만 퀸을 놓은 상태).
- 부분 후보가 이미 제약을 어겼으면 그 아래로는 더 가지 않고 버립니다(
reject, 가지치기). - 아니면 해가 완성되었는지 확인하고(
accept), 아니면 다음 선택지(first,next)를 하나씩 붙여 같은 일을 되풀이합니다. - 막히면 직전 갈림길로 돌아가 다른 선택지를 시도합니다. 이 순회는 탐색 트리를 뿌리부터 깊이 우선으로 내려가는 방식입니다.
“백트랙”이라는 말은 D. H. Lehmer가 1950년대에 만든 것으로 소개됩니다. 가지치기 판정이 뿌리에 가깝게 일어날수록 효과가 크고, 판정이 늘 거짓이면 사실상 완전탐색과 같아집니다.
언제 쓰고 무엇을 얻나
부분 후보를 만들 수 있고 빠르게 “이 후보는 틀렸다”고 판정할 수 있을 때 씁니다. 대표 예가 N-퀸 문제입니다. 8×8 판에서 해는 92개(회전과 대칭을 같은 것으로 보면 12개)입니다. 행마다 하나씩 퀸을 놓는 백트래킹을 직접 구현해 방문한 노드 수(재귀 호출 수)를 센 값입니다(구현에 따른 값).
| N | 방문 노드 수 | 해의 수 |
|---|---|---|
| 4 | 17 | 2 |
| 6 | 153 | 4 |
| 8 | 2,057 | 92 |
가지치기가 없다면 행마다 8칸 중 하나를 고르는 8⁸ = 16,777,216가지를 모두 늘어놓아야 합니다. 백트래킹은 충돌이 생기는 순간 그 아래를 버리므로 2,057개 노드만 방문했습니다. 다만 최악의 경우에는 여전히 많은 노드를 봐야 할 수 있으므로, 효율은 가지치기 규칙과 변수, 값의 선택 순서에 좌우됩니다.
논문에는 이렇게 적는다
- 후보를 어떻게 표현하고(부분 해의 정의), 어떤 가지치기 규칙을 쓰는지 적습니다.
- 변수와 값의 선택 순서(휴리스틱)를 밝힙니다. 순서에 따라 방문 노드 수가 크게 달라집니다.
- 첫 해에서 멈추는지, 모든 해를 찾는지, 시간이나 후보 수 제한이 있는지 적습니다.
- 실행 시간과 함께 방문한 노드 수를 보고하면 구현이나 컴퓨터가 달라도 비교하기 쉽습니다.
논문에서는 이렇게 쓰입니다
실제 논문에서
이 용어를 직접 쓴 국내 논문 문장을 아직 수집하지 못했습니다. 수집되는 대로 출처와 함께 싣겠습니다.
예시 문장
아래는 용어의 쓰임을 보여 주려고 만든 예시로, 실제 논문에서 가져온 문장이 아닙니다.
완전 탐색을 하되 불필요한 경로를 미리 배제하는 탐색 전략을 설명할 때 쓰인다.
제약 만족 문제(CSP) 분야에서 백트래킹의 효율을 높이기 위해 탐색 순서를 조정하는 접근을 설명할 때 쓰인다.
회로 설계나 배치 최적화처럼 조합적 설계 문제를 다루는 응용 분야에서 백트래킹을 활용하는 사례를 설명할 때 쓰인다.
조금 더 깊게 보면
백트래킹의 실제 성능은 대개 가지치기 규칙과 변수·값 선택 순서에 좌우되는데, 논문에서는 이를 위해 제약 전파(constraint propagation), 순방향 확인(forward checking), 충돌 유도 학습(conflict-driven learning)과 같은 보조 기법을 함께 언급하는 경우가 많다. 이러한 기법들은 유망하지 않은 분기를 더 빨리 판단하거나, 실패의 원인이 된 변수를 파악해 탐색 트리를 효율적으로 줄이는 역할을 한다. 관련 개념인 분기 한정법(branch and bound)은 백트래킹에 목적함수의 상한·하한 경계를 추가로 활용하는 변형으로 이해할 수 있으며, 두 기법이 함께 비교되거나 결합되어 제시되는 경우도 흔하다.
주의할 점
백트래킹은 최악의 경우 여전히 지수 시간이 걸릴 수 있으며, 가지치기(pruning)의 효율성에 따라 실제 성능이 크게 달라진다.
헷갈리기 쉬운 용어
| 용어 | 한 줄 설명 |
|---|---|
| 백트래킹 | 부분 해를 키우다가 틀린 경로를 버리고 되돌아오는 탐색 |
| 완전탐색 | 가능한 모든 경우를 하나씩 확인하는 방법 |
| 깊이 우선 탐색 | 한 경로를 끝까지 따라가다 되돌아오는 그래프 탐색, 백트래킹의 순회 방식 |
| 분기 한정법 | 분기에 목적함수의 상한, 하한 경계를 더해 가지를 버리는 방법 |
| 제약 만족 문제 | 변수, 값의 범위, 제약으로 정의되는 문제, 백트래킹이 자주 쓰이는 대상 |
참고 문헌
- Golomb, S. W., & Baumert, L. D. (1965). Backtrack programming. Journal of the ACM, 12(4), 516-524.
- Knuth, D. E. (1975). Estimating the efficiency of backtrack programs. Mathematics of Computation, 29(129), 122-136.
- Haralick, R. M., & Elliott, G. L. (1980). Increasing tree search efficiency for constraint satisfaction problems. Artificial Intelligence, 14(3), 263-313.
- Knuth, D. E. (2019). The art of computer programming, Volume 4, Fascicle 5. Addison-Wesley.
표의 기준값은 위 문헌에 근거한 관례이며, 분야·학술지마다 다른 기준을 쓸 수 있습니다.