Algorithm - Backtracking

이소라·2022년 12월 27일
0

Algorithm

목록 보기
36/77

Backtracking

  • 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾는 기법
  • 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것
    • 조건문을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색함
  • 최적화 문제와 결정 문제를 푸는 방법이 됨

DFS & Backtracking

  • DFS
    • 가능한 모든 경로를 탐색함
  • Backtracking
    • 해를 찾아가는 도중, 지금 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아감
    • 노드가 유망한지 판단하고 유망하지 않으면 가지차기하는 것
      • 유망하다(promising) = 해가 될 가능성이 있다
      • 가지치기(pruning) = 유망하지 않은 노드에 가지 않는다
    • 가지치기를 얼마나 잘 하느냐에 따라 효율성이 결정됨

참고

0개의 댓글