Slide 1 — Title Slide: Search Algorithms

“Hello everyone. I am Dr. S. V. Anandhi, Associate Professor from the Department of AI

and DS at Ramco Institute of Technology.
Today I will be presenting a detailed session on Search Algorithms, which form the
foundation for problem solving in Artificial [Link] is used to
understand their behavior, and analyze their strengths and limitations.
Let’s begin.”

Slide 2- This slide shows the classification of search algorithms in AI.

Search algorithms are divided into two main types: Uninformed (Blind) Search and
Informed Search.

Uninformed Search does not use any extra information about the goal. It explores the search
space blindly.
Examples include:

 Breadth-First Search – explores level by level

 Uniform Cost Search – picks the lowest-cost path
 Depth-First Search – goes deep into one branch
 Depth-Limited Search – DFS with a depth limit
 Iterative Deepening DFS – repeated DFS with increasing depth
 Bidirectional Search – searches from start and goal simultaneously

On the other hand, Informed Search uses heuristics, meaning additional knowledge to guide
the search.
Main examples are:

 Best-First Search – chooses the most promising node

 A* Search – combines path cost and heuristic to find optimal solutions

So in simple terms:
Uninformed search = no extra knowledge, blind exploration.
Informed search = guided search using heuristics.”

Slide 3 — Uninformed vs Informed Search

“In AI, search algorithms are generally divided into two main types: Uninformed search and
Informed search.
Uninformed search, also known as blind search, does not use any domain knowledge beyond
the problem definition.
Informed search, on the other hand, uses heuristics or additional information to guide the
search process more efficiently.
In this session, our focus will primarily be on uninformed search strategies, and we will
compare them at the end.”
Slide 4 — Search Data Structures
“To understand search algorithms, it is important to know the underlying data structures.
Queues are used for Breadth-First Search because they follow the FIFO principle — First In,
First Out.
Stacks are used for Depth-First Search because they follow LIFO — Last In, First Out.
The basic operations we use include isEmpty, pop, top, and add.
These operations determine how nodes are expanded during the search.”

Slide 5-6 — Breadth First Search

“Breadth-First Search, commonly called BFS, explores nodes level by level starting from the
root.
This algorithm is especially useful when all actions have the same cost.
BFS is implemented using a queue, ensuring that the shallowest unexpanded node is always
selected next.”

Slide 7-
“This slide explains two basic terms used in graph traversal: visiting and exploring.

On the left side, we see visiting a node.

Visiting simply means selecting or reaching a particular node—for example, starting at node
a. We are only marking the node, not moving to its neighbors yet.

On the right side, we see exploring a node.

Exploring means we not only visit the node but also check all its adjacent or connected
nodes.
For example, after visiting a, exploring it means we look at its neighbors like b and d.

So in short:

 Visiting = selecting a node.

 Exploring = checking all the neighboring nodes connected to it.”

Slide 8-10 — Breadth First Search (Explanation)

“Here are the key steps in Breadth-First Search:
Step 1: Start with an empty queue.
Step 2: Insert the starting node.
Step 3: While the queue is not empty, remove the front node, explore it, and add all its
children.
The search continues until the goal is reached or there are no more nodes to explore.”
Slide 11
“In BFS, the search expands outward layer by layer.
It examines all nodes at depth one before moving to depth two, and continues this way.
This guarantees that if a solution exists at any level, BFS will find the one with the minimum
number of steps.” “This slide visually demonstrates how nodes are expanded in BFS.
You can observe that all immediate children of the root are expanded first, followed by their
children.
The tree grows level by level.”

Slide 12 — BFS Advantages & Disadvantages

“Advantages:
• BFS guarantees finding a solution if one exists.
• If multiple solutions exist, BFS returns the one with the fewest steps.

Disadvantages:
• It requires large memory to store nodes at each level.
• If the solution is deep, BFS takes significant time and space.”

Slide 13-14 — Uniform Cost Search

“Uniform Cost Search, or UCS, is commonly used when each edge in the graph has a
different cost.
UCS does not look for the shallowest node — instead, it always expands the least-cost path.
It uses a priority queue, where the node with the minimum cumulative cost is expanded
first.”

Slide 14 — Uniform Cost Search (Explanation)

“The main aim of UCS is to find the path to the goal with the lowest total cost.
Each time a node is expanded, its path cost is evaluated.
The algorithm proceeds based on increasing cost values, ensuring that cheaper paths are
explored earlier.”

Slide 15 — UCS Advantages & Disadvantages

“Advantages:
• UCS is guaranteed to be optimal because it always selects the least-cost path.
Disadvantages:
• It may ignore the number of steps and focus only on path cost.
• It may get stuck in exploring long low-cost paths.”

Slide 16-17 — Depth First Search

“Depth-First Search, or DFS, expands the deepest unexpanded node first.
It goes as far down a branch as possible before backtracking.
DFS uses a stack structure, which allows the most recently discovered node to be explored
next.
Compared to BFS, DFS uses much less memory.”

Slide 18-25 — DFS Problem

“This slide shows a typical DFS scenario.
You can see how the DFS algorithm quickly moves deep into the graph, but may miss
shallower solutions because it prioritizes depth over breadth.”

Slide 26-27 — Another DFS Example

“Here you can see another example where DFS reaches a goal node that lies deep in the
graph.
This example highlights both the strength and the potential drawback of DFS — it may find a
deep solution quickly or waste time exploring a wrong deep path.”

Slide 28 — DFS Advantages & Disadvantages

“Advantages:
• DFS uses very little memory.
• It may reach a goal faster than BFS if the solution lies deep in the correct path.

Disadvantages:
• DFS may re-explore states many times.
• There is no guarantee of completeness or optimality.
• DFS may also fall into infinite loops.”

Slide 29-33 — Depth Limited Search

“Depth-Limited Search is a variant of DFS where a depth limit is imposed.
Nodes deeper than the limit are treated as if they have no children.
This prevents the search from going indefinitely into deep or infinite branches.”

Slide 34 — Failure conditions of DLS

“There are two failure conditions in Depth-Limited Search:
• Standard failure — there is no solution in the tree.
• Cutoff failure — the limit was too small, so the search ended prematurely.
Cutoff indicates that increasing the limit may help reach a solution.”

Slide 35— DLS Advantages & Disadvantages

“Depth-Limited Search is memory-efficient and reduces the risk of infinite loops.
However, if the depth limit is set incorrectly, the search may miss the solution entirely.
Thus, DLS is not always complete.”

Slide 36-37— Iterative Deepening DFS

“Iterative Deepening Depth-First Search, or IDDFS, combines the best features of BFS and
DFS.
IDDFS repeatedly runs Depth-Limited Search with increasing limits: 0, 1, 2, and so on.
This allows it to find the shallowest solution like BFS, while using memory close to DFS.”

Slide 38 — IDDFS Continued

“In IDDFS, nodes at the deepest level are expanded once, while nodes near the top may be
expanded multiple times.
Although repeated work occurs, the bulk of search happens at the deepest level, making the
method efficient in practice.”

Slide 39 — DFS vs BFS Traversal

“This slide visually compares how DFS and BFS traverse the graph.
BFS expands nodes level by level, while DFS expands nodes depth by depth.
This comparison is essential to understand why IDDFS combines both strategies.”
Slide 40 — IDDFS Problem Example
“This slide shows a problem example where IDDFS gradually increases the depth limit,
eventually reaching the goal node.
Each iteration explores deeper levels but maintains the memory advantage of DFS.”

Slide 41 — IDDFS Advantages & Disadvantages

“Advantages:
• Combines the minimal memory usage of DFS and completeness of BFS.
• Efficient for large search spaces with unknown depth.

Disadvantages:
• Repeated expansion of upper-level nodes increases computation time.”

Slide 42-43 — Bidirectional Search Algorithm

“Bidirectional Search starts from two directions:
One search begins at the start node and another begins at the goal node.
The search stops when the two search frontiers meet.
This dramatically reduces the search space, because instead of exploring bᵈ nodes, it explores
roughly 2 × b^(d/2).”

Slide 44-45 — Bidirectional Search Illustration

“In this example, the forward search begins at node 1, and the backward search begins at
node 16.
Both searches meet at node 9.
This point of intersection gives us the solution path with far fewer node expansions.”

Slide 46— Bidirectional Search: Pros & Cons

“Advantages:
• Much faster than unidirectional search.
• Requires less memory.
Disadvantages:
• Hard to implement.
• Requires knowing the goal state clearly.
• Backward actions may not always be defined.”

Slide 47 — Comparison of Uninformed Search Algorithms

“This final comparison slide summarizes all uninformed search strategies: BFS, DFS, UCS,
DLS, IDDFS, and Bidirectional Search.
We compare them based on:
• Completeness
• Optimality
• Time complexity
• Space complexity
Understanding these helps choose the right algorithm for different AI problems.”

Slide 48 — Thank You

“Thank you for listening to this presentation on Search Algorithms in AI.
I hope this session gave you a clear understanding of how different search strategies work
and when to use them.
Feel free to ask questions or request more examples. Thank you.”