백트래킹
백트래킹은 해를 구성하는 도중 조건에 맞지 않는 부분해를 조기에 폐기하는 깊이 우선 탐색 방법이다. 알고리즘의 상태 공간 탐색 분야에서 다루며, 문제를 어떤 하위 단계로 표현하고 어떤 계산을 생략하거나 공유할지를 결정하는 방법이다. 이 기법을 적용할 때에는 결과의 정확성뿐 아니라 종료...
| 분류 | 알고리즘 · 상태 공간 탐색 |
|---|---|
| 목적 | 해를 구성하는 도중 조건에 맞지 않는 부분해를 조기에 폐기하는 깊이 우선 탐색 방법 |
| 핵심 과정 | 변수나 선택지를 하나씩 확정해 부분해를 확장하고, 제약을 위반하거나 완성 가능성이 없으면 이전 단계로 되돌아간다 |
| 시간·연산 비용 | 최악에는 여전히 지수·팩토리얼 시간; 재귀 깊이의 스택 공간 |
| 적용 전제 | 부분해의 유효성 또는 완성 가능성을 조기에 판정하는 검사가 필요하다 |
| 관련 분야 | 알고리즘 설계, 계산 복잡도 |
| 참고 자료 | MIT 알고리즘 강의 |
백트래킹은 해를 구성하는 도중 조건에 맞지 않는 부분해를 조기에 폐기하는 깊이 우선 탐색 방법이다. 알고리즘의 상태 공간 탐색 분야에서 다루며, 문제를 어떤 하위 단계로 표현하고 어떤 계산을 생략하거나 공유할지를 결정하는 방법이다. 이 기법을 적용할 때에는 결과의 정확성뿐 아니라 종료 조건, 필요한 상태의 표현과 입력 조건을 함께 정의한다.[1]
핵심 처리 과정은 다음과 같다. 변수나 선택지를 하나씩 확정해 부분해를 확장하고, 제약을 위반하거나 완성 가능성이 없으면 이전 단계로 되돌아간다. N-퀸·스도쿠·순열 생성에 사용한다. 설계 시에는 각 단계에서 보존되어야 할 불변식이나 조건을 정의하고, 결과를 반환하기까지 어떤 상태가 수정되는지를 추적한다.
계산 자원은 문제의 크기와 구현 방식에 좌우된다. 최악에는 여전히 지수·팩토리얼 시간; 재귀 깊이의 스택 공간. 적용 조건은 부분해의 유효성 또는 완성 가능성을 조기에 판정하는 검사가 필요하다라는 점이다. 이 조건이 성립하는지를 먼저 확인해야 동일한 절차를 다른 입력에도 일관되게 사용할 수 있다.
완전 탐색의 후보 생성 순서를 개선한 방식이며, 최적화 문제에서는 비용 하한으로 가지치기하는 분기 한정법과 결합할 수 있다. 실제 구현에서는 상태 표현, 자료구조 선택, 재귀 호출 또는 반복 처리, 메모리 접근과 경계 입력을 함께 고려한다. 이론적 계산 모델과 구체적인 프로그램의 시간·공간 비용은 입력 분포와 실행 환경에 따라 달라질 수 있다.[2]