양방향 탐색(Bidirectional Search)

(출처: 종만북)

 

BFS의 단점은 탐색 깊이(depth)가 늘어날수록 탐색 공간이 기하급수적으로 증가한다는 것인데요, 양방향 탐색(Bidirectional Search)으로 depth를 절반 가량 줄일 수 있습니다.

BFS시 탐색의 분기 수(branching factor)와 탐색 깊이에 따른 시간복잡도는 \(O(b^d)\)인데요, 시작점과 끝점에서 양방향 탐색을 사용할 경우 탐색 깊이가 절반인 탐색을 두번 하는 것과 같기 때문에 시간 복잡도는 \(O(b^{d/2})\)가 됩니다.

 

설명만 들으면 무조건 BFS보다 양방향 탐색이 나은 것 같은데요, 양방향 탐색을 쓰기 힘든 때가 있습니다.

• 정방향 간선은 찾기 쉽지만 역방향 간선을 찾기 힘든 경우 (ex. 2048)
• 각 정점마다 역방향 간선이 아주 많은 경우

 

class State;

// x의 부호 반환
int sgn(int x) { if(!x) return 0; return x>0?1:-1; }

// x의 절대값을 1 증가시킴
int incr(int x) { return x<0?x-1:x+1; }

// start에서 finish까지 가는 최단경로의 길이를 반환
int bidirectional(State start, State finish) {
	map<State, int> c;	// 각 정점까지의 최단경로 길이 저장
	queue<State> q;

	if (start==finish) return 0;
	q.push(start);	c[start] = 1;
	q.push(finish);	c[finish] = -1;
	while (!q.empty()) {
		State current = q.front();
		q.pop();

		vector<State> adj = current.getAdjacent();	// 인접 노드 받아오기
		for (int i=0; i<adj.size(); ++i) {
			map<State, int>::iterator it = c.find(adj[i]);
			if (it==c.end()) {
				c[adj[i]] = incr(c[current]);
				q.push(adj[i]);
			} else if (sgn(it->second) != sgn(c[current]))	// 가운데서 만난 경우
				return abs(it->second) + abs(c[current]) - 1;
		}
	}

	// 최단경로를 찾지 못한 경우
	return -1;
}

위 코드는 양방향 탐색 알고리즘을 구현한 코드입니다.

탐색 방향이 정방향인지, 역방향인지를 양수/음수로 구별하기 때문에 시작점의 최단거리도 1, -1로 설정합니다. 가운데서 만난 경우 두 정점까지의 최단거리를 합한 뒤 처음에 더한 1을 각각 빼고, 두 정점 사이 간선을 하나 더하면 최단경로를 얻을 수 있습니다.