Module 2: Problem Solving by Searching
The concept of a problem-solving agent. What are the components of a
search problem?
A problem-solving agent is a type of intelligent agent that formulates goals and searches for
solutions to achieve those goals through a sequence of actions. Unlike reactive agents,
problem-solving agents plan ahead before taking actions.
A problem-solving agent operates in three phases:
1. Goal formulation: The agent decides what it wants to achieve.
2. Problem formulation: It defines the search problem based on the current state and
possible actions.
3. Search and execution: It searches for the best solution path and executes the resulting
plan.
The five components of a well-defined search problem are:
1. Initial State: The starting point from which the agent begins searching.
2. Actions (Successor function): Defines the set of legal actions available to the agent.
3. Transition Model: Describes the result of performing an action in a given state.
4. Goal Test: Determines whether the current state is a goal state.
5. Path Cost: A numerical cost associated with a path. The objective is usually to find the
path with the lowest cost.
Example: Route Finding Problem
- Initial state: City A
- Actions: Move to adjacent cities
- Transition model: Resulting city after each move
- Goal test: Destination reached?
- Path cost: Distance or time of travel
Detailed note on uninformed search strategies. Compare different
uninformed search algorithms.
Uninformed search strategies are also known as blind search strategies. They do not use
any domain-specific knowledge about the goal. They explore the search space
systematically.
Types of Uninformed Search Strategies:
1. Breadth-First Search (BFS)
2. Depth-First Search (DFS)
3. Uniform Cost Search (UCS)
4. Depth-Limited Search (DLS)
5. Iterative Deepening DFS (IDDFS)
Comparison Table:
Time Space
Strategy Complete Optimal Notes
Complexity Complexity
Explores shallow nodes
BFS Yes Yes O(b^d) O(b^d)
first
Can go deep and loop
DFS No No O(b^m) O(bm)
forever
Like BFS but with cost-
UCS Yes Yes O(b^(C*/ε)) O(b^d)
aware expansion
Depth-limited version of
DLS No No O(b^l) O(bl)
DFS
Combines benefits of BFS
IDDFS Yes Yes O(b^d) O(bd)
and DFS
Breadth-First Search (BFS)
Definition:
Breadth-First Search is an uninformed search strategy that explores all nodes at the current
depth before moving to nodes at the next depth level.
Working:
• BFS uses a FIFO queue.
• It expands the shallowest unexpanded node first.
• Suitable for finding shortest path if all step costs are equal.
Example:
Start at node A
Graph: A → B, A → C, B → D, C → E
Order of expansion: A → B → C → D → E
Pseudocode (optional for extra detail):
BFS(problem):
Initialize queue with initial state
While queue not empty:
Dequeue a node
If node is goal, return solution
Enqueue all unvisited child nodes
Evaluation:
• Complete: Yes
• Optimal: Yes (if costs are equal)
• Time Complexity: O(b^d)
• Space Complexity: O(b^d)
BFS Tree (Level-order Expansion):
A
/ \
B C
/\ /\
D E F G
Order of Expansion: A → B → C → D → E → F → G
Depth-First Search (DFS)
Definition:
DFS explores as deep as possible along each branch before backtracking.
Working:
• DFS uses a LIFO stack (or recursion).
• It can get stuck in infinite paths unless depth-limited.
• Faster than BFS in practice but may miss the shortest path.
Example:
Graph: A → B → D, A → C → E
Order: A → B → D → C → E
Evaluation:
• Complete: No (if loops/infinite depth)
• Optimal: No
• Time Complexity: O(b^m)
• Space Complexity: O(bm)
DFS Tree (Deep-first Expansion):
A
/ \
B C
/\ /\
D E F G
Order of Expansion: A → B → D → E → C → F → G
Uniform Cost Search (UCS)
Definition:
UCS expands the node with the lowest path cost (g(n)), not depth.
Working:
• Uses a priority queue ordered by cumulative cost.
• Finds least-cost solution, even with varying path costs.
Example:
Graph: A → B (2), A → C (5), B → Goal (3), C → Goal (1)
UCS explores A → B → Goal = cost 5 before A → C → Goal = cost 6
Evaluation:
• Complete: Yes
• Optimal: Yes
• Time Complexity: O(b^(C*/ε))
• Space Complexity: O(b^d)
(C* = cost of optimal solution, ε = smallest step cost)
Depth-Limited Search (DLS)
Definition:
DLS is DFS with a predetermined depth limit, preventing infinite loops.
Working:
• Ignores any path beyond the depth limit.
• Helps avoid getting stuck in infinite paths.
Example:
If the goal is at depth 4 and depth limit = 3, DLS will fail.
Evaluation:
• Complete: No (if goal is beyond limit)
• Optimal: No
• Time Complexity: O(b^l)
• Space Complexity: O(bl)
(l = depth limit)
Iterative Deepening DFS (IDDFS)
Definition:
IDDFS is a combination of DFS and BFS. It performs DFS with increasing depth limits.
Working:
• Runs DFS with depth = 0, 1, 2, ..., until goal is found.
• Combines DFS’s space efficiency with BFS’s completeness.
Example:
Goal at depth 3 → IDDFS does DFS(0), then DFS(1), then DFS(2), then finds it in DFS(3)
Evaluation:
• Complete: Yes
• Optimal: Yes (if step cost = 1)
• Time Complexity: O(b^d)
• Space Complexity: O(bd)
Informed search strategies? Explain A* algorithm with an example.
Informed search strategies differ from uninformed ones in that they use additional
information about the problem domain — typically in the form of a heuristic function. These
strategies are more efficient as they guide the search toward the goal instead of exploring
blindly. Among these, the A* (A-star) algorithm is one of the most popular and effective.
A* combines the advantages of Uniform Cost Search and Greedy Best-First Search by
considering both the cost to reach a node and the estimated cost to reach the goal from
there. This makes A* both optimal and complete when used with the right heuristic.
Informed search strategies use domain-specific knowledge in the form of heuristics to find
solutions more efficiently.
A* Search Algorithm:
Uses the function f(n) = g(n) + h(n)
- g(n): Actual cost from the start node to node n.
- h(n): Heuristic estimated cost from n to the goal.
Admissible Heuristic:
- Never overestimates the cost to reach the goal.
Consistent Heuristic:
- h(n) ≤ c(n, a, n') + h(n')
Example: Route Finding
- Cities as nodes.
- h(n): Straight-line distance to destination.
- A* finds the path with the least total estimated cost.
Advantages:
- A* is complete and optimal when h(n) is admissible.
Define heuristic function. Explain its role with examples. Also
differentiate between admissible and consistent heuristics.
A heuristic function h(n) is used in informed search strategies to estimate the cost from a
given state n to the goal state. It guides the search algorithm to choose the most promising
path.
Role of Heuristic:
- Helps reduce the number of nodes explored.
- Used in algorithms like Greedy Best-First Search and A*.
Examples of Heuristics:
1. Straight-line distance (route finding)
2. Number of misplaced tiles (8-puzzle)
3. Manhattan distance (grid-based problems)
Admissible Heuristic:
- h(n) ≤ actual cost to goal.
Consistent Heuristic:
- h(n) ≤ cost(n to n') + h(n')
Comparison Table:
Property | Admissible Heuristic | Consistent Heuristic
---------------|----------------------------------|-----------------------------
Definition | h(n) ≤ true cost to goal | h(n) ≤ cost + h(n')
Optimality | Guarantees A* optimality | Guarantees A* optimality
Efficiency | May re-expand nodes | Never re-expands nodes
Explain Greedy Best-First Search with an example. Is it complete and
optimal?
Greedy Best-First Search is an informed search strategy that uses a heuristic function h(n)
to estimate the cost to reach the goal. It chooses the node that appears closest to the goal,
based solely on this heuristic.
It does not consider the cost to reach the current node (g(n)), making decisions based on
future estimates only.
Formula:
f(n) = h(n)
Example:
Imagine finding a restaurant using Google Maps, and you pick the one that looks closest in
straight line, without checking the actual traffic or road conditions. It might be fast, or it
might lead you into traffic — that’s how Greedy search works.
Advantages:
- Fast and simple to implement.
- Works well when the heuristic is very accurate.
Disadvantages:
- Not complete: Can get stuck in loops.
- Not optimal: May miss better solutions.
Comparison with A*:
| Strategy | Formula | Optimal | Complete
|------------------------- |------------------------|------------ |---------------
| Greedy Best-First | f(n) = h(n) | No | No
| A* Search | f(n) = g(n) + h(n) | Yes | Yes