Backtracking & State Space Search

1. Overview

백트래킹 및 상태 공간 탐색(Backtracking & State Space Search, BSS)은 모든 가능성이 열려있는 망막한 '해답의 숲'에서 가장 현명하게 길을 찾는 컴퓨터의 '시시비비 가리기' 기법입니다.

어떤 문제는 수학 공식 한 줄로 정답을 낼 수 없으며, 직접 하나하나 해봐야만 알 수 있습니다. 학습자는 현재의 선택이 정답이 될 가능성이 없다고 판단되면 즉시 '뒤로 돌아가(Backtrack)' 다른 길을 찾는 물리적 포기 전략을 배웁니다. 또한, 문제의 모든 상태를 노드로 가진 **상태 공간 트리(State Space Tree)**를 배웁니다. 특히 가지를 쳐내어 탐색량을 획기적으로 줄이는 **가지치기(Pruning)**의 수리적 효율성을 심도 있게 다룹니다. 이를 통해 미로 찾기나 퍼즐 해결 등 복잡한 조건이 얽힌 난제를 정복하는 논리 설계 능력을 확보합니다.

2. Scope & Boundaries

In-Scope

• Recursive DFS Search: 깊이 우선 탐색(DFS)을 이용한 상태 공간 순회 물리
• Pruning Strategies: 유망성(Promising) 판단을 통한 탐색 트리 절단 기법
• Constraint Satisfaction: 정해진 물리적 제약 사항을 만족하는 해집합 발굴
• Classic Search Problems: N-Queens, 스도쿠, 외판원 문제(TSP), 미로 탈출

Out-of-Scope

• 확률적 탐색이나 유전 알고리즘 (04-03-03 노드로 위임 가능하나 여기서는 논리적 백트래킹에 집중)
• 단순한 그래프 탐색 기초 (04-04-01 노드에서 분담)

Boundaries

• BSS vs. Brute Force: Brute Force가 '무식하게 끝까지' 다 해본다면, BSS는 '안 될 것 같으면 즉시 복귀'함으로써 물리적 시간을 비약적으로 단축하여 구분합니다.

3. Counterexample

• 단순히 "모든 경우를 따지는 것"이라 설명하는 것은 BSS 학습이 아닙니다. 왜 가중치 기반 가지치기가 없는 백트래킹이 사실상 완전 탐색과 다를 바 없는 지수 시간 연산을 하는지 물리적 폭발 관점에서 증명할 수 있어야 하며, 해답을 찾은 즉시 재귀 호출을 중단(Terminate)하는 탈출 조건이 누락되었을 때 하드웨어가 왜 불필요한 연산을 반복하게 되는지 설명하지 못한다면 BSS의 효율을 이해하지 못한 것입니다.

4. Prerequisites

• Stacks, Queues & Deques (Basic): 재귀용 시스템 스택 이해가 필수입니다. (04-01-03 SQD)
• Recursion & Divide-and-Conquer (Recommended): 재귀 모델링 기초 이해가 권장됩니다. (04-03-01 RDC)

5. Learning Map

1. The Choice Tree: 선택의 순간마다 갈라지는 '운명의 나무(State Space Tree)'를 그립니다.
2. Trial and Error: 한 길을 끝까지 가보고 실패하면 직전 갈림길로 물리 복구하는 법을 배웁니다.
3. The Pruning Saw: 싹수가 노란(Unpromising) 가지를 미리 발견하고 잘라내는 혜안을 익힙니다.
4. Valid Configuration: 수억 개의 오답 속에서 단 하나의 완벽한 보석( 정답)을 캐내는 기술을 완성합니다.

6. Learning Topics

Basic

Core: 상태 공간 트리와 DFS (Search Traversal)

• Why to Learn: 복잡한 문제의 해답군을 계층적으로 시각화하고 탐색 경로를 추적하기 위해서입니다.
• What to Learn:
  • State Space Tree: 모든 가능한 선택의 시퀀스를 트리 노드로 사상한 물리 모델
  • DFS with Backtracking: 깊게 파고들되 막히면 되돌아오는 물리 시퀀스
  • Solution Node: 리프 노드 중 제약 조건을 모두 만족하는 특별한 지점
• How to Learn:
  • $1$부터 $3$까지 숫자의 순열을 백트래킹으로 생성하며, 스택에 쌓이는 숫자들의 물리적 변화 기록 실습
  • 간단한 미로 지도에서 막다른 골목에 도달했을 때 '직전 갈림길'로 돌아가는 과정을 화살표로 그려보기
• Implement: $n$개의 요소 중 $k$개를 뽑는 모든 조합을 생성하는 백트래킹 함수

Recommended

Core: 유망성 판단과 가지치기 (Promising & Pruning)

• Why to Learn: 우주의 모든 원자 수보다 많은 경우의 수를 현실적으로 줄일 수 있는 유일한 물리적 무기이기 때문입니다.
• What to Learn:
  • Constraint Checking: 현재 노드에서 정답으로 갈 가능성이 있는지 물리적 검문
  • Pruning (가지치기): 유망하지 않은 하위 트리를 통째로 무시하여 연산량을 절감하는 기법
  • Bounding Function: 해답의 품질이 이미 찾은 해보다 좋을지 수리적으로 예측
• How to Learn:
  • $N-Queens$ 문제에서 같은 열이나 대각선에 퀸이 있는지 체크하는 함수가 탐색 횟수를 얼마나 물리적으로 줄이는지 수치 비교 실습
  • $Sum of Subsets$ 문제에서 현재 합이 목표치를 넘었을 때 즉시 중단하는 로직 삽입 실습
• Implement: 효율적인 가지치기 로직이 포함된 N-Queens 해결 엔진

Practical

Core: 제약 충족 문제와 최적화 (Constraint Satisfaction)

• Why to Learn: 스케줄링, 물류 배치, 하드웨어 설계 등 현실의 엄격한 제약 조건을 풀어내기 위함입니다.
• What to Learn:
  • CSP (Constraint Satisfaction Problem): 변수, 도메인, 제약 조건으로 이루어진 수리 모델
  • Sudoku Solver: 9x9 격자의 행/열/박스 제약을 백트래킹으로 만족시키는 물리 경로
  • Map Coloring: 인접한 영토는 다른 색으로 칠해야 하는 위상적 탐색
• How to Learn:
  • 스도쿠 빈칸을 채워나가며, 숫자를 하나 넣을 때마다 주변 칸들의 도메인이 어떻게 물리적으로 좁아지는지(Variable ordering) 관찰 실습
  • 가장 제약이 심한 노드부터 방문하는 'Minimum Remaining Values' 휴리스틱 분석
• Implement: 복잡한 제약 조건이 얽힌 스도쿠 게임을 자동으로 풀어주는 백트래킹 봇

Advanced

Core: 분기 한정과 실시간 서칭 (Branch and Bound)

• Why to Learn: 정답 유무를 넘어 '가장 좋은 정답'을 찾는 최적화 문제에서 최고의 성능을 내기 위해서입니다.
• What to Learn:
  • Branch and Bound (B&B): 최선의 비용 하한(Lower bound)을 계산하여 탐색 범위를 극한으로 좁히는 기법
  • Best-first Search: 큐(Queue)를 이용해 가장 유망해 보이는 노드부터 물리적으로 확장
  • Game Tree (Minimax): 적의 최선과 나의 최선이 충돌하는 대결 구도의 상태 공간 탐색
• How to Learn:
  • 외판원 문제(TSP)를 B&B로 풀 때, 특정 경로의 가중치 합이 이미 발견된 최단 거리보다 크면 왜 버려야 하는지 수리적 증명 실습
  • 체스나 틱택토 게임의 수읽기 트리를 구성하고 '알파-베타 가지치기'의 물리적 생략 효과 분석
• Implement: 현재까지의 가중치를 기반으로 미래의 최소 비용을 예측하여 가지치기하는 TSP 최적화 루틴

7. Terminology

8. References

Primary

• [P2] SWEBOK v4.0 - Software Construction / Runtime Efficiency (Search Techniques) — Search strategies.
• [P1] CS2023 - AL/Algorithms and Complexity (Search Paradigms) — Core requirements.

Secondary

• [Artificial Intelligence: A Modern Approach] Russell — CSP and state space depth.
• [The Algorithm Design Manual] Steven Skiena — Backtracking and pruning recipes.

Industry

• [IBM: Constraint Solver for Scheduling] — Real-world industry application.
• [Google: OR-Tools (Constraint Programming)] — Advanced solver implementation.

9. Final Checklist

Primary

• '백트래킹' 과정에서 이전 상태를 복구하기 위해 '상태 관리 배열'이나 '시스템 스택'이 물리적으로 어떻게 사용되는지 설명 가능한가? (P1)
• '가지치기'가 적용된 알고리즘과 적용되지 않은 알고리즘의 탐색 노드 수 차이를 수리적으로 입증할 수 있는 가? (P1)

Secondary

• DFS와 백트래킹의 관계가 왜 시스템 자원(재귀 깊이)의 물리적 한계와 직결되는지 소통 가능한가?
• 주어진 문제의 제약 조건을 이용해 '유망성 함수'를 설계하고 이를 코드로 옮기는 과정을 도출할 수 있는 가?

Industry

• 배송 경로 최적화나 물류 관리 솔루션 설계 시, 백트래킹 기반의 CSP 기법이 왜 물리적 표준 인프라인지 기술할 수 있는 가? (SFIA)
• 대용량 퍼즐 게임 서버에서 수천 명의 동시 요청을 처리하기 위해 탐색 트리의 깊이를 제한하는 'Iterative Deepening'의 물리적 필요성을 제안할 수 있는 가?