백트래킹

1 개요[ | ]

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

2 예시[ | ]

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 참고[ | ]

문서 댓글 ({{ doc_comments.length }})
{{ comment.name }} {{ comment.created | snstime }}