Scribd
Upload
107 views3 pages

AI Lect 09 Bidirectional Search

Bidirectional Search is an AI algorithm that simultaneously explores paths from both the initial and goal states to find the shortest path, significantly reducing search space and time complexity. It involves two searches: a forward search from the start node and a backward search from the goal node, meeting at a common node to reconstruct the solution. While it offers advantages like faster search and less memory usage, it can be complex to implement and requires knowledge of the goal state.

Uploaded by

anmol198395 anmol198395
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
107 views3 pages

AI Lect 09 Bidirectional Search

Bidirectional Search is an AI algorithm that simultaneously explores paths from both the initial and goal states to find the shortest path, significantly reducing search space and time complexity. It involves two searches: a forward search from the start node and a backward search from the goal node, meeting at a common node to reconstruct the solution. While it offers advantages like faster search and less memory usage, it can be complex to implement and requires knowledge of the goal state.

Uploaded by

anmol198395 anmol198395
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

Bidirectional Search in AI

Bidirectional Search is a search algorithm used in Artificial Intelligence (AI) to find the shortest
path between an initial state (start node) and a goal state (goal node). Unlike traditional search
algorithms that explore the search space in one direction, bidirectional search works by running
two simultaneous searches:

1. Forward Search: Starts from the initial state and moves towards the goal.
2. Backward Search: Starts from the goal state and moves towards the initial state.

The search stops when the two searches meet in the middle, significantly reducing the search
space and time complexity.

How It Works

1. Begin two searches: one from the start node and one from the goal node.
2. Expand nodes alternately in both directions.
3. When the two searches meet at a common node, a path is found.
4. The solution is reconstructed by combining the forward and backward paths.

Example Using a Simple Tree

Let's say we have a tree like this:

A
/ \
B C
/ \ \
D E F
/ \
G H

We want to find the shortest path from A to G.

How the Bidirectional Search Works

We will search from A (Start Node) and G (Goal Node) at the same time.

Step 1: Start Search in Both Directions

 Forward Search from A: Expand A → Finds B and C.


 Backward Search from G: Expand G → Finds E.

Step 2: Continue Expanding

 Forward Search from B: Expand B → Finds D and E.


 Backward Search from E: Expand E → Finds B.

Step 3: Searches Meet

 The two searches meet at node B.


 The shortest path is A → B → E → G.

Advantages of Bidirectional Search

✅ Faster than Unidirectional Search: Reduces the number of nodes explored compared to
algorithms like BFS or DFS.
✅ Less Memory Usage: Stores fewer states, making it efficient in memory.
✅ Efficient in Large Graphs: Useful when the branching factor is high.

Disadvantages of Bidirectional Search

❌ Difficult to Implement: Requires a way to efficiently check when two searches meet.
❌ Requires Knowledge of Goal State: Not always possible in dynamic environments.
❌ Extra Overhead: Managing two search processes simultaneously can be complex.

Applications of Bidirectional Search

 Pathfinding in Graphs (e.g., GPS Navigation, Google Maps)


 Artificial Intelligence (e.g., solving puzzles like Rubik’s Cube)
 Networking and Routing (e.g., finding shortest paths in computer networks)

Why Bidirectional Search is Efficient?

 Instead of exploring all nodes from A or G separately, we reduce the search space by
working from both directions.
 This results in fewer steps than a standard BFS or DFS.

You might also like