Scribd
Upload
15 views11 pages

Unit 2 LECT 2

The document discusses two search strategies: Depth-First Search (DFS) and Bi-Directional Search. DFS explores deeply using a stack but may not find the optimal path and can get stuck in infinite loops, while Bi-Directional Search operates from both the start and goal simultaneously for efficiency, though it is more complex to implement. Each method has its advantages and disadvantages in terms of memory usage, time complexity, and effectiveness in various scenarios.

Uploaded by

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

Unit 2 LECT 2

The document discusses two search strategies: Depth-First Search (DFS) and Bi-Directional Search. DFS explores deeply using a stack but may not find the optimal path and can get stuck in infinite loops, while Bi-Directional Search operates from both the start and goal simultaneously for efficiency, though it is more complex to implement. Each method has its advantages and disadvantages in terms of memory usage, time complexity, and effectiveness in various scenarios.

Uploaded by

ky0307005
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as 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