Bidirectional Search
We know our traditional searching algorithms to search for a goal vertex starting from a source
vertex using BFS.In normal graph search using BFS/DFS we begin our search in one direction usually from source vertex toward the goal vertex, but what if we start search form both direction simultaneously.
So , Bidirectional search is a graph searching algorithm which find shortest path from source to goal vertex. It runs two simultaneous search that is.
1)Forward search form source/initial vertex toward goal vertex
2)Backward search form goal/target vertex toward source vertex
Bidirectional search replaces single search graph which is likely to grow exponentially with two smaller sub graphs – one starting from initial vertex and other starting from goal vertex. The search terminates when two graphs reach at same point or intersect each-other.
For Example:
Suppose we want to find if there exists a path from vertex 0 to vertex 14. Here we can execute two searches, one from vertex 0 and other from vertex 14. When both forward and backward search meet at vertex 7, we know that we have found a path from node 0 to 14 and search can be terminated now. We can clearly see that we have successfully avoided unnecessary exploration.
Now Question is why bidirectional approach?
Ans: Because
1)in many cases it is faster.
2)It dramatically reduce the amount of required exploration.
Let us suppose,
if branching factor of tree is a and distance of goal vertex from source is d,
then the normal BFS/DFS searching complexity would be O(a^d).
On the other hand, if we execute two search operation then the complexity would be O(a^{d/2})
for each search and total complexity would be O(a^{d/2}+a^{d/2}) which is far less than O(a^d).
When to use bidirectional approach?
1)Both initial and goal states are unique and completely defined.
The branching factor is exactly the same in both directions.
Performance measures
Completeness : Bidirectional search is complete if BFS is used in both searches.
Optimality : It is optimal if BFS is used for search and paths have uniform cost.
Time and Space Complexity : Time and space complexity is O(a^{d/2})
Sample Code:
public static class Node
{
private final T data;
private final Set<Node> adjacent = new HashSet<Node>();
public Set<Node> getAdjacent() {
return adjacent;
}
public Node(T data) {
this.data = data;
}
public T getData() {
return data;
}
// returns if the node was added, false if already there
public boolean addAdjacent(Node node) {
return adjacent.add(node);
}
// returns true if any were added
public boolean addAdjacents(Set<Node> nodes) {
return adjacent.addAll(nodes);
}
}
public static boolean pathExistsBidirectional(Node a, Node b)
{
// BFS on both nodes at the same time
Queue<Node> queueA = new Queue<Node>();
Queue<Node> queueB = new Queue<Node>();
Set<Node> visitedA = new HashSet<Node>();
Set<Node> visitedB = new HashSet<Node>();
visitedA.add(a);
visitedB.add(b);
queueA.add(a);
queueB.add(b);
while (!queueA.isEmpty() && !queueB.isEmpty()) {
if (pathExistsBidirectionalHelper(queueA, visitedA, visitedB)) {
return true;
}
if (pathExistsBidirectionalHelper(queueB, visitedB, visitedA)) {
return true;
}
}
return false;
}
private static boolean pathExistsBidirectionalHelper(Queue<Node> queue, Set<Node> visitedFromThisSide, Set<Node> visitedFromThatSide) {
if (!queue.isEmpty()) {
Node next = queue.remove();
for (Node adjacent : next.getAdjacent()) {
if (visitedFromThatSide.contains(adjacent)) {
return true;
} else if (visitedFromThisSide.add(adjacent)) {
queue.add(adjacent);
}
}
}
return false;
}
We know our traditional searching algorithms to search for a goal vertex starting from a source
vertex using BFS.In normal graph search using BFS/DFS we begin our search in one direction usually from source vertex toward the goal vertex, but what if we start search form both direction simultaneously.
So , Bidirectional search is a graph searching algorithm which find shortest path from source to goal vertex. It runs two simultaneous search that is.
1)Forward search form source/initial vertex toward goal vertex
2)Backward search form goal/target vertex toward source vertex
Bidirectional search replaces single search graph which is likely to grow exponentially with two smaller sub graphs – one starting from initial vertex and other starting from goal vertex. The search terminates when two graphs reach at same point or intersect each-other.
For Example:
Suppose we want to find if there exists a path from vertex 0 to vertex 14. Here we can execute two searches, one from vertex 0 and other from vertex 14. When both forward and backward search meet at vertex 7, we know that we have found a path from node 0 to 14 and search can be terminated now. We can clearly see that we have successfully avoided unnecessary exploration.
Now Question is why bidirectional approach?
Ans: Because
1)in many cases it is faster.
2)It dramatically reduce the amount of required exploration.
Let us suppose,
if branching factor of tree is a and distance of goal vertex from source is d,
then the normal BFS/DFS searching complexity would be O(a^d).
On the other hand, if we execute two search operation then the complexity would be O(a^{d/2})
for each search and total complexity would be O(a^{d/2}+a^{d/2}) which is far less than O(a^d).
When to use bidirectional approach?
1)Both initial and goal states are unique and completely defined.
The branching factor is exactly the same in both directions.
Performance measures
Completeness : Bidirectional search is complete if BFS is used in both searches.
Optimality : It is optimal if BFS is used for search and paths have uniform cost.
Time and Space Complexity : Time and space complexity is O(a^{d/2})
Sample Code:
public static class Node
{
private final T data;
private final Set<Node> adjacent = new HashSet<Node>();
public Set<Node> getAdjacent() {
return adjacent;
}
public Node(T data) {
this.data = data;
}
public T getData() {
return data;
}
// returns if the node was added, false if already there
public boolean addAdjacent(Node node) {
return adjacent.add(node);
}
// returns true if any were added
public boolean addAdjacents(Set<Node> nodes) {
return adjacent.addAll(nodes);
}
}
public static boolean pathExistsBidirectional(Node a, Node b)
{
// BFS on both nodes at the same time
Queue<Node> queueA = new Queue<Node>();
Queue<Node> queueB = new Queue<Node>();
Set<Node> visitedA = new HashSet<Node>();
Set<Node> visitedB = new HashSet<Node>();
visitedA.add(a);
visitedB.add(b);
queueA.add(a);
queueB.add(b);
while (!queueA.isEmpty() && !queueB.isEmpty()) {
if (pathExistsBidirectionalHelper(queueA, visitedA, visitedB)) {
return true;
}
if (pathExistsBidirectionalHelper(queueB, visitedB, visitedA)) {
return true;
}
}
return false;
}
private static boolean pathExistsBidirectionalHelper(Queue<Node> queue, Set<Node> visitedFromThisSide, Set<Node> visitedFromThatSide) {
if (!queue.isEmpty()) {
Node next = queue.remove();
for (Node adjacent : next.getAdjacent()) {
if (visitedFromThatSide.contains(adjacent)) {
return true;
} else if (visitedFromThisSide.add(adjacent)) {
queue.add(adjacent);
}
}
}
return false;
}
