포스트

백트래킹(Backtracking)

백트래킹(Backtracking)
  • 백트래킹은 여러 후보해 중 특정 조건을 충족시키는 모든 해를 찾는 알고리즘이다.
    • 후보해는 해가 될 수 있는 가능성을 가진 부분해의 조합이다.
    • 해를 찾는 비용을 줄이기 위해 방문할 노드의 수를 최소화하는 것이 중요하다.
  • 이는 보통 DFS로 구현된다.

과정

  1. 해를 찾아가는 과정은 뿌리부터 출발한다. 뿌리도 하나의 부분해이다.
  2. 현재 위치한 부분해에서 선택 가능한 다음 부분해의 목록을 얻는다.
  3. 2단계에서 얻는 목록의 부분해들을 하나씩 방문한다.
  4. 방문한 부분해가 해가 될 수 있는 조건을 만족하면 그 자리에서 단계 2,3을 수행한다. 그렇지 않으면 이전 부분해로 돌아 나와 다른 부분해를 시도한다.
  5. 최종해를 얻을 때까지 또는 모든 경우의 수를 확인해도 해가 없음을 확인할 때까지 반복한다.
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.