ELE335 (Artificial Intelligence)

BIDIRECTIONAL
SEARCH
Presented by:

Ahmed Ragab Abdelrhamn Waheed

Shams Hisham Abdelrhman Mamdouh

Aya Mohamed
 Outline 1

1 What is Bidirectional Search

2 Types of Bidirectional Search

3 Uninformed Bidirectional

4 Informed Bidirectional

5 Example Problem
What is Bidirectional Search? 2

Bidirectional Search is a graph search algorithm that finds the shortest

path between start and goal by searching forward from the start and
backward from the goal at the same time.
The search stops when both directions meet at a common point between Example
them .
The final path is built by combining both halves.
This method greatly reduces the search space compared to one-
directional search.
Used in
GPS
Network routing
Robotics
Types of Bidirectional Search 3

Uninformed Informed

Without heuristic functions, nodes are Enhancing efficiency using heuristic

expanded using the basic approaches functions through three distinct approaches

Front-to-front

Breadth-first-search BFS Front-to-back

Depth-first-search DFS Perimeter search

Uniform-cost-search UCS
Uninformed Bidirectional (1) 4

Implementing the basic search algorithms, specially BFS,

from both ends start and goal states.

For each search, a frontier is explored at each step. The

Charactertiques process lasts until an intersection is found.

The algorithm optimizes performance by minimizing the

state space and reducing search time
Uninformed Bidirectional (2) 5

Evaluation

Completness
When implemented correctly, it guarantees reaching the goal, as demonstrated by algorithms like BFS
and UCS

Optimalality
It finds the shortest path if edge costs are equal using (BFS) or handled correctly using (UCS)

Time Complexity
Each search (forward and backward) is exploring only half of the state space reducing the time complexity to
[O(b ^ (d/2)]

Space Complexity
Since there are two frontiers, for the forward and backward searches, space complexity will also be [O(b ^
(d/2)]
Uninformed Bidirectional (3) 6

Advantages compared to informed

Used for simple and simple domain with

general purpose solutions uniform costs and with
with guaranteed no heuristic function is
correctness. needed
Uninformed Bidirectional (4) 7

Disadvantages compared to informed

Informed approaches are

Explores all paths
best suited in large and
wasting time on
structured problems.
irrelevant branches.
informed Bidirectional (1) 8

Searching from both ends implementing a heuristic

function to find the shortest path.

At each step, both the forward and the backward

Charactertiques searches expand the node with the min h(n)

Evaluating h(n) is based on three distinct approaches

front-to-back, front-to-front, and perimeter.
informed Bidirectional (2) 9

Front-to-back approach

The most intuaitive and straightforward approach.

In the forward search, h(n) estimates the cost from the current state to the goal state.

In the backward search, h(n) estimates the cost from the current state to the start state.

Forward estimation f(n) = g(n) + h(n, goal)

Backward estimation f(n) = g(n) + h(n, start)

informed Bidirectional (3) 10

Advantages Front-to-back approach

Is is straight-forward and Works will if heuristics of

simple to implement than both start and goal states
other approahes. are defind accurately.
informed Bidirectional (4) 11

Disadvantages Front-to-back approach

May waste time

Each search does not
exploring unnecessary
adapt to whatever the
paths.
other is doing
informed Bidirectional (5) 12

Front-to-front approach

More intelligent approach.

Both searches try to meet each other.

For ex, if the forward search is exploring the area A1, the backward will target that area.

h(n) = min(estimation(n, m)) where m in backward

Forward estimation
frontier

h(n) = min(estimation(n, m)) where m in forward

Backward estimation
frontier
informed Bidirectional (6) 13

Advantages Front-to-front approach

Improves focus and Powerful in large state

reduces wasted spaces like puzzles.
exploration.
informed Bidirectional (7) 14

Disadvantages Front-to-front approach

Need to constantly
More complex to
update and compare
implement
both frontiers
informed Bidirectional (8) 15

Perimeter approach

A little different approach.

One search usually proceeds till finding a perimeter is found.

not a common one.

In the perimeter approach, one of the searches expands until it reaches a predefined boundary or

region—known as the perimeter. Then, the other search proceeds toward that region, using heuristics

(h(n)) calculated based on the estimated cost to reach this perimeter area.
informed Bidirectional (9) 16

Advantages Perimeter approach

The forward perimeter

Useful if the goal area avoids deep
is more complicated or commitment before the
costly to search backward search
confirms a valid path
informed Bidirectional (10) 17

Disadvantages Perimeter approach

Needs good choice of Not widely used or

perimeter depth standardized like the

others
 informed Bidirectional (11) 18

Use Cases of each approach

Charactertiques

Front-to-back Front-to-front Perimeter

Problems with well-defind endpoints Puzzles and combinatorial problems Problems where middle ground or
with symmetrical properties hubs are natural meeting areas
GPS Navigation
Robot path-planning Puzzles Large-scale map
routing
informed Bidirectional (12) 19

Advantages compared to uninformed

Considering complexity,
Can reach intersection Informed can outperform in
Often achieves less than
point faster and with less cost-based or large-state-
O(b^(d/2)) depending
space. space problems.
on the heuristic quality
Example Problem (1) 20

We will examine an example problem using the BFS algorithm.

Start state → 0

Goal State → 14
Example Problem (2) 21

Having 7 levels from 0 to 6

We divide the path into two equivalent paths

First Path from 0 to 3.

Second Path from 3 to 6

Example Problem (3) 22
Example Problem (4) 23
Example Problem (5) 24
Example Problem (6) 25
Bidirectional Search Function: 26

This function performs bidirectional search on the

given graph.
It initializes two queues and visited dictionaries
for both the start and goal nodes.
The search proceeds from both ends
simultaneously, checking for overlapping nodes
between the two searches.
When an overlap occurs, it triggers the
reconstruction of the path from both directions.
Reconstruct Path Function: 27

This function reconstructs the shortest path once the

two searches meet.
It traces the path from the meeting node back to
the start node and from the meeting node to the
goal node.
The paths are then merged to create the final
shortest path.
Citations 28

Wikipedia - Bidirectional Search

GeeksForGeeks - Bidirectional Search

 ELE335 (Artificial Intelligence)

TEAM MEMBERS
Presented by:

Ahmed Ragab Abdelrhamn Waheed

Shams Hisham Abdelrhman Mamdouh

Aya Mohamed

Directed by Dr. Mohamed Rehan