CS 188 Introduction to Artificial Intelligence Exam Prep 2
Q1. Searching with Heuristics
Consider the A* searching process on the connected undirected graph, with starting node S and the goal node G. Suppose the
cost for each connection edge is always positive. We define ℎ∗(𝑋) as the shortest (optimal) distance to G from a node X.
Answer Questions (a), (b) and (c). You may want to solve Questions (a) and (b) at the same time.
(a) Suppose ℎ is an admissible heuristic, and we conduct A* tree search using heuristic ℎ′ and finally find a solution. Let
𝐶 be the cost of the found path (directed by ℎ′, defined in part (a)) from S to G
(i) Choose one best answer for each condition below.
1. If ℎ′(𝑋) = 1
ℎ(𝑋) for all Node 𝑋, then # 𝐶 = ℎ∗(𝑆) # 𝐶 > ℎ∗(𝑆) # 𝐶 ≥ ℎ∗(𝑆)
2. If ℎ′(𝑋) = ℎ(𝑋)+ℎ∗(𝑋)
for all Node 𝑋, then # 𝐶 = ℎ∗(𝑆) # 𝐶 > ℎ∗(𝑆) # 𝐶 ≥ ℎ∗(𝑆)
3. If ℎ′(𝑋) = ℎ(𝑋) + ℎ∗(𝑋) for all Node 𝑋, then # 𝐶 = ℎ∗(𝑆) # 𝐶 > ℎ∗(𝑆) # 𝐶 ≥ ℎ∗(𝑆)
4. If we define the set 𝐾(𝑋) for a node 𝑋 as all its neighbor nodes 𝑌 satisfying ℎ∗(𝑋) > ℎ∗(𝑌 ), and the following
always holds
min𝑌∈𝐾(𝑋) ℎ
′(𝑌 ) − ℎ(𝑌 ) + ℎ(𝑋) if 𝐾(𝑋) ≠ ∅
ℎ(𝑋) if 𝐾(𝑋) = ∅
then, # 𝐶 = ℎ∗(𝑆) # 𝐶 > ℎ∗(𝑆) # 𝐶 ≥ ℎ∗(𝑆)
5. If 𝐾 is the same as above, we have
min𝑌∈𝐾(𝑋) ℎ(𝑌 ) + 𝑐𝑜𝑠𝑡(𝑋, 𝑌 ) if 𝐾(𝑋) ≠ ∅
ℎ(𝑋) if 𝐾(𝑋) = ∅
where 𝑐𝑜𝑠𝑡(𝑋, 𝑌 ) is the cost of the edge connecting 𝑋 and 𝑌 ,
then, # 𝐶 = ℎ∗(𝑆) # 𝐶 > ℎ∗(𝑆) # 𝐶 ≥ ℎ∗(𝑆)
6. If ℎ′(𝑋) = min𝑌∈𝐾(𝑋)+{𝑋} ℎ(𝑌 ) (𝐾 is the same as above), # 𝐶 = ℎ∗(𝑆) # 𝐶 > ℎ∗(𝑆) # 𝐶 ≥ ℎ∗(𝑆)
(ii) In which of the conditions above, ℎ′ is still admissible and for sure to dominate ℎ? Check all that apply. Remember
we say ℎ1 dominates ℎ2 when ℎ1(𝑋) ≥ ℎ2(𝑋) holds for all 𝑋. □ 1 □ 2 □ 3 □ 4 □ 5 □ 6
(b) Suppose ℎ is a consistent heuristic, and we conduct A* graph search using heuristic ℎ′ and finally find a solution.
(i) Answer exactly the same questions for each conditions in Question (a)(i).
1. # 𝐶 = ℎ∗(𝑆) # 𝐶 > ℎ∗(𝑆) # 𝐶 ≥ ℎ∗(𝑆) 2. # 𝐶 = ℎ∗(𝑆) # 𝐶 > ℎ∗(𝑆) # 𝐶 ≥ ℎ∗(𝑆)
3. # 𝐶 = ℎ∗(𝑆) # 𝐶 > ℎ∗(𝑆) # 𝐶 ≥ ℎ∗(𝑆) 4. # 𝐶 = ℎ∗(𝑆) # 𝐶 > ℎ∗(𝑆) # 𝐶 ≥ ℎ∗(𝑆)
5. # 𝐶 = ℎ∗(𝑆) # 𝐶 > ℎ∗(𝑆) # 𝐶 ≥ ℎ∗(𝑆) 6. # 𝐶 = ℎ∗(𝑆) # 𝐶 > ℎ∗(𝑆) # 𝐶 ≥ ℎ∗(𝑆)
(ii) In which of the conditions above, ℎ′ is still consistent and for sure to dominate ℎ? Check all that apply.
□ 1 □ 2 □ 3 □ 4 □ 5 □ 6
(c) Suppose ℎ is an admissible heuristic, and we conduct A* tree search using heuristic ℎ′ and finally find a solution.
If 𝜖 > 0, and 𝑋0 is a node in the graph, and ℎ′ is a heuristic such that
ℎ(𝑋) if 𝑋 = 𝑋0
ℎ(𝑋) + 𝜖 otherwise
• Alice claims ℎ′ can be inadmissible, and hence 𝐶 = ℎ∗(𝑆) does not always hold.
• Bob instead thinks the node expansion order directed by ℎ′ is the same as the heuristic ℎ′′, where
ℎ(𝑋) − 𝜖 if 𝑋 = 𝑋0
ℎ(𝑋) if otherwise
Since ℎ′′ is admissible and will lead to 𝐶 = ℎ∗(𝑆), and so does ℎ′. Hence, 𝐶 = ℎ∗(𝑆) always holds.
The two conclusions (underlined) apparently contradict with each other, and only exactly one of them are correct and
the other is wrong. Choose the best explanation from below – which student’s conclusion is wrong, and why are they
# Alice’s conclusion is wrong, because the heuristic ℎ′ is always admissible.
# Alice’s conclusion is wrong, because an inadmissible heuristics does not necessarily always lead to the failure of the
optimality when conducting A* tree search.
# Alice’s conclusion is wrong, because of another reason that is not listed above.
# Bob’s conclusion is wrong, because the node visiting expansion ordering of ℎ′′ during searching might not be the
same as ℎ′.
# Bob’s conclusion is wrong, because the heuristic ℎ′′ might lead to an incomplete search, regardless of its optimally
# Bob’s conclusion is wrong, because of another reason that is not listed above.
Q2. Iterative Deepening Search
Pacman is performing search in a maze again! The search graph has a branching factor of b, a solution of depth d, a maximum
depth of m, and edge costs that may not be integers. Although he knows breadth first search returns the solution with the smallest
depth, it takes up too much space, so he decides to try using iterative deepening. As a reminder, in standard depth-first iterative
deepening we start by performing a depth first search terminated at a maximum depth of one. If no solution is found, we start
over and perform a depth first search to depth two and so on. This way we obtain the shallowest solution, but use only O(bd)
But Pacman decides to use a variant of iterative deepening called iterative deepening A*, where instead of limiting the depth-
first search by depth as in standard iterative deepening search, we can limit the depth-first search by the f value as defined in A*
search. As a reminder f [node] = g[node] + h[node] where g[node] is the cost of the path from the start state and h[node] is a
heuristic value estimating the cost to the closest goal state.
In this question, all searches are tree searches and not graph searches.
(a) Complete the pseudocode outlining how to perform iterative deepening A* by choosing the option from the next page
that fills in each of these blanks. Iterative deepening A* should return the solution with the lowest cost when given a
consistent heuristic. Note that cutoff is a boolean and new-limit is a number.
function ITERATIVE-DEEPENING-TREE-SEARCH(problem)
start-node ← MAKE-NODE(INITIAL-STATE[problem])
limit ← f [start-node]
fringe ← MAKE-STACK(start-node)
new-limit ← (i)
cutoff ← (ii)
while fringe is not empty do
node ← REMOVE-FRONT(fringe)
if GOAL-TEST(problem, STATE[node]) then
return node
for child-node in EXPAND(STATE[node], problem) do
if f [child-node] ≤ limit then
fringe ← INSERT(child-node, fringe)
new-limit ← (iii)
cutoff ← (iv)
new-limit ← (v)
cutoff ← (vi)
if not cutoff then
return failure
limit ← (vii)
end function
𝐀𝟏 −∞ 𝐀𝟐 0 𝐀𝟑 ∞ 𝐀𝟒 limit
𝐁𝟏 True 𝐁𝟐 False 𝐁𝟑 cutoff 𝐁𝟒 not cutoff
𝐂𝟏 new-limit 𝐂𝟐 new-limit + 1 𝐂𝟑 new-limit +
𝐂𝟒 new-limit +
f [child-node]
𝐂𝟓 MIN(new-limit,
𝐂𝟔 MIN(new-limit,
f [child-node])
𝐂𝟕 MAX(new-limit,
𝐂𝟖 MAX(new-limit,
f [child-node])
(i) #𝐀𝟏 #𝐀𝟐 #𝐀𝟑 #𝐀𝟒
(ii) #𝐁𝟏 #𝐁𝟐 #𝐁𝟑 #𝐁𝟒
(iii) #𝐂𝟏 #𝐂𝟐 #𝐂𝟑 #𝐂𝟒
#𝐂𝟓 #𝐂𝟔 #𝐂𝟕 #𝐂𝟖
(iv) #𝐁𝟏 #𝐁𝟐 #𝐁𝟑 #𝐁𝟒
(v) #𝐂𝟏 #𝐂𝟐 #𝐂𝟑 #𝐂𝟒
#𝐂𝟓 #𝐂𝟔 #𝐂𝟕 #𝐂𝟖
(vi) #𝐁𝟏 #𝐁𝟐 #𝐁𝟑 #𝐁𝟒
(vii) #𝐂𝟏 #𝐂𝟐 #𝐂𝟑 #𝐂𝟒
#𝐂𝟓 #𝐂𝟔 #𝐂𝟕 #𝐂𝟖
(b) Assuming there are no ties in f value between nodes, which of the following statements about the number of nodes that
iterative deepening A* expands is True? If the same node is expanded multiple times, count all of the times that it is
expanded. If none of the options are correct, mark None of the above.
# The number of times that iterative deepening A* expands a node is greater than or equal to the number of times
A* will expand a node.
# The number of times that iterative deepening A* expands a node is less than or equal to the number of times
A* will expand a node.
# We don’t know if the number of times iterative deepening A* expands a node is more or less than the number
of times A* will expand a node.
# None of the above