[Search] 맹목적 탐색

개요

탐색에는 크게 맹목적 탐색, 정보이용 탐색, 게임에서의 탐색 등이 있습니다.

탐색이란 문제에 대한 최적의 해를 찾기 위해 공간을 체계적으로 찾아보는 것으로, 이 때의 공간은 문제의 해가 될 수 있는 것(동작 또는 상태)들의 집합입니다.

이번 포스팅에서는 탐색의 기초이자 가장 친숙한 맹목적 탐색의 종류에 대해 알아보고, 다음 포스팅들에서 이어서 다른 탐색의 종류들을 살펴보겠습니다.

깊이 우선 탐색

깊이 우선 탐색(depth-first search, DFS)은 다음과 같은 특징을 갖습니다.

• 초기 노드에서 시작하여 깊이 방향으로 탐색
• 더 이상 진행할 수 없으면 백트래킹(부모 노드로 회귀)
• 방문한 노드는 재방문하지 않음

너비 우선 탐색

너비 우선 탐색(breath-first search, BFS)은 다음과 같은 특징을 갖습니다.

• 초기 노드에서 시작하여 너비 방향(동일한 깊이에 있는 모든 노드를 우선)으로 탐색
• 해당 깊이의 모든 노드를 탐색했으면 다음 깊이로 이동
• 방문한 노드는 재방문하지 않음

반복적 깊이 심화 탐색

깊이 제한 탐색

반복적 깊이 심화 탐색을 쉽게 이해하려면, 먼저 깊이 제한 탐색(depth-limited search)에 대해 알아야합니다.

깊이 제한 탐색은 깊이 우선 탐색이 무한 루프에 빠지거나 초기 방향을 잘못 잡아 탐색 시간이 너무 길어질 수 있는 단점을 극복하기 위해 깊이에 한계를 두는 깊이 우선 탐색입니다.

당연하게도, 이 탐색 방법에는 치명적인 단점이 있습니다. 바로 최적 해가 깊이 제한보다 더 깊은 깊이에 존재한다면, 최적 해를 찾지 못한다는 것이죠.

여기서 반복적 깊이 심화 탐색이 등장합니다.

반복적 깊이 심화 탐색

깊이 제한 탐색을 이해했다면 반복적 깊이 심화 탐색은 쉽습니다.

반복적 깊이 심화 탐색(iterative-deepening search)은 깊이 제한 탐색을 반복적으로 적용하는 것입니다.

예를 들어 깊이 제한이 1이라면, ‘깊이 1 -> 깊이 2 -> 깊이 3 -> …‘ 의 순으로 깊이 우선 탐색을 진행합니다.

이 때 깊이 제한이 늘어날 때마다 루트 노드에서부터 탐색을 다시 진행해야 합니다.

양방향 탐색

마지막 맹목적 탐색 방법으로 양방향 탐색(bidirectional search)이 있습니다.

양방향 탐색은 단순히 초기 노드와 목적 노드에서 동시에 너비 우선 탐색을 진행하는 것이며, 중간에 만나도록 하여 최단 경로를 찾는 방식입니다.

맹목적 탐색 비교

지금까지 4가지의 맹목적 탐색 방법에 대해 살펴봤습니다.

이 중 3가지 주요 개념인 깊이 우선 탐색, 너비 우선 탐색, 반복적 깊이 심화 탐색의 장담점을 비교해보겠습니다.

깊이 우선 탐색

1. 메모리 공간의 사용이 효율적이다.
2. 최적해의 최단 경로 탐색을 보장하지 못한다.
3. 탐색 시간이 매우 오래 걸릴 수 있다.

너비 우선 탐색

1. 최단 경로 해의 탐색을 보장한다. (단, 모든 간선의 길이/비용이 동일한 경우)
2. 메모리 공간의 사용이 비효율적이다.
3. 탐색에 소요되는 시간이 일정하게 늘어난다.

반복적 깊이 심화 탐색

1. 최단 경로 해의 탐색을 보장한다. (단, 모든 간선의 길이/비용이 동일한 경우)
2. 메모리 공간의 사용이 효율적이다. (깊이 우선 탐색의 장점)
3. 너비 우선 탐색에 비해 탐색에 소요되는 시간이 크게 늘지 않는다. (너비 우선 탐색의 장점)

따라서 맹목적 탐색에 있어서 반복적 깊이 심화 탐색은 가장 먼저 고려해볼 만한 탐색 방법이라고 할 수 있겠습니다.