230221 공부내용 정리

용어 정리

백트래킹(BackTracking)

• 퇴각 검색
• 모든 조합을 시도해서 문제의 해를 찾는다.
• 해를 얻을 때 까지 모든 가능성을 시도한다.
• 모든 가능성은 하나의 트리처럼 구성할 수 있으며,
  가지 (선택지) 중에 해결책이 있다.
• 여러 가지(선택지) 들이 존재하는 상황에서 하나의 가지를 선택한다.
• 선택이 이루어지면 새로운 선택지들의 집합이 생성된다.
• 이런 선택을 반복하면서 최종 상태에 도달한다.
• 보통 재귀 함수로 구현된다.

• 모든 후보를 검사 ?

  • no!!
    
    

• 백트래킹 기법

  • 어떤 노드의 유망성을 점검한 후에 유망하지 않다고 결정되면 그 노드의 부모로 되돌아가 다음 자식 노드로 간다.

  • 유망하다

    • 어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 수 있으면 유망하다고 한다.

  • 가지치기

    • 유망하지 않은 노드가 포함되는 경로는 더 이상 고려하지 않는다.
      
      

• 백트래킹을 이용한 알고리즘은 다음과 같은 절차로 진행된다.

  1. 상태 공간 트리의 깊이 우선 검색을 실시한다.(재귀로 구현)

  2. 각 노드가 유망한지를 점검한다.

  3. 만일 그 노드가 유망하지 않으면, 그 노드의 부모 노드로 돌아가서 다른 노드로의 검색을 계속한다.