양방향 검색이란?
양방향 검색(Bidirectional Search)은 두 방향에서 동시에 진행되는 그래프 탐색 기법입니다. 한쪽 탐색은 출발점(시작 노드)에서 목표 노드를 향해 순방향으로 진행하고, 다른 쪽 탐색은 목표 노드에서 출발점을 향해 역방향으로 진행합니다. 이상적인 경우 두 탐색은 자료구조의 중간 지점에서 서로 만나게 됩니다.
양방향 검색 알고리즘은 방향 그래프(directed graph)에서 출발 노드와 목표 노드 사이의 최단 경로를 찾는 데 활용됩니다. 두 탐색은 각자의 위치에서 동시에 시작하며, 알고리즘은 두 탐색이 특정 노드에서 만나는 순간 종료됩니다.
양방향 접근법의 중요성
양방향 검색은 단방향 탐색에 비해 속도가 훨씬 빠른 기법으로, 그래프를 순회하는 데 소요되는 시간을 크게 단축할 수 있습니다.
또한 이 접근법은 출발 노드와 목표 노드가 명확하게 정의되어 있고, 양방향의 분기 계수(branching factor)가 동일한 경우에 특히 효율적으로 작동합니다.
성능 평가 기준
완전성(Completeness) — 두 탐색 모두 BFS(너비 우선 탐색)를 사용할 경우 완전합니다.
최적성(Optimality) — BFS로 탐색하고 경로의 비용이 균일할 경우 최적의 해를 보장합니다.
시간 및 공간 복잡도 — 시간과 공간 복잡도는 모두 O(b^{d/2})입니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Graph {
int V;
list<int> *adj;
public:
Graph(int V);
int isIntersecting(bool *s_visited, bool *t_visited);
void addEdge(int u, int v);
void printPath(int *s_parent, int *t_parent, int s,
int t, int intersectNode);
void BFS(list<int> *queue, bool *visited, int *parent);
int biDirSearch(int s, int t);
};
Graph::Graph(int V) {
this->V = V;
adj = new list<int>[V];
};
void Graph::addEdge(int u, int v) {
this->adj[u].push_back(v);
this->adj[v].push_back(u);
};
void Graph::BFS(list<int> *queue, bool *visited,
int *parent) {
int current = queue->front();
queue->pop_front();
list<int>::iterator i;
for (i=adj[current].begin();i != adj[current].end();i++) {
if (!visited[*i]) {
parent[*i] = current;
visited[*i] = true;
queue->push_back(*i);
}
}
};
int Graph::isIntersecting(bool *s_visited, bool *t_visited) {
int intersectNode = -1;
for(int i=0;i<V;i++) {
if(s_visited[i] && t_visited[i])
return i;
}
return -1;
};
void Graph::printPath(int *s_parent, int *t_parent,
int s, int t, int intersectNode) {
vector<int> path;
path.push_back(intersectNode);
int i = intersectNode;
while (i != s) {
path.push_back(s_parent[i]);
i = s_parent[i];
}
reverse(path.begin(), path.end());
i = intersectNode;
while(i != t) {
path.push_back(t_parent[i]);
i = t_parent[i];
}
vector<int>::iterator it;
cout<<"Path Traversed by the algorithm\n";
for(it = path.begin();it != path.end();it++)
cout<<*it<<" ";
cout<<"\n";
};
int Graph::biDirSearch(int s, int t) {
bool s_visited[V], t_visited[V];
int s_parent[V], t_parent[V];
list<int> s_queue, t_queue;
int intersectNode = -1;
for(int i=0; i<V; i++) {
s_visited[i] = false;
t_visited[i] = false;
}
s_queue.push_back(s);
s_visited[s] = true;
s_parent[s]=-1;
t_queue.push_back(t);
t_visited[t] = true;
t_parent[t] = -1;
while (!s_queue.empty() && !t_queue.empty()) {
BFS(&s_queue, s_visited, s_parent);
BFS(&t_queue, t_visited, t_parent);
intersectNode = isIntersecting(s_visited, t_visited);
if(intersectNode != -1) {
cout << "Path exist between " << s << " and "
<< t << "\n";
cout << "Intersection at: " << intersectNode << "\n";
printPath(s_parent, t_parent, s, t, intersectNode);
exit(0);
}
}
return -1;
}
int main() {
int n=15;
int s=0;
int t=14;
Graph g(n);
g.addEdge(0, 4);
g.addEdge(1, 4);
g.addEdge(2, 5);
g.addEdge(3, 5);
g.addEdge(4, 6);
g.addEdge(5, 6);
g.addEdge(6, 7);
g.addEdge(7, 8);
g.addEdge(8, 9);
g.addEdge(8, 10);
g.addEdge(9, 11);
g.addEdge(9, 12);
g.addEdge(10, 13);
g.addEdge(10, 14);
if (g.biDirSearch(s, t) == -1)
cout << "Path don't exist between "
<< s << " and " << t << "\n";
return 0;
}실행 결과
Path Traversed by the algorithm 0 4 6 7 8 10 14
실행 결과를 보면 알고리즘이 노드 0에서 시작해 14로 끝나는 경로를 성공적으로 찾아낸 것을 확인할 수 있습니다. 최종 경로는 0 → 4 → 6 → 7 → 8 → 10 → 14이며, 총 7개의 노드를 거쳐 목표 노드에 도달합니다.