Scribd
Upload
15 views11 pages

Lect 2

The document discusses two search strategies: Depth-First Search (DFS) and Bi-Directional Search. DFS explores deeply using a stack, has low memory usage, but may not find the optimal path and can get stuck in infinite loops. Bi-Directional Search operates from both start and goal simultaneously, is faster for large search spaces, but is more complex to implement and requires synchronization.

Uploaded by

Anchal Shukla
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
15 views11 pages

Lect 2

The document discusses two search strategies: Depth-First Search (DFS) and Bi-Directional Search. DFS explores deeply using a stack, has low memory usage, but may not find the optimal path and can get stuck in infinite loops. Bi-Directional Search operates from both start and goal simultaneously, is faster for large search spaces, but is more complex to implement and requires synchronization.

Uploaded by

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

LECTURE: 2

Search Strategies
Depth-First Search (DFS)
• Explores deeply before backtracking.
• Uses a stack for tracking.
• Time complexity: O(V+E)
• Space complexity: O(V)
• Not guaranteed to find optimal path.
• May get stuck in infinite loops.
Algorithm of Depth-First Search (DFS)
• Create an empty stack, push root.
• While stack isn’t empty, continue process.
• Pop the top node from stack.
• Check if popped node is goal.
• If not, push unvisited neighbors.
• Repeat until goal found or stack empty.
Advantages of DFS:
• Low memory usage
• Works well with deep graphs
• Simple and easy to implement
• Efficient for cyclic graphs
• Suitable for pathfinding in mazes
• Less storage space required
Disadvantages of DFS:
• May not find shortest path
• Not guaranteed to find all solutions
• High time consumption in deep paths
• Fails in graphs with loops
• Can get stuck in infinite paths
Bi-Directional Search

• Searches from start and goal simultaneously


• Meets in the middle for efficiency
• Faster for large search spaces
• Time complexity: O(bd/2)
• Space complexity: O(bd/2)
• Eg: Google Maps, Social networks, Gaming
Algorithm of Bi-Directional Search
• Initialize two queues for searches.
• Start forward and backward searches simultaneously.
• Expand nodes from both search fronts.
• Check if nodes meet in middle.
• If paths connect, return the solution.
• Repeat until solution found or queues empty.
Advantages of Bi-Directional Search
• Reduces search space significantly.
• Faster than unidirectional search.
• Efficient for large state spaces.
• Can find optimal solutions.
• Improves search time in complex networks.
• requires less memory than traditional algorithms
Disadvantages of Bi-Directional Search
• Requires clearly defined start and goal.
• More complex to implement.
• Needs synchronization between two search fronts.
• Memory usage can be high in some cases.
• Less effective in asymmetric graphs.
• Struggles with non-uniform transition costs.
Quiz Time
• ________ is used for implementing DFS?
a) Queue
b) Stack
c) Heap
d) All of the above
NEXT: Discover Iterative Deepening Search
pros & cons of uninformed search methods

You might also like