CSCI 3430 - (Introduction to Artificial Intelligence)
Assignment #1
Problem 1. Invent a heuristic funciton for the 8-puzzle that sometimes overestimates. Prove that if h
never overestimates by more than c, A* using h returns a solution whose cost exceeds that of the
optimal solution by no more than c.
Problem 2. Which of the following are true and which are false? Explain your answers.
(a) Depth-first search always expands at least as many nodes as A* search with an admissible
heuristic.
(b) h(n) = 0 is an admissible heuristic for the 8-puzzle.
(c) Breadth-first search is complete even if zero step costs are allowed.
Problem 3. For each of the following graph search strategies, work out the order in which states are
expanded, as well as the path returned by graph search. In all cases, assume ties resolve in such a way
that states with earlier alphabetical order are expanded first. The start and goal state are S and G,
respectively. Remember that in graph search, a state is expanded only once.
A
h=2 Goal
2 2
4
Start C
h=2
5 5
3 1
B D
h=5 4 h=1
(a) Depth-first search.
(b) Breadth-first search.
(c) Uniform cost search.
(d) Greedy search with the heuristic h shown on the graph.
(e) A* search with the same heuristic.
Problem 4.
Node h1 h2
A 9.5 10
B 9 12
C 8 10
D 7 8
E 1.5 1
F 4 4.5
G 0 0
Consider the state space graph shown above. A is the start state and G is the goal state. The costs for
each edge are shown on the graph. Each edge can be traversed in both directions. Note that the
heuristic h1 is consistent but the heuristic h2 is not consistent.
(a) Possible paths returned
For each of the following graph search strategies (do not answer for tree search), mark which,
if any, of the listed paths it could return. In all cases, assume ties resolve in such a way that
states with earlier alphabetical order are expanded first.
Search Algorithm A-B-D-G A-C-D-G A-B-C-D-F-G
Depth first search
Breadth first search
Uniform cost search
A* search with heuristic h1
A* search with heuristic h2
(b) Heuristic function properties
Suppose you are completing the new heuristic function h3 shown below. All the values are fixed
except h3(B).
Node A B C D E F G
h3 10 ? 9 7 1.5 4.5 0
For each of the following conditions, write the set of values that are possible for h3(B). For
example, to denote all non-negative numbers, write [0, ∞], to denote the empty set, write ∅, and
so on.
(i) What values of h3(B) make h3 admissible?
(ii) What values of h3(B) make h3 consistent?
(iii) What values of h3(B) will cause A* graph search to expand node A, then node C, then
node B, then node D in order?
