Updated February 28, 2023
Introduction to Bidirectional Search
Bidirectional search is a graph search where unlike Breadth First search and Depth First Search, the search begins simultaneously from Source vertex and Goal vertex and ends when the two searches meet somewhere in between in the graph. This is thus especially used for getting results in a fraction of the time taken by both DFS and FS searches. The search from the initial node is forward search while that from the goal node is backwards. It is also based on heuristic search meaning finding the shortest path to goal optimally.
Bidirectional Search Algorithm
Heuristic refers to the concept of finding the shortest path from the current node in the graph to the goal node. The search always takes the shortest path to the goal node. This principle is used in a bidirectional heuristic search. The only difference being the two simultaneous searches from the initial point and from goal vertex. The main idea behind bidirectional searches is to reduce the time taken for search drastically.
This happens when both searches happen simultaneously from the initial node depth or breadth-first and backwards from goal nodes intersecting somewhere in between of the graph. Now the path traverses through the initial node through the intersecting point to goal vertex is the shortest path found because of this search. This is the shortest path and found in a fraction of time taken by other search algorithms.
This can be simplified by the following example.
Step 1: Say, A is the initial node and O is the goal node, and H is the intersection node.
Step 2: We will start searching simultaneously from start to goal node and backward from goal to start node.
Step 3: Whenever the forward search and backward search intersect at one node, then the searching stops.
Thus, it is possible when both the Start node and goal node are known and unique, separate from each other. Also, the branching factor is the same for both traversals in the graph. Also, other points to be noted are that bidirectional searches are complete if a breadth-first search is used for both traversals, i.e. for both paths from start node till intersection and from goal node till intersection.
Time and Space complexity of the bidirectional search is represented by O(b^{d/2})
Two main types of bidirectional searches are as follows:
- Front to back or BFEA
- Front to Front or BFFA
1. Front to back or BFEA
In bidirectional Front, to Front Search, two heuristic functions are needed. First is the estimated distance from a node to goal state using forwards search and second, node to start state using reverse action. Here, h is calculated in the algorithm, and it is the heuristic value of the distance between the node n to the root of the opposite search tree s or t. This is the most widely used bidirectional search algorithm of the three types.
2. Front to Front or BFFA
Here the distance of all nodes is calculated, and h is calculated as the minimum of all heuristic distances from the current node to nodes on opposing fronts.
Code:
#include <bits/stdc++.h>
using namespace std;
class Bi_Graph
{
list<int> *j;
int v;
public:
Bi_Graph(int v);
int intersect(bool *a_marked, bool *b_marked);
void edge(int x, int y);
void route(int *a_head, int *b_head, int a, int b, int intersectPoint);
void bfs(list<int> *q, bool *marked, int *head);
int bi_search(int a, int b);
};
void Bi_Graph::bfs(list<int> *q, bool *marked,int *head)
{
int c = q->front();
q->pop_front();
list<int>::iterator i;
for (i=j[c].begin();i != j[c].end();i++) {
if (!marked[*i]) {
head[*i] = c;
marked[*i] = true;
q->push_back(*i);
}
}
};
void Bi_Graph::edge(int x, int y)
{
this->j[x].push_back(y);
this->j[y].push_back(x);
};
int Bi_Graph::intersect(bool *a_marked, bool *b_marked)
{
int intersectPoint = -1;
for(int i=0;i<v;i++)
{
if(a_marked[i] && b_marked[i])
return i;
}
return -1;
};
Bi_Graph::Bi_Graph(int v)
{
this->v = v;
j = new list<int>[v];
};
void Bi_Graph::route(int *a_head, int *b_head, int a, int b, int intersectPoint)
{
vector<int> pt;
pt.push_back(intersectPoint);
int i = intersectPoint;
while (i != a)
{
pt.push_back(a_head[i]);
i = a_head[i];
}
reverse(pt.begin(), pt.end());
i = intersectPoint;
while(i != b) {
pt.push_back(b_head[i]);
i = b_head[i];
}
vector<int>::iterator iterator;
cout<<"Output is ";
for(iterator = pt.begin();iterator != pt.end();iterator++)
cout<<*iterator<<" ";
};
int Bi_Graph::bi_search(int a, int b) {
bool a_marked[v], b_marked[v];
int a_head[v], b_head[v];
list<int> a_q, b_q;
int intersectPoint = -1;
for(int i=0; i<v; i++) {
a_marked[i] = false;
b_marked[i] = false;
}
a_q.push_back(a);
a_marked[a] = true;
a_head[a]=-1;
b_q.push_back(b);
b_marked[b] = true;
b_head[b] = -1;
while (!a_q.empty() && !b_q.empty()) {
bfs(&a_q, a_marked, a_head);
bfs(&b_q, b_marked, b_head);
intersectPoint = intersect(a_marked, b_marked);
if(intersectPoint != -1) {
route(a_head, b_head, a, b, intersectPoint);
exit(0);
}
}
return -1;
}
int main()
{
int total=11,a=0,b=7;
Bi_Graph bg(total);
bg.edge(0, 2);
bg.edge(1, 2);
bg.edge(2, 4);
bg.edge(3, 4);
bg.edge(4, 5);
bg.edge(5, 6);
bg.edge(6, 7);
bg.edge(6, 8);
bg.edge(8, 9);
bg.edge(8, 10);
if (bg.bi_search(a, b) == -1)
cout << "No path ";
return 0;
}
Output:
Advantages and Disadvantages of Bidirectional Search
Given below are the advantages and disadvantages:
Advantages
Below are the advantages:
- One of the main advantages of bidirectional searches is the speed at which we get the desired results.
- It drastically reduces the time taken by the search by having simultaneous searches.
- It also saves resources for users as it requires less memory capacity to store all the searches.
Disadvantages
Below are the disadvantages:
- The fundamental issue with bidirectional search is that the user should be aware of the goal state to use bidirectional search and thereby to decrease its use cases drastically.
- The implementation is another challenge as additional code and instructions are needed to implement this algorithm, and also care has to be taken as each node and step to implement such searches.
- The algorithm must be robust enough to understand the intersection when the search should come to an end or else there’s a possibility of an infinite loop.
- It is also not possible to search backwards through all states.
Conclusion
Although it has several drawbacks, a bidirectional search is the most efficient and fastest way to get to desired search results when the goal state is known before the search begins and therefore one of the most widely used and researches search algorithms available. Anyone looking to make a career in ‘Search’ of the Database management system should have a working knowledge of all search algorithms, and bidirectional is the most unique and sought-after algorithms.
Recommended Articles
This is a guide to Bidirectional Search. Here we discuss the introduction to bidirectional Search along with algorithm, advantages and disadvantages. You may also have a look at the following articles to learn more –
