백트래킹

1 개요

backtracking

백트래킹, 역추적, 퇴각검색

• 한정조건을 가진 문제를 푸는 전략
• 생성 시스템이나 탐색 과정에서, 문제의 해답을 구하기 위한 추론 제어 방식의 하나
• 규칙을 적용하여 얻은 결과가 틀리면 그 규칙을 적용한 다음부터 현재까지의 결과를 무시하고 처음으로 돌아가서 다른 규칙을 선택하여 다시 시도함
• 예: DFS에서의 가지치기(pruning)

2 예시

pascal

Copy

procedure bt(c)
  if reject(P,c) then return
  if accept(P,c) then output(P,c)
  s ← first(P,c)
  while s ≠ NULL do
    bt(s)
    s ← next(P,s)

3 같이 보기

• 백점핑
• 재귀함수
• 후방 추론
• 깊이 우선 탐색
• 스도쿠 풀이 알고리즘

4 참고

• 위키백과 "백트래킹"
• 다음사전 "백트래킹"
• 다음백과 "백트래킹"
• 네이버사전 "백트래킹"
• 네이버백과 "백트래킹"
• https://goldenrabbit.co.kr/2023/12/29/코딩-테스트-합격자-되기-백트래킹-1-백트래킹과-백/
• https://goldenrabbit.co.kr/2024/01/03/코딩-테스트-합격자-되기-백트래킹-2-백트래킹-알고/