백트래킹

전부확인하지만, 조건을 두어서 확인을 최소화 하는 기법

개요

• 퇴각 검색 / 역추적
• 모든 조합을 시도해서 문제의 해를 찾는다.
• 해를 얻을 때 까지 모든 가능성을 시도한다.
• 모든 가능성은 하나의 트리처럼 구성할 수 있으며, 가지(선택지)중에 해결책이 있다. 이 가지를 상태공간트리라고 한다.
• 여러가지 선택지들이 존재하는 상황에서 하나의 집합이 생성된다.
• 이런 선택을 반복하면서 최종 상태에 도달한다.
• 보통 재귀함수로 구현된다.
• 그러나 이 방법을 사용하면 가능성이 없는 노드의 후손 노드 까지 검색하기 때문에 비효율적이다.

특징 - 유망하다(promising)

• 모든 후보를 검사하지 않는다.
• 어떤 노드의 유망성을 점검한 후, 유망하지 않으면 그 노드의 부모로 되돌아가서 다음 자식 노드로 간다.
• 유망하다 -> 어떤 노드를 방문했을 때 그 경로가 해답일 가능성이 있다.
• 가지치기(pruning) -> 유망하지 않은 노드가 포함되는 경로는 더이상 고려하지 않는다.

완전탐색(DFS)와의 차이

• 어떤 노드에서 출발하는 경로가 해답일 가능성이 없을때, 그 경로를 따라가지 않는다.
• 상태에 조건을 주면서 해보는 것이다.
• 즉, 불필요한 경로를 조기에 차단하는 것이다.
• 하지만 최악의 경우에는 처리가 불가능 할 수 있다.

절차

• 상태 공간 트리의 깊이우선검색(DFS)를 실행한다.
• 유망한지 점검한다.
• 유망하지 않으면, 부모노드로 돌아가서 다른 노드의 검색을 계속한다.

알고리즘

backtrack (node v)
    if promising v == false then return;
    if there is a solution at v -> solution
    else 
        for each child u of v
            backtrack( u )

백트래킹 예시

당첨 리프노드 찾기

• 루트에서 갈 수 있는 노드를 선택한다.
• 꽝 노드 까지 전달하면 최근 선택으로 되돌아와서 다시 시작한다.
• 더 이상의 선택지가 없다면 이전 선택지로 돌아가서 다른 선택을한다.
• 루트까지 돌아갔을 경우 더이상 선택지가 없다면 찾는답이 없다.

8-Queens 문제

• 퀸 8개를 8개의 체스판 안에서 서로를 공격할 수 없도록 배치하는 모든 경우를 구하는 문제이다.
• 후보는 64C8로, 4,426,165,368(44억)개가 있다.
• 44억 개의 후보 중에서 92개를 효율적으로 찾아내야한다.

부분집합의 합 문제

• 백트래킹 조건 : 집합이 모두 자연수 / 더한 값이 특정한 경우
• 유한개의 정수로 이루어진 집합이 있을 때, 부분집합의 원소를 모두 더한 값이 0 이되는 경우를 찾기 : 이때는 불가하다.