What is Bidirectional search?
Bidirectional search is a strategy used in computer algorithms to find the shortest path between two points in a network or graph. It's like having two people searching for each other in a maze.
Imagine you and your friend are in a big maze, and you're both trying to find each other as quickly as possible. Instead of searching separately and hoping to meet in the middle, you decide to use bidirectional search.
In bidirectional search, you and your friend start from your respective positions and begin exploring the maze. You both move simultaneously, but in opposite directions. You explore the maze from two different starting points, searching for each other.
As you and your friend explore, you leave breadcrumbs (or marks) to remember the path you've taken. This helps you avoid retracing your steps and ensures you don't get lost. You keep moving until you meet in the middle, where both of your paths intersect. This means you have successfully found the shortest path between your starting positions.
By using bidirectional search, you can potentially find each other faster because you're exploring the maze from two directions at once, reducing the overall search space and increasing your chances of finding the shortest path.
In computer algorithms, bidirectional search is often used to optimize pathfinding algorithms by searching from both the start and the goal simultaneously. It can be more efficient than traditional search methods that explore the entire graph or network from a single starting point.
Who invented it?
The idea of bidirectional search can be traced back to the mid-1960s when researchers began exploring techniques to improve the efficiency of search algorithms. Early work on bidirectional search was done by Nils Nilsson in his 1969 book "Problem-Solving Methods in Artificial Intelligence."
Since then, numerous researchers and scientists have contributed to the development and refinement of bidirectional search algorithms. It has become a widely used technique in various domains, such as artificial intelligence, computer graphics, and network routing.
Since then, numerous researchers and scientists have contributed to the development and refinement of bidirectional search algorithms. It has become a widely used technique in various domains, such as artificial intelligence, computer graphics, and network routing.
Pseudocode
function bidirectionalSearch(graph, startNode, goalNode):
// Initialize forward and backward search queues
forwardQueue = Queue()
backwardQueue = Queue()
// Initialize visited sets for forward and backward searches
forwardVisited = Set()
backwardVisited = Set()
// Initialize parent dictionaries for forward and backward searches
forwardParent = {}
backwardParent = {}
// Add start and goal nodes to their respective queues and visited sets
forwardQueue.enqueue(startNode)
forwardVisited.add(startNode)
forwardParent[startNode] = None
backwardQueue.enqueue(goalNode)
backwardVisited.add(goalNode)
backwardParent[goalNode] = None
while not forwardQueue.isEmpty() and not backwardQueue.isEmpty():
// Perform forward search expansion
currentForward = forwardQueue.dequeue()
neighborsForward = graph.getNeighbors(currentForward)
for neighbor in neighborsForward:
if neighbor not in forwardVisited:
forwardVisited.add(neighbor)
forwardParent[neighbor] = currentForward
forwardQueue.enqueue(neighbor)
if neighbor in backwardVisited:
// Intersection point found; path is found
return constructPath(forwardParent, backwardParent, neighbor)
// Perform backward search expansion
currentBackward = backwardQueue.dequeue()
neighborsBackward = graph.getNeighbors(currentBackward)
for neighbor in neighborsBackward:
if neighbor not in backwardVisited:
backwardVisited.add(neighbor)
backwardParent[neighbor] = currentBackward
backwardQueue.enqueue(neighbor)
if neighbor in forwardVisited:
// Intersection point found; path is found
return constructPath(forwardParent, backwardParent, neighbor)
// No path found
return null
function constructPath(forwardParent, backwardParent, intersectionNode):
// Constructs the final path by traversing the parent pointers
path = []
// Add nodes from the start to the intersection point
currentNode = intersectionNode
while currentNode is not None:
path.append(currentNode)
currentNode = forwardParent[currentNode]
// Reverse and append nodes from the intersection point to the goal
currentNode = backwardParent[intersectionNode]
while currentNode is not None:
path.insert(0, currentNode)
currentNode = backwardParent[currentNode]
return path
1. The `bidirectionalSearch` function takes a graph, a start node, and a goal node as input and returns the shortest path between them.
2. Two queues (`forwardQueue` and `backwardQueue`) are initialized to perform the forward and backward searches, respectively.
3. Two visited sets (`forwardVisited` and `backwardVisited`) are initialized to keep track of visited nodes during the forward and backward searches.
4. Two parent dictionaries (`forwardParent` and `backwardParent`) are initialized to store the parent-child relationships of nodes discovered during the searches.
5. The start node is enqueued into `forwardQueue`, marked as visited in `forwardVisited`, and assigned as the root node in `forwardParent`.
6. The goal node is enqueued into `backwardQueue`, marked as visited in `backwardVisited`, and assigned as the root node in `backwardParent`.
7. The main loop runs as long as both `forwardQueue` and `backwardQueue` are not empty.
8. Inside the loop, the algorithm performs the forward search expansion. The current node is dequeued from `forwardQueue`, and its neighbors are retrieved from the graph.
9. For each unvisited neighbor, the neighbor is marked as visited, the parent-child relationship is recorded in `forwardParent`, and the neighbor is enqueued into `forwardQueue`.
10. If a neighbor is already visited in the backward search (`neighbor in backwardVisited`), it means an intersection point has been found. In this case, the `constructPath` function is called to construct and return the final path.
11. After the forward search expansion, the algorithm performs the backward search expansion in a similar manner.
12. If a neighbor is already visited in the forward search (`neighbor in forwardVisited`), an intersection point has been found, and the `constructPath` function is called to construct and return the final path.
13. If the main loop completes without finding an intersection point, it means there is no path between the start and goal nodes, and `null` is returned.
14. The `constructPath` function constructs the final path by traversing the parent pointers from the intersection point to the start node and from the intersection point to the goal node.
15. The constructed path is returned as the shortest path between the start and goal nodes.
Time and Space Complexity
In the worst case, bidirectional search may need to explore a significant portion of the graph or network from both the start and goal simultaneously. This means that the algorithm may have to traverse a large number of nodes, resulting in a higher time complexity.
Specifically, if we denote the number of nodes in the graph or network as "N" and the branching factor (average number of outgoing edges from each node) as "B," then the worst case time complexity of bidirectional search can be approximated as O(B^(N/2)). This is because both the forward and backward searches can potentially explore up to B^(N/2) nodes.
Similarly, the space complexity of bidirectional search in the worst case can be approximated as O(B^(N/2)), as it needs to store information for both the forward and backward searches.
Specifically, if we denote the number of nodes in the graph or network as "N" and the branching factor (average number of outgoing edges from each node) as "B," then the worst case time complexity of bidirectional search can be approximated as O(B^(N/2)). This is because both the forward and backward searches can potentially explore up to B^(N/2) nodes.
Similarly, the space complexity of bidirectional search in the worst case can be approximated as O(B^(N/2)), as it needs to store information for both the forward and backward searches.
Advantages
1. Reduced Search Space: By simultaneously exploring from both the start and goal nodes, bidirectional search can significantly reduce the search space. This can lead to faster search times, especially when the start and goal nodes are closer to each other.
2. Improved Efficiency: Compared to traditional search algorithms that explore the entire graph or network from a single starting point, bidirectional search can be more efficient. It divides the search effort between two directions, potentially reaching the goal faster.
3. Potential for Early Termination: Bidirectional search has the advantage of potentially terminating early when the forward and backward searches meet in the middle. This means that if the start and goal nodes are close, the algorithm can find the solution more quickly.
2. Improved Efficiency: Compared to traditional search algorithms that explore the entire graph or network from a single starting point, bidirectional search can be more efficient. It divides the search effort between two directions, potentially reaching the goal faster.
3. Potential for Early Termination: Bidirectional search has the advantage of potentially terminating early when the forward and backward searches meet in the middle. This means that if the start and goal nodes are close, the algorithm can find the solution more quickly.
Disadvantages
1. Increased Memory Usage: Bidirectional search requires storing information for both the forward and backward searches. As a result, it typically uses more memory compared to traditional search algorithms that explore from a single starting point. However, the total space required is often less than twice the space needed for a single-direction search.
2. Additional Overhead: Implementing bidirectional search involves managing two separate searches and coordinating their efforts. This coordination introduces additional complexity and overhead in terms of algorithm design and implementation.
3. Problem Suitability: Bidirectional search is most effective in problems where the search space is well-defined, and there is a clear notion of a goal or target. It may not be suitable for all types of problems or graphs, especially those without a defined goal state or where the graph structure is not conducive to bidirectional exploration.