BDS602-Ai & Ml

Module 2: Problem Solving by Searching

Q1: Discuss the five components of a well-defined
problem using the 8-puzzle as an example.
Ans:
Introduction:
In Artificial Intelligence, formulating a problem clearly is the first step in designing
a problem-solving agent. A well-defined problem consists of five essential
components that help simplify the search for a solution. We will explain these
components using the classic 8-puzzle problem as an example.

Five Components of a Well-Defined Problem

Initial State:
This is the starting point of the problem.
Example: For the 8-puzzle, it is the current arrangement of tiles on the board.
Real-world example: Starting point of a maze where a robot begins its
navigation.
Actions (Available Moves):

BDS602-Ai & Ml 1
 These are the operations the agent can perform from any state.
Example: In 8-puzzle, actions are sliding the blank space Up, Down, Left, or
Right to swap with an adjacent tile (if possible).
Real-world example: Turning left or right, moving forward or backward while
driving.
Transition Model:
This defines the result of applying an action to a state (i.e., the next state).
Example: If the blank space moves left, the tiles swap accordingly to create a
new configuration.
Real-world example: Pressing a button on a remote changes the TV channel to
the next or previous one.
Goal Test:
A function or condition that checks if a state meets the goal criteria.
Example: For the 8-puzzle, the goal test checks if the tiles are in the correct
order from 1 to 8, with the blank at the last position as shown in the diagram
above.
Real-world example: A robot reaching the exit point of a maze.
Path Cost (Step Cost):
Assigns a numeric value (cost) to each path or action taken. The agent tries to
minimize this cost.
Example: Each move of a tile counts as 1 step, so the total path cost is the
number of moves made to reach the goal.
Real-world example: The distance traveled by a delivery vehicle, where
shorter routes cost less fuel and time.

Q2: Write an algorithm for Breadth-First Search (BFS)

and explain with an example.
Ans:

BDS602-Ai & Ml 2
 Introduction:
Breadth-First Search (BFS) is a fundamental uninformed search algorithm used in
Artificial Intelligence for traversing or searching tree or graph data structures. It
explores all nodes at the current depth before moving on to nodes at the next
depth level, ensuring the shortest path in terms of number of edges.

Breadth-First Search (BFS) Algorithm

Algorithm Steps:
1. Initialize: Create a queue (FIFO) and enqueue the start node (initial state).
Also, create a set to keep track of explored nodes to avoid revisits.
2. While the queue is not empty, do the following:
Dequeue the first node from the queue and call it current_node.
If current_node is the goal, stop and return the solution (path).
Else, expand current_node to get its neighboring nodes (children).
For each neighbor:
If the neighbor has not been visited or enqueued, enqueue it.
3. Repeat until the goal is found or the queue is empty (meaning no solution).
Pseudo-code:

BFS(start_node, goal_test):

Initialize queue Q
Enqueue start_node onto Q
Initialize explored set as empty

BDS602-Ai & Ml 3
 while Q is not empty:
current_node = Dequeue(Q)
if goal_test(current_node):
return solution_path(current_node)
[Link](current_node)
for each child in expand(current_node):
if child not in explored and child not in Q:
Enqueue(child, Q)
return failure // goal not found

Example (Real-world and AI Problem):

Real-world example: Imagine you are in a building and want to find the shortest
route to the exit by exploring all rooms on the current floor first before moving to
the next floor.
AI example (using the graph above): Starting at node A, BFS visits nodes level
by level:
Start: Queue = [A]
Visit A: Enqueue its neighbors B, C, D → Queue = [B, C, D]
Visit B: Enqueue E → Queue = [C, D, E]
Visit C: No new neighbors → Queue = [D, E]
Visit D: Enqueue F → Queue = [E, F]
Visit E: No new neighbors → Queue = [F]
Visit F: Goal found or no more nodes.
Key Points:
BFS finds the shortest path in terms of number of edges when all step costs
are equal.
It uses a queue to keep track of nodes to explore next.
Space complexity is high (can grow exponentially with depth) but guarantees
completeness and optimality for unweighted graphs.

BDS602-Ai & Ml 4
 Useful for tasks like shortest path in maps, friends suggestions in social
networks, etc.

Q3: Explain the A* search algorithm to minimize the

total estimated cost.
Ans:
Introduction:
A* (A-star) search is a popular informed search algorithm used in Artificial
Intelligence to find the least-cost path from the start node to a goal node. It uses
both the actual cost to reach a node and a heuristic estimate of the cost from that
node to the goal, efficiently guiding the search towards the target.

BDS602-Ai & Ml 5
 A* Search Algorithm to Minimize Total Estimated Cost
Key Concepts:

BDS602-Ai & Ml 6
 g(n): Actual cost from the start node to the current node n.
h(n): Heuristic estimate of the cheapest cost from n to the goal node.
f(n): Total estimated cost of the cheapest solution through node n, calculated
as:
f(n)=g(n)+h(n)
Algorithm Steps:
1. Initialize:
Put the start node into the frontier priority queue with f-value = h(start).
Maintain an explored set to avoid revisiting nodes.
2. Loop:
Remove the node n with the lowest f(n) from the frontier.
If n is the goal, return the solution path.
Otherwise, expand n and add its successors to the frontier if they are not
already explored or if a cheaper path to them is found.
Update g, h, and f values for successors accordingly.
Properties:
Completeness: A* will find a solution if one exists (when the heuristic is
admissible).
Optimality: A* finds the least-cost path when the heuristic is admissible (never
overestimates) and consistent (monotone).
Efficiency: Guides search smartly to reduce the number of nodes expanded
compared to uninformed search.
Example (Real-world):
Navigation app: Suppose you want to find the quickest route from home (A) to
your office (Goal).
g(n): actual time taken so far (e.g., driving time from home to a certain
intersection).
h(n): estimated time remaining (straight-line distance converted to time).

BDS602-Ai & Ml 7
 A* efficiently finds the fastest route by balancing actual time spent with
estimated time remaining.

Q4: Discuss in detail the infrastructure for a search

algorithm.
Introduction:
A search algorithm systematically explores a problem’s state space to find a path
from an initial state to a goal state. To efficiently manage this process, a search
algorithm relies on a well-defined infrastructure, which organizes, tracks, and
evaluates each state examined during the search.

Infrastructure for a Search Algorithm

1. Search Tree Node:
Each node represents a particular state in the problem’s state space.
Contains four important components:
[Link]: The specific state this node represents (e.g., the current
configuration of a puzzle, or location on a map).
[Link]: The node from which this node was generated, which helps to
reconstruct the path once the goal is found.
[Link]: The action applied to the parent to get to the current node (e.g.,
move left, move to next city).

BDS602-Ai & Ml 8
 [Link]-COST (g(n)): The total cost from the initial state to this node, often the
sum of the costs of all actions taken.
Example:
In a maze-solving robot, a node’s state could be the robot’s position, the parent is
the previous position, the action might be "move north", and the path cost is the
total distance traveled so far.
1. Frontier (Open List):
A data structure (often a queue or priority queue) holding all nodes generated
but not yet expanded.
Decides the order in which nodes are explored.
Different search algorithms (like BFS, DFS, A*) manipulate this structure
differently.
Example:
In navigation, frontier represents possible next intersections to explore.
2. Explored Set (Closed List):
Keeps track of already visited states to avoid repeated exploration.
Prevents infinite loops and reduces redundant work in graph search problems.
Example:
In pathfinding, this avoids revisiting the same street intersections endlessly.
3. Path Recovery:
Once the goal node is found, the solution path is reconstructed by following
parent pointers backwards from the goal to the start node.

Q5: What is an admissible heuristic? Explain with an

example and its impact on A*.
Ans:
Introduction:
In heuristic search algorithms like A*, an admissible heuristic plays a crucial role
in guiding the search efficiently while ensuring optimality. An admissible heuristic

BDS602-Ai & Ml 9
 is an estimate of the cost from a given state to the goal that never overestimates
the true cost.
What is an Admissible Heuristic?
Definition:
An admissible heuristic h(n) for any node n is a function that satisfies:
h(n) ≤ h∗(n)
where h∗(n) is the actual lowest cost from node n to the goal.
In other words, it never overestimates the true cost to reach the goal.
Why important?
This property guarantees that the heuristic is optimistic and ensures that A*
search will find the optimal (least-cost) solution.
Example of an Admissible Heuristic
Real-world example: Straight-Line Distance (SLD) in Pathfinding In a map-
navigation problem (like finding the shortest route from one city to another), a
common heuristic is the straight-line distance (also called "as the crow flies")
between the current city and the goal city.
Explanation:
The straight-line distance is always less than or equal to the true road distance
because roads rarely go in a perfect straight line. So, it never overestimates
the actual travel cost.
Impact of Admissible Heuristic on A* Search
Optimality:
A* using an admissible heuristic is guaranteed to find the least-cost path to
the goal in a tree search. This means the solution will be the best possible.
Efficiency:
It helps A* focus the search towards promising paths and avoid exploring
unnecessary nodes, often leading to faster search compared to uninformed
methods.
Figure reference:
For example, when searching for a route to Bucharest (Romania map problem),

BDS602-Ai & Ml 10
 A* with straight-line distance only expands nodes that potentially lead to the
shortest route, pruning longer paths.

BDS602-Ai & Ml 11
 Q6: Explain the Greedy Best-First Search algorithm
and its limitations.
Ans:
Introduction:
Greedy Best-First Search is an informed search algorithm that uses heuristic
information to guide the search towards the goal. It always expands the node that
appears to be closest to the goal, hoping to find a solution quickly.

Greedy Best-First Search Algorithm

Definition:
Greedy Best-First Search selects the next node to expand based on the
heuristic function h(n) only, where:
f(n) = h(n)
This means it picks the node that seems closest to the goal, ignoring the cost
already spent.
How it works:

BDS602-Ai & Ml 12
 Initialize the frontier with the start node.
Loop until the goal is found or frontier is empty:
Pick the node with the lowest heuristic value h(n).
Expand this node and add its children to the frontier.
Goal:
To quickly find a path to the goal by being "greedy" – always trying to get closer
according to heuristic estimates.
Example of Greedy Best-First Search
Real-world example: Road map navigation Suppose we want to find a route
from Arad to Bucharest in Romania. The heuristic, called straight-line distance
(SLD), estimates how far a city is from Bucharest.
Initially, from Arad, expand the city that looks closest to Bucharest (lowest
SLD), say Sibiu.
Then expand Sibiu’s neighbor with the lowest SLD, say Fagaras.
Finally, from Fagaras, expand Bucharest which is the goal.
This way, the search quickly reaches Bucharest without exploring nodes that look
far from the goal.
Limitations of Greedy Best-First Search
Not optimal:
Since it only considers the heuristic and ignores the path cost so far, it might
find paths that are longer than the shortest possible. For example, it might not
pick the shortest route but the one that looks nearest step-by-step.
Incomplete in some cases:
It can get stuck in loops or dead ends if the heuristic misleads it. For example,
when trying to go from Iasi to Fagaras, it might keep revisiting nodes if the
heuristic values don't correctly represent the true costs.
High memory usage:
It stores all generated nodes in memory which can cause problems in large or
infinite state spaces.

BDS602-Ai & Ml 13
 Example of limitation:
If a dead-end node looks closer to the goal by the heuristic, the algorithm may
waste time exploring it and fail to find a path that initially moves away but
leads to the goal.

Q7: Describe Depth-First Search (DFS) and compare it

with BFS.
Ans:
Introduction:
Depth-First Search (DFS) and Breadth-First Search (BFS) are fundamental
uninformed search algorithms used to explore or traverse state spaces or graphs.
Both techniques aim to find a path to the goal but differ in the order in which they
explore nodes.

Depth-First Search (DFS)

Definition:
DFS expands the deepest node in the current search frontier first, going as far
along a branch as possible before backtracking.
How it works:
Start at the root node.

BDS602-Ai & Ml 14
 Explore one child node and keep going down to the next level until no
successors are left.
Backtrack to the most recent node with unexplored children and continue.
Implementation:
Uses a Last-In-First-Out (LIFO) data structure (stack) or recursion.
Stores only the current path and siblings, leading to low memory usage.
Time Complexity:
Potentially O(b^m), where b is branching factor and m is maximum depth.
May explore many nodes if the depth is large or infinite.
Space Complexity:
Uses O(b×m) space, much less than BFS in deep trees.
Example:
Imagine searching a maze by always moving forward until hitting a wall, then
backtracking to try different directions. This is like DFS exploring one path fully
before trying others.
Breadth-First Search (BFS)
Definition:
BFS expands the shallowest unexpanded node first, effectively searching level-
by-level.
How it works:
Begin at the root.
Explore all immediate children, then their children, and so on level by level.
Implementation:
Uses a First-In-First-Out (FIFO) queue to store nodes in the frontier.
Time Complexity:
O(b^d), where d is the depth of the shallowest solution.
Space Complexity:

BDS602-Ai & Ml 15
 Uses O(b^d), which can be very large for deep problems.
Example:
Thinking of finding the shortest path in a network by checking all neighbors first,
then neighbors’ neighbors, similar to BFS.

Q8: Explain the concept of Iterative Deepening Search.

Ans:
Introduction:
Iterative Deepening Search (IDS) is a search strategy that combines the benefits
of Depth-First Search (DFS) and Breadth-First Search (BFS). It repeatedly applies
depth-limited search with increasing depth limits until the goal is found.

BDS602-Ai & Ml 16
 Iterative Deepening Search (IDS)
Definition:
IDS performs a series of depth-limited searches with depth limits increasing from
0, 1, 2,... until the goal node is found.
Working Principle:
Start with depth limit = 0: only root node is explored.
Increase depth limit by 1 in each iteration.
Apply depth-limited DFS up to that limit.
Repeat until the goal is located.

BDS602-Ai & Ml 17
 Advantages:
Completeness: Like BFS, IDS is complete for finite state spaces because it
eventually explores all depths.
Optimality: IDS finds the shallowest goal like BFS (if step costs are equal).
Space Efficiency: Uses only O(bd) memory, much less than BFS's O(bd),
because each depth-limited search is DFS-based.
Time Complexity:
Although nodes at upper levels are expanded multiple times, total time
complexity remains O(bd), asymptotically the same as BFS.
Space Complexity:
Requires O(bd) space, where b is branching factor and d is the depth of the
shallowest solution.
Example:
Suppose you are searching for a book on a shelf arranged in layers. You first
check only the topmost layer (depth 0). If not found, you check the top two
layers (depth 1), then three layers (depth 2), and so on until the book is found.
Every time you restart checking from the top, but this ensures you don’t miss
anything while using little space.
Key Points to Remember
IDS overcomes DFS's problem of getting stuck in infinite depth by limiting
depth at each iteration.
It avoids BFS's large memory use by only storing nodes on the current path,
not all nodes at a depth.
IDS is widely preferred when the depth of the solution is unknown and
memory is limited.

Q9: Discuss local search algorithms and the limitations

of Hill Climbing.
Ans:

BDS602-Ai & Ml 18
 Introduction:
Local search algorithms are optimization methods that start with an initial solution
and try to improve it step-by-step by exploring neighbors. Hill Climbing is one
such simple local search algorithm that tries to reach the peak of the solution
space by moving to better neighbors.

Local Search Algorithms

Definition:
Local search algorithms explore the state space by moving from one solution to a
neighboring solution to find better solutions without maintaining a search tree or
memory of all visited states.
Characteristics:
Use only the current state and its neighbors.
Useful for large or infinite state spaces.
Focus on optimization problems.
Common Local Search Algorithms:
Hill Climbing
Simulated Annealing

BDS602-Ai & Ml 19
 Genetic Algorithms
Random Restart Hill Climbing
Hill Climbing Algorithm
Basic Idea:
Start from a random state, evaluate neighbors, move to the neighbor with the best
improvement, and repeat until no better neighbor is found.
Types:
Simple Hill Climbing: Moves to the first better neighbor found.
Steepest-Ascent Hill Climbing: Scans all neighbors and moves to the best one.
Example:
Imagine trying to find the highest point on a hill by walking uphill. You look around
and take the step uphill with the biggest increase in height. You repeat this until no
step leads higher.
Limitations of Hill Climbing
Local Maxima:
The algorithm may get stuck at a point higher than its neighbors but lower than
the global maximum.
Example: Imagine climbing a smaller hill instead of the highest mountain.
Plateaus:
Flat regions where all neighbors have the same value cause the algorithm to
stop because it can’t find a better neighbor to move to.
Example: Walking on a flat plain without any slope to climb.
Ridges:
Narrow paths that ascend diagonally can be hard to climb as single-step
neighbors may not improve. Hill Climbing struggles here.
Example: Climbing a steep and narrow ridge where you must zigzag carefully.
No Backtracking:
Hill Climbing does not remember previous states and cannot backtrack, so it
cannot escape poor choices.

BDS602-Ai & Ml 20