Hello readers, in this article let’s try to understand what is bidirectional search, its advantages, disadvantages, and its implementation in python.
Also read: Depth First Iterative Deepening (DFID) Algorithm in Python
What is Bidirectional Search?
A graph search algorithm called bidirectional search conducts two searches simultaneously. When the two searches meet at the midway, one stops moving forward from the starting point and the other stops moving backwards from the destination. For issues with a single start state and a single objective state, it is helpful.
When implementing a bidirectional search for k = 1, 2,…, the Depth First Iterative Deepening Search (DFID) can be used. In the kth iteration, instead of storing states but rather simply matching against the stored states generated from the forwarding direction, all states in the forward direction are generated from the start state up to depth k using breadth-first search and from the goal state up to depth k and depth k+ 1.
Here, to identify odd-length answers, a reverse or backward search to depth k+ 1 is required. If a match is identified, the route from the beginning to the matched state and from the matched state to the objective state can then be determined. It should be noted that each node has a link to its successors as well as to its parent. These links will help generate a complete path from start to goal states.
How does Bidirectional Search work?
Let us illustrate the working of this method using an existing graph. Consider the following graph as shown in Figure. Consider the graph to find a route from the 1st node that is 1 to the last element 16.
Tracing nodes in both directions simultaneously.
Implementing Bidirectional Search in Python
class adjacent_Node:
def __init__(self, v):
self.vertex = v
self.next = None
class bidirectional_Search:
def __init__(self, vertices):
self.vertices = vertices
self.graph = [None] * self.vertices
self.source_queue = list()
self.last_node_queue = list()
self.source_visited = [False] * self.vertices
self.last_node_visited = [False] * self.vertices
self.source_parent = [None] * self.vertices
self.last_node_parent = [None] * self.vertices
def AddEdge(self, source, last_node):
node = adjacent_Node(last_node)
node.next = self.graph[source]
self.graph[source] = node
node = adjacent_Node(source)
node.next = self.graph[last_node]
self.graph[last_node] = node
def breadth_fs(self, direction = 'forward'):
if direction == 'forward':
current = self.source_queue.pop(0)
connected_node = self.graph[current]
while connected_node:
vertex = connected_node.vertex
if not self.source_visited[vertex]:
self.source_queue.append(vertex)
self.source_visited[vertex] = True
self.source_parent[vertex] = current
connected_node = connected_node.next
else:
current = self.last_node_queue.pop(0)
connected_node = self.graph[current]
while connected_node:
vertex = connected_node.vertex
if not self.last_node_visited[vertex]:
self.last_node_queue.append(vertex)
self.last_node_visited[vertex] = True
self.last_node_parent[vertex] = current
connected_node = connected_node.next
def is_intersecting(self):
#
for i in range(self.vertices):
if (self.source_visited[i] and
self.last_node_visited[i]):
return i
return -1
def path_st(self, intersecting_node,
source, last_node):
path = list()
path.append(intersecting_node)
i = intersecting_node
while i != source:
path.append(self.source_parent[i])
i = self.source_parent[i]
path = path[::-1]
i = intersecting_node
while i != last_node:
path.append(self.last_node_parent[i])
i = self.last_node_parent[i]
path = list(map(str, path))
print(' '.join(path))
def bidirectional_search(self, source, last_node):
self.source_queue.append(source)
self.source_visited[source] = True
self.source_parent[source] = -1
self.last_node_queue.append(last_node)
self.last_node_visited[last_node] = True
self.last_node_parent[last_node] = -1
while self.source_queue and self.last_node_queue:
self.breadth_fs(direction = 'forward')
self.breadth_fs(direction = 'backward')
intersecting_node = self.is_intersecting()
if intersecting_node != -1:
print("Path exists between {} and {}".format(source, last_node))
print("Intersection at : {}".format(intersecting_node))
self.path_st(intersecting_node,
source, last_node)
exit(0)
return -1
if __name__ == '__main__':
n = 17
source = 1
last_node = 16
my_Graph = bidirectional_Search(n)
my_Graph.AddEdge(1, 2)
my_Graph.AddEdge(1, 3)
my_Graph.AddEdge(1, 4)
my_Graph.AddEdge(2, 5)
my_Graph.AddEdge(2, 6)
my_Graph.AddEdge(3, 7)
my_Graph.AddEdge(4, 8)
my_Graph.AddEdge(4, 9)
my_Graph.AddEdge(5, 10)
my_Graph.AddEdge(6, 10)
my_Graph.AddEdge(10, 11)
my_Graph.AddEdge(7, 11)
my_Graph.AddEdge(7, 12)
my_Graph.AddEdge(8, 13)
my_Graph.AddEdge(9, 13)
my_Graph.AddEdge(10, 6)
my_Graph.AddEdge(11, 14)
my_Graph.AddEdge(12, 15)
my_Graph.AddEdge(13, 15)
my_Graph.AddEdge(14, 16)
my_Graph.AddEdge(15, 16)
out = my_Graph.bidirectional_search(source, last_node)
if out == -1:
print("No path between {} and {}".format(source, last_node))
OUTPUT:
Path exists between 1 and 16
Intersection at: 8
1 4 8 13 15 16
Complexity of Bidirectional Search
The reason for this approach is that each of the two searches has a time complexity of O(b^d/2), and O(b^d/2+b^d/2) is much less than the running time of one search from the beginning to the goal, which would be O(b^d). This search can be made in an already existing graph/tree or a search graph/ tree can be generated as a part of the search.
Advantages
- The speed with which we receive the desired results is one of the key advantages of bidirectional searches.
- By conducting multiple searches simultaneously, the search time is significantly shortened.
- Users can also conserve resources because less memory is necessary to store all of the searches.
Disadvantages
- There is a chance of an infinite loop if the algorithm isn’t robust enough to recognise the intersection at which the search should terminate.
- A further challenge is that this algorithm’s implementation requires additional code and instructions, and each node and step should be carefully implemented in order to conduct such searches.
- Bidirectional search has a basic problem in that the user must be aware of the objective state in order to use it, thus reducing the use cases for it.
Summary
It does have some drawbacks, a bidirectional search is among the most popular and extensively researched search algorithms because it is the most effective and rapid approach to arrive at desired search results when the destination state is known before the search begins.