백트래킹(Backtracking)
백트래킹(Backtracking)
- 백트래킹은 여러 후보해 중 특정 조건을 충족시키는 모든 해를 찾는 알고리즘이다.
- 후보해는 해가 될 수 있는 가능성을 가진 부분해의 조합이다.
- 해를 찾는 비용을 줄이기 위해 방문할 노드의 수를 최소화하는 것이 중요하다.
- 이는 보통 DFS로 구현된다.
과정
- 해를 찾아가는 과정은 뿌리부터 출발한다. 뿌리도 하나의 부분해이다.
- 현재 위치한 부분해에서 선택 가능한 다음 부분해의 목록을 얻는다.
- 2단계에서 얻는 목록의 부분해들을 하나씩 방문한다.
- 방문한 부분해가 해가 될 수 있는 조건을 만족하면 그 자리에서 단계 2,3을 수행한다. 그렇지 않으면 이전 부분해로 돌아 나와 다른 부분해를 시도한다.
- 최종해를 얻을 때까지 또는 모든 경우의 수를 확인해도 해가 없음을 확인할 때까지 반복한다.
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.