상태 공간 완전 탐색

물건 20개 가운데 몇 개를 골라 가방에 넣어 가치를 가장 크게 하려 한다. 가능한 모든 조합을 따져 보면 답이 틀릴 리 없다. 20개의 조합은 약 100만 가지라 컴퓨터는 1초도 안 되어 끝낸다. 그런데 물건이 40개이면 1조 가지가 넘어 몇십 분이 걸리고, 60개이면 수십 년이 걸린다. 순서까지 정해야 하는 문제는 더 빨리 감당할 수 없게 된다. 완전 탐색은 언제 쓸 수 있고, 모든 경우를 빠짐없이 늘어놓으려면 어떻게 해야 할까?

결정할 대상의 수 n

3.1.1상태와 결정으로 나타내기

완전 탐색은 가능한 모든 경우를 하나도 빠짐없이, 겹치지 않게 살펴보는 방법이다. 그러려면 문제를 상태와 결정으로 나타낸다. 물건 고르기라면 '지금까지 어떤 물건을 골랐는가'가 상태이고, '다음 물건을 넣을까 말까'가 결정이다. 처음 상태에서 결정을 하나씩 내릴 때마다 상태가 갈라지므로, 모든 경우는 하나의 트리가 된다. 이 트리를 상태 공간 트리라 한다. 컴퓨터는 재귀 함수로 트리를 깊이 우선으로 훑으며, 잎에 이를 때마다 그 경우가 답의 조건을 만족하는지 확인한다.

그림 1에서 \(n\)을 바꾸어 보자. 1초에 10억 가지를 검사한다고 하면, 고르기 문제는 \(n = 30\)에서 1초, \(n = 40\)에서 약 18분, \(n = 50\)에서 약 13일이 걸린다. 순서 문제는 더 빨라서 \(n = 13\)에서 6초, \(n = 15\)에서 약 22분, \(n = 20\)에서 약 77년이다. 그래서 완전 탐색은 대상이 수십 개를 넘지 않는 문제에 쓰고, 그보다 크면 쓸모없는 가지를 잘라 내거나 다른 방법을 찾는다.¹

3.1.2빠짐없이, 겹치지 않게

완전 탐색이 맞는 답을 주려면 모든 경우를 한 번씩만 살펴야 한다. 같은 경우를 두 번 살피면 시간이 낭비되고, 하나라도 빠뜨리면 그것이 답일 때 틀린다. 결정을 정해진 순서로 하나씩 내리는 상태 공간 트리는 이 두 조건을 저절로 만족한다. 순열을 만들 때는 아직 쓰지 않은 원소만 다음 자리에 놓고, 조합을 만들 때는 앞에서 고른 원소보다 뒤의 원소만 고르면 같은 조합을 두 번 만들지 않는다. 그리고 탐색하기 전에 경우의 수를 먼저 계산해 보면, 그 문제를 완전 탐색으로 풀 수 있는지 미리 판단할 수 있다.

3.1.3예제 풀이

물건마다 넣을지 말지 두 가지이므로 \(2^4 = 16\)가지이다. 무게가 10 kg 이하인 조합 가운데 가치가 큰 것을 찾는다. 4 kg과 3 kg을 넣으면 7 kg, 가치 90이다. 여기에 5 kg을 더하면 12 kg으로 넘고, 6 kg을 더해도 13 kg으로 넘는다.

6 kg과 4 kg은 10 kg, 가치 70이고, 6 kg과 3 kg은 9 kg, 가치 80이다. 5 kg과 4 kg은 가치 50, 5 kg과 3 kg은 가치 60이다. 16가지를 모두 살펴보면 4 kg과 3 kg의 조합이 가치 90으로 가장 크다. 물건이 4개이면 손으로도 다 따질 수 있지만, 40개이면 1조 가지가 넘는다. 즉 완전 탐색은 언제나 맞는 답을 주지만, 그 값은 경우의 수만큼의 시간이다. 그래서 다음 절에서는 살펴볼 필요가 없는 가지를 미리 잘라 내는 방법을 배운다.

아래 탐구 카드에서 문제를 상태와 결정으로 나타내 상태 공간 트리를 그리고, 그 트리를 재귀로 훑어 보자.

1. 체스에서 둘 수 있는 게임의 가짓수는 약 \(10^{120}\)으로 추정되어, 관측 가능한 우주의 원자 수(약 \(10^{80}\))보다 훨씬 많다. 그래서 체스 프로그램은 완전 탐색 대신 가지치기와 평가 함수를 쓴다.