🔗 관련 문서: Wikipedia - 탐색 알고리즘
탐색(Search)은 문제의 답이 될 수 있는 것들의 집합을 상태 공간(state space)으로 간주하고, 초기 상태에서 목표 상태에 도달하기 위한 경로를 체계적으로 검색하는 과정이다. 인공지능에서 탐색은 추론, 계획 수립, 게임 플레이 등 다양한 문제 해결의 근간이 되는 기법이다.
탐색 문제는 일반적으로 다음 다섯 가지 요소로 정의된다.
여러 탐색 알고리즘의 성능은 다음 네 가지 기준으로 비교한다.
탐색은 크게 맹목적 탐색(uninformed / blind search)과 목표까지의 거리에 대한 추가 정보를 활용하는 정보 기반 탐색(informed / heuristic search), 그리고 경로 전체가 아닌 현재 상태 주변만 살피는 지역 탐색(local search)으로 나눌 수 있다.
맹목적 탐색은 목표까지 남은 거리 등 문제에 특화된 추가 정보(휴리스틱) 없이, 상태 공간의 구조만을 이용해 체계적으로 탐색하는 방법이다.
시작 노드로부터 얕은 깊이의 노드부터 순차적으로 모든 형제 노드를 탐색한 뒤 다음 깊이로 내려가는 방법이다. 목표 상태를 찾을 때까지 생성된 모든 노드를 큐(queue, FIFO)에 넣어 관리하므로 메모리 사용량이 크다는 단점이 있다. 그러나 각 단계에서 이동 비용이 모두 동일(균일)하다면, 얕은 깊이의 해부터 확인하므로 완비적이며 최적해(전역 최적값)를 보장한다.
한 방향으로 갈 수 있는 만큼 깊이 내려간 뒤, 더 이상 진행할 수 없으면 되돌아와(backtracking) 다른 경로를 탐색하는 방법이다. 스택(stack, LIFO) 구조로 관리되어 BFS에 비해 메모리 부담이 적지만, 먼저 도달한 해가 최단 경로라는 보장이 없어 최적성을 보장하지 않는다. 또한 무한히 깊은 경로나 순환이 있는 공간에서는 완비성도 보장되지 않는다.
탐색 깊이에 제한을 두는 깊이 제한 탐색(depth-limited search)을 적용하면 무한 루프는 방지할 수 있지만, 제한된 깊이 안에 해가 없으면 찾지 못하고, 설령 찾아도 최단 경로라는 보장은 여전히 없다.
각 경로의 누적 비용 $g(n)$이 가장 낮은 노드부터 우선적으로 확장하는 방법이다. 이동 비용이 모두 동일하지 않은 경우에도 완비적이며 최적해를 보장하지만, 비용이 낮은 노드를 계속 우선 처리하기 위해 우선순위 큐를 사용해야 하므로 계산·메모리 부담이 크다.
탐색 깊이 제한을 0부터 시작하여 점차 1씩 증가시키면서 깊이 우선 탐색을 반복 수행하는 방법이다. DFS의 낮은 메모리 사용량과 BFS의 완비성·최적성(균일 비용 조건에서)을 동시에 갖춘 절충안으로 평가된다.
정보 기반 탐색은 목표까지 남은 비용을 추정하는 휴리스틱 함수 $h(n)$을 활용하여 탐색 효율을 높이는 방법이다.
휴리스틱 함수 $h(n)$값, 즉 목표까지 남았다고 추정되는 비용이 가장 작은 노드를 우선적으로 확장하는 방법이다. 지금까지의 실제 이동 비용은 고려하지 않으므로 계산이 빠르지만, 최적해를 보장하지 못한다.
A* 알고리즘은 시작 노드로부터 실제로 소요된 비용 $g(n)$과 목표까지 남은 비용의 추정치인 휴리스틱 함수 $h(n)$을 함께 고려한 평가함수를 사용한다.
지역 탐색은 지금까지의 경로를 기억하지 않고, 현재 상태 주변(이웃)만을 살피며 상태를 개선해 나가는 방법이다. 메모리 사용이 적어 큰 문제에 적합하지만, 탐색 트리 전체를 보지 못하므로 전역 최적값을 보장하지 못하는 경우가 많다.
현재 상태의 이웃 상태들 중 가장 개선되는 방향으로만 이동하는 탐욕적(greedy) 지역 탐색 기법이다. 구현이 간단하고 계산이 빠르지만, 주변 이웃보다는 낫지만 전체적으로는 최선이 아닌 지역 최적값(local optimum)에 빠지면 그 지점에서 더 이상 나아가지 못하는 한계가 있다. 따라서 전역 최적값을 보장하지 않는다.
언덕 오르기의 지역 최적값 문제를 완화하기 위해, 일정 확률로 더 나쁜 상태로도 이동을 허용하는 기법이다. 금속을 서서히 냉각시키며 안정적인 결정 구조를 얻는 담금질(annealing) 과정에서 착안했으며, 탐색이 진행될수록(온도가 낮아질수록) 나쁜 상태로의 이동 확률을 점차 줄여나간다.
주요 탐색 기법의 완비성·최적성을 정리하면 다음과 같다. (단, 완비성·최적성은 상태 공간이 유한하고 이동 비용이 0보다 큰 일반적인 조건을 기준으로 한다)
| 탐색 기법 | 완비성 | 최적성 | 비고 |
|---|---|---|---|
| BFS | O | O (비용 균일 시) | 메모리 부담 큼 |
| DFS | △ (무한공간 X) | X | 메모리 부담 적음 |
| UCS | O | O | 비용 비균일에도 최적 |
| IDS | O | O (비용 균일 시) | DFS의 메모리 + BFS의 완비성 |
| 탐욕적 최우선 탐색 | X | X | $h(n)$만 고려 |
| A* (허용적 휴리스틱) | O | O | $f(n)=g(n)+h(n)$ |
| 언덕 오르기 | X | X | 지역 최적값에 빠질 수 있음 |