Introduction to Artificial Intelligence

IT3160E
Topic: Search
Exercise
Exercise 1:
• Consider the following graph, where 'S' is the start node and 'G' is the goal
node. The numbers on the edges represent the cost of traversing that edge.

Assume that when multiple nodes are added to the fringe,

they are added in alphabetical order. Trace the sequence of
nodes expanded by the following algorithms to find the path
from S to G.
1. Breadth-First Search (BFS): Show the state of the fringe
(queue) at each step.
2. Depth-First Search (DFS): Show the state of the fringe
(stack) at each step.
3. Iterative Deepening Search (IDS): Show the nodes
expanded at each depth limit (l=0, l=1, ...), until the goal
is found.

4
Exercise 2:

The "Pouring Water" problem is a classic search problem. You are given a 5-litre
jug and a 3-litre jug. Neither jug has any markings on it. You have an unlimited
supply of water. Your goal is to get exactly 4 litres of water in the 5-litre jug.

Define this problem by specifying the following components:

1.State Space: How would you represent a state? What are the possible values?
(e.g., a state can be represented as an ordered pair (x,y), where x is the water
in the 5-litre jug and y is the water in the 3-litre jug).
2.Initial State: What is the starting state of the problem?
3.Successor Function (Actions): List all possible actions you can take from any
given state (x,y). For example, one action is "Fill the 5-litre jug completely."
4.Goal Test: How do you know when you have solved the problem?

5
Definition of “Pouring Water”

• Given 2 containers A(m litres), B(n litres). Finding a method to measure k litres (
k < max(m,n) ) by 2 containers A, B and a container C
• Action: C → A; C → B; A → B; A → C; B → A; B → C
• Conditions: no overflow, pouring all water
• Mathematical model:
(x, y) → (x’, y’)
AB AB

6
Exercise 3:

Trace the path from Arad to Bucharest. Show the first 4 steps of expansion for
each algorithm below. For each step, show the node being expanded and the
current state of the fringe, ordered by the eval function.
1. Greedy Best-First Search: The evaluation function is f(n)=h(n).
2. A* Search: The evaluation function is f(n)=g(n)+h(n).

7
Exercise 4:
The 8-puzzle:
• ℎ1 (𝑛): The number of misplaced tiles.
• ℎ2 (𝑛): The total Manhattan distance

1. Explain why both h1​(n) and h2​(n) are admissible heuristics. An

admissible heuristic never overestimates the cost to reach the goal
2. We have if ℎ2 (𝑛) ≥ ℎ1 (𝑛): for all n, then ℎ2 dominates ℎ1 ​ and is better
for search. Prove that ℎ2 ​ ​ dominates ℎ1 ​ .
3. Why does a dominating heuristic like ℎ2 ​ lead to better search
performance? Relate your answer to the evaluation function of A*,
f(n)=g(n)+h(n), and how it prunes the search space.

8
Exercise 5

• Consider the following weighted graph where S is the start node and G is the
goal. The heuristic value h(n) for each node is shown below.

Greedy Best-First Search: Find a path from S to G.

S
A* Search: Trace the A* algorithm (f(n)=g(n)+h(n)) to
find a path from S to G.
• What is the order of expanded nodes?
A B
• What is the path found and its total cost?

Comparison: Explain why Greedy Best-First Search

C D chose a suboptimal path in this specific scenario. How
did the g(n) component of A* search help it avoid the
"trap"?
G

9
Exercise 6:

• For A* to be optimal with Graph Search, the heuristic must be

consistent. A heuristic is consistent if for any node n and its successor
n′, h(n) ≤ c(n,n′) + h(n′)

10
Exercise 6

Consider the graph below with an admissible but

inconsistent heuristic. The goal is node G
1. For each node (S, A, B), find the true cost of the optimal
path to G (ℎ∗ (𝑛)) and show that ℎ(𝑛) ≤ ℎ∗ (𝑛).
2. Identify the edge and successor pair that violates the
consistency rule.
S
3. Trace the A* algorithm using Graph Search.
A 4. What path does the algorithm find? What is its cost?
What is the actual optimal path and cost? Explain how
the inconsistent heuristic combined with the closed set
B caused A* to return a suboptimal solution.

11
Exercise 7:

• Consider the cryptarithmetic puzzle

• Define the states, initial state, successor function and

goal test.
• What is the max depth of the search tree?
• What is the branching factor at the top of the tree?
• Compare the feasibility of using Depth-First Search
versus Breadth-First Search to solve this problem.

12
Exercise 7

• 𝐷 + 𝐸 = 𝑌 + 10 ∗ 𝑅1
• 𝑁 + 𝑅 = 𝐸 + 𝑅1 + 10 ∗ 𝑅2
• 𝐸 + 𝑂 = 𝑁 + 𝑅2 + 10 ∗ 𝑅3
• 𝑆 + 𝑀 = 𝑀 + 𝑅3 + 10 ∗ 𝑅4
• 𝑀 = 𝑅4
• 𝑅𝑖 ∈ 0,1

13
Exercise 8

Given the search problem defined by the below graph, where A is the initial state
and L is the goal state, the cost is indicated on the edge
Solve the problem using the following search strategies:
1. Breadth-first with elimination of repeated states
2. Uniform-cost with elimination of repeated states
3. Depth-cost with elimination of repeated states

14
Exercise 9

You have 3 containers that may hold 12 liters, 8 liters and 3 liters of water,
respectively, as well as access to a water faucet. You can fill a container from the
faucet, pour it into another container, or empty it onto the ground. The goal is to
measure exactly one liter of water.
1. Give a specification of the task as a search problem
2. Draw the search tree produced by depth-limited search with maximum depth
equal to three and elimination of repeated states.

15
Exercise 10

Given the search problem defined by the following graph, where A is the initial
state and G is the goal state and the cost of each action is indicated on the
corresponding edge:
Solve the search problem using the following search strategies:
1. breadth-first with elimination of repeated states
2. depth-first with elimination of repeated states
3. uniform-cost without elimination of repeated states
4. uniform-cost with elimination of repeated states
5. greedy best-first without elimination of repeated states
6. greedy best-first with elimination of repeated states
7. A∗ without elimination of repeated states
8. A∗ with elimination of repeated states 11. Is the heuristic h admissible? Is it
consistent?

16
Exercise 10

• Given the search problem defined by the following graph, where A is the initial
state and G is the goal state and the cost of each action is indicated on the
corresponding edge:

17
Exercise 11

• Consider a version of best-first search that uses f(n) = (2 – ω) g(n) + ω h(n) for
some constant ω. What kind of search does this perform for ω = 0, ω = 1, and ω
= 2? For which values of ω is the search optimal, assuming that h is admissible?

18
THANK YOU !

19