알고리즘을 하자 (너비 우선 탐색)

(이 부분은 스튜어드 러셀의 인공지능을 이용해서 설명합니다.)

 

너비 우선 탐색이라고 불리는 너비 우선 검색(breadth-first search)은 뿌리 노드를 먼저 확장하고, 뿌리 노드의 모든 후행자를 확장하고, 그 후행자들의 후행자들을 확장하는 식으로 진행하는 간단한 전략입니다. 일반화 하자면, 검색 트리의 임의의 깊이에서 그 깊이에 있는 모든 노드가 확장된 후에야 그다음 수준의 노드들이 확장됩니다. 

 

너비 우선 검색은 일반적 그래프 검색 알고리즘의 한 예로, 확장되지 않은 노드 중 가장 얕은 노드를 선택해서 확장한다는 전략을 사용합니다. 이러한 전략은 전선을 FIFO(First In First Out) 대기열에 담기만 하면 간단히 구현 할 수 있습니다. 

즉, 새 노드들이 대기열의 뒤에 추가되고, 오래된 노드들(새 노드들보다 항상 더 얕은)이 먼저 확장됩니다. 이 알고리즘에는 일반적 그래프 검색 알고리즘을 약간 비튼 부분이 있는데, 바로 목표 판정을 확장할 노드를 선택한 시점에서 수행하는 것이 아니라 애초에 노드를 생성할 때 수행한다는 것입니다. 왜 그렇게 하는지는 천천히 알아보도록 합시다.

또한 그래프 검색을 위한 일반적 틀을 따르는 이 알고리즘이 전선이나 탐색된 집합에 이미 있는 노드로 이어지는 새 경로를 모두 폐기한다는 점도 주목하여야 합니다. 그런 경로의 깊이가 이미 발견된 임의의 경로의 깊이가 이미 발견된 임의의 경로의 깊이보다 더 얕을 수는 없다는 점을 쉽게 이해할 수 있을 것입니다. 따라서 너비 우선 검색에서 전선에 있는 각 노드로 가는 경로는 항상 가장 얕은 경로입니다. 만일 가장 얕은 목표 노드가 어떤 유한한 깊이 d에 있다면, 너비 우선 검색은 더 얕은 노드들을 모두 생성한 후 결국 그 목표 노드를 찾아냅니다. 그리고 목표 노드가 생성된 즉시 그것이 가장 얕은 목표 노드임을 알 수 있다는 점도 주목하시기 바랍니다. 그 시점에서는 더 얕은 노드들이 이미 모두 생성되었고 목표 판정에 실패 했을 것이기 때문입니다. 그런데 가장 얕은 목표 노드가 항상 최적의 해답이 되는 것은 아닙니다. 기술적으로 말하자면, 너비 우선 검색은 경로 비용이 노드 깊이의 비감소 함수(nondecreasing function)일 때 최적입니다. 그런 경우로 가장 흔한 것은 모두 동작의 비용이 같을 때입니다.

(파이썬) 출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

 

 

지금까지 살펴본 너비 우선 검색의 속성들은 훌륭합니다. 그러나 시간과 공간 복잡도는 그리 좋지 않았습니다. 모든 상태에 b개의 후행자가 있는 균일한 트리를 검색한다고 합시다. 그러한 검색 트리의 뿌리는 첫 수준에서 b개의 노드를 생성하며, 그 노드들은 각자 b개의 노드를 더 생성하므로 둘째 수준에서 노드는 총 b의 2승개입니다. 이들 역시 각각 노드 b개를 생성하므로 셋째 수준에서 노드는 총 b3개가 되며, 그 다음 수준에서도 마찬가지로 진행됩니다. 해답이 깊이 d에 있다고 합시다. 최악의 경우 해답은 그 수준에서 생성되는 마지막 노드입니다.

 

공간 복잡도를 보자면, 확장된 모든 노드를 explored집합에 저장하는 임의의 종류의 그래프 검색의 공각 복잡도는 항상 시간 복잡도의 b 거듭제곱보다 지수가 낮은 거듭제곱으로 한정됩니다. 구체적으로, 너비 우선 검색에서 생성된 모든 노드는 메모리에 계속 남아있습니다.

 

깊이	노드 개수	시간	메모리
2	110	.11밀리초	107킬로바이트
4	11,110	11밀리초	10.6킬로바이트
6	10의 6승	1.1초	1기가바이트
8	10의 8승	2분	103기가바이트
10	10의 10승	3시간	10테라바이트
12	10의 12승	13일	1페타바이트
14	10의 14승	3.5년	99페타바이트
16	10의 16승	350년	10엑사바이트

윗 그림에서 2가지 교훈(단점?)을 얻을 수 있습니다. 첫째로, 너비 우선 검색에서는 실행 시간보다 메모리 요구량이 더 큰 문제입니다. 검색 깊이가 12인 중요한 문제의 해답을 얻기 위해 13일을 기다리려는 사람은 있을지 몰라도, 메모리가 1페타바이트인 개인용 컴퓨터는 현재로서는 없습니다. 다행히 메모리를 덜 사용하는 다른 전략들이 존재합니다.

둘째 교훈은 시간이 여전히 주요 요인이라는 것입니다. 만일 문제의 해답이 깊이 16에 있다면, 너비 우선 검색으로 그 해답을 찾으려면 약 350년이 걸립니다. 지수적 복잡도를 가진 검색 문제는 극히 간단한 경우가 아닌 한 정보없는 방법으로는 풀 수 없습니다.