Portfolio

1. 백트래킹

1-1. 백트래킹이란

백트래킹은 ‘완전탐색 알고리즘' 중 하나로 한 번에 하나의 문제를 해결하되, 가지치기(Pruning) 를 통해 유망하지 않은 경로는 고려하지 않고 탐색하는 방법

기본적으로 백트래킹은 '가능한 모든 방법을 탐색한다' 는데 기본 아이디어가 있다.

대표적인 완전 탐색 방법으로는 DFS (Depth First Search, 깊이 우선 탐색)이 있다.

DFS 는 현재 지점에서 방문할 곳이 있으면 재귀 호출을 이용해서 계속 이동함

DFS 의 장점 : 무한히 깊은곳을 찾아야할때 효과적

but DFS 는 모든곳을 방문하기 때문에 목표지점이 있지 않는 경로로 빠져서 비효율적이 될 수도 있음

비효율적인 경로를 차단하고 목표지점에 갈수있는 가능성이 있는 루트를 검사하는 방법이 백트래킹 알고리즘

백트래킹은 DFS에 가지치기 (Pruning) 를 통해 가도되지 않는 루트는 고려하지 않고 탐색하는 완전탐색 기법

가지치기를 얼마나 잘하느냐에 따라서 효율이 극대화 될수 있음

우리가 알아야할것은 '배제', '풀이 시간 단축'

백트래킹은 깊이우선탐색(Depth-First Search)과 마찬가지로 스택을 사용한다!

가지치기(Pruning)

가지치기는 모든 해를 전부 검사(brute force)와 백트래킹을 구분하는 핵심으로, 기준함수(현재 만들어진 케이스가 해답의 조건을 만족하는지 검사하는 함수)를 통해 가능성이 없는 케이스를 배제하여 풀이시간을 상당히 줄일 수 있다.

1-2 백트래킹 문제 접근

💡

Sum of SubSet 문제 n =4, S = { 5, 9, 11, 20 }, m = 25 일 때, S의 모든 부분집합의 합이 m이 되는 모든 경우의 수를 찾는 문제 정답: {5, 9, 11}, {5, 20}

1) 문제 상황을 상태공간 트리로 표현하기

Sum of Subset의 경우 아래 그림과 같이 집합의 각 원소의 선택 여부로 상태 공간 트리를 표현할 수 있다.

명시적 제약 조건 : 트리의 각 노드는 0 또는 1의 값을 가진다. 이때 i번째 높이의 노드는 i번째 원소의 선택 여부를 나타내며 0은 선택하지 않음, 1은 선택함을 나타낸다.

2) 루트 부터 DFS를 하여 불필요한 탐색을 하지 않고 한정 함수를 만족하는 (x[1], x[2], ..., x[n])를 찾는 것을 목표로 한다.

아래 그림은 Sum of Subset 문제에서 DFS 후 정답 25가 만들어지는 부분집합 {5. 25}를 찾아낸 상황이다.

3. 각 노드 s 에 도착할 때마다 루트에서 s까지의 경로 예를 들어 k번째 선택에선 (x[1], x[2], ..., x[k])의 튜플이 한정함수를 만족하는지 판단한다.

한정 함수는 암시적 제약 조건의 참/거짓 여부를 판별하는 함수이다. Sum of Subset의 경우 집합의 원소의 개수가 n이고 원하는 부분집합의 합이 m일 때 암시적 제약 조건은 다음과 같다. 암시적 제약 조건 : w[i]를 집합에서 i번째 원소라고 가정하면 한정함수 한정함수: 현재까지 선택한 요소와 남은 모든 요소의 합이 m 보다 커야만하고, 현재까지 선택한 요소와 남은 요소중 가장 작은 값을 더했을 때 m보다 작아야만 true를 리턴 즉 { 9 }를 선택하고 {11, 20}이 남았을 때, 9 + SumAllRest(11 + 20) ≥ 25 && 9 +MinRest(11) ≤ 25 를 만족해야만 다음 노드로 진입한다.