[알고리즘] 백트래킹(되추적)

유재식·2020년 10월 12일
1
post-thumbnail

백트래킹(Backtracking)

어떤 노드의 유망성을 점검한 후, 유망하지 않다고 판정이 되면 그 노드의 후손 노드(서브 트리)들에 대한 검색을 중지하고, 그 노드의 부모노드(parent)로 돌아간다 ("backtrack").

깊이 우선 검색(DFS)과의 차이점

DFS는 가능한 모든 경로(후보)를 탐색합니다. 즉, 불필요한 노드까지 모두 검색해야 하므로 비효율 적이다.

백트래킹의 유망성 판단

어떤 노드의 유망성, 즉 해가 될 만한지 판단한 후 유망하지 않다고 결정되면 그 노드의 이전(부모)로 돌아가 다음 자식 노드로 갑니다.

해가 될 가능성이 있으면 유망하다(promising)고 하며, 유망하지 않은 노드에 가지 않는 것을 가지치기(pruning) 한다고 하는 것입니다.

백트래킹의 절차

  1. 상태공간트리의 깊이우선검색을 실시한다.
  2. 각 노드가 유망한지(promising)를 점검한다.
  3. 만일 그 노드가 유망하지 않으면, 가지치기를 수행하고, 그 노드의 부모노드로 돌아가서 검색을 계속한다.
profile
토프레 무접점 사고싶다

0개의 댓글