양방향 탐색
양방향 탐색(Bidirectional search)은 그래프 탐색 알고리즘의 일종으로, 시작 노드에서 목표 노드로 향하는 순방향 탐색과 목표 노드에서 시작 노드로 향하는 역방향 탐색을 동시에 진행하여 두 탐색이 중간에서 만나는 지점을 찾는 방식이다.
개요
일반적인 탐색 알고리즘(예: 너비 우선 탐색)은 시작 지점부터 목표 지점에 도달할 때까지 단방향으로 그래프를 확장한다. 반면, 양방향 탐색은 시작점과 목표점 양쪽에서 동시에 탐색을 시작함으로써 탐색 범위를 획기적으로 줄이는 것을 목적으로 한다. 두 탐색이 공통된 노드에서 만나는 순간 탐색이 종료되며, 시작 노드에서 만남의 지점까지의 경로와 만남의 지점에서 목표 노드까지의 경로를 합쳐 전체 경로를 완성한다.
특징 및 효율성
- 시간 복잡도: 분기 계수(branching factor)를 $b$, 시작 노드와 목표 노드 사이의 거리를 $d$라고 할 때, 일반적인 너비 우선 탐색(BFS)의 시간 복잡도는 $O(b^d)$이다. 양방향 탐색을 사용할 경우 각각 $d/2$만큼의 깊이만 탐색하면 되므로, 전체 시간 복잡도는 $O(b^{d/2} + b^{d/2})$ 즉, $O(b^{d/2})$가 된다. 이는 탐색 성능을 지수적으로 향상시킨다.
- 공간 복잡도: 탐색이 만나는 지점을 확인하기 위해 적어도 한 방향의 탐색 노드들을 메모리에 저장해야 하므로, 일반적으로 $O(b^{d/2})$의 공간 복잡도를 가진다.
- 완전성 및 최적성: 적절한 알고리즘(예: 너비 우선 탐색)을 기반으로 구현될 경우 솔루션을 반드시 찾아내며(완전성), 가중치가 없는 그래프에서는 최단 경로를 보장(최적성)한다.
전제 조건 및 제약
양방향 탐색이 효과적으로 작동하기 위해서는 다음과 같은 조건이 필요하다.
- 역방향 탐색 가능 여부: 목표 노드에서 시작 노드 방향으로 거슬러 올라가는 역방향 연산이 가능해야 한다. 즉, 그래프의 간선이 역방향으로도 정의되어 있거나 추론 가능해야 한다.
- 목표 상태의 명확성: 목표 상태가 단 하나이거나, 역방향 탐색을 시작할 수 있는 명확한 목표 노드 집합이 존재해야 한다.
- 접점 확인 알고리즘: 두 탐색 영역이 겹치는지 효율적으로 확인할 수 있는 데이터 구조(예: 해시 테이블)가 필요하다.
주요 활용 분야
양방향 탐색은 길 찾기 알고리즘, 인공지능의 상태 공간 탐색, 루빅스 큐브의 해법 탐색 등 탐색 공간의 크기가 크고 시작점과 끝점이 명확한 문제에서 주로 활용된다.