University of Cagliari

MSc courses in Computer Engineering, Cybersecurity and Artificial Intelligence, and in Electronic Engineering

Artificial Intelligence
Academic Year: 2019/2020
Instructor: Giorgio Fumera

Exercises on search algorithms

1. The graph in the figure below shows the state space of a hypothetical search problem. States are denoted
by letters, and the cost of each action is indicated on the corresponding edge. Note that actions are
not reversible, since the graph is oriented. The table next to the state space shows the value of some
admissible heuristic function, considering G as the goal state (it is easy to verify that such an heuristic
never overestimates the true, minimum path cost from any given state to the goal state G).

state space

3 F 6
heuristic function (goal state: G)
2 2 4
S A C G S A B C D E F G
3 4 6 4 5 2 2 8 4 0
1
B 2 D
4
E

Considering S as the initial state, solve the above search problem using:
• breadth-first search
• depth-first search
• A* search with the heuristic above
When drawing the search tree you should clearly indicate: the order of expansion of each node (e.g., by
numbering the expanded nodes according to the order of their expansion); the action corresponding to
each edge of the tree; the state, the path cost and the value of the heuristic of each node. In the case
of depth-first search you should also indicate which nodes of the search tree are simultaneously stored in
computer memory (in the case of a computer implementation) during the search process.
2. The block’s world is a well-known toy domain used in AI for planning problems related to robots. It
consists of a set of blocks of various size, shape, and color, possibly identified by a letter or by a number,
and placed on a surface (e.g., on a table); the blocks can be stacked into one or more piles, possibly with
some constraints (depending, e.g., on their size); the goal is to form a target set of piles starting from
a given initial configuration, by moving one block at a time, either to the table or atop another pile of
blocks, and only if it is not under another block.
Consider a simple version of this problem, in which there are five blocks with identical shape and size,
numbered from 1 to 5. The figure below shows two possible configurations of such blocks; note that the
relative position of the piles does not matter, thus the configuration on the left is equivalent to the one
in the middle. Every block can be either on the table (there are no constraints on the number of piles)
or atop any another block. The goal is to stack the blocks in a single pile, in the order shown in the
rightmost configuration in the figure, starting from any given set of piles, by moving the smallest possible
number of blocks. Only blocks at the top of the current piles can be moved, and can be placed only on
the table or atop another pile.
 1
2
2 2 3
5 1 1 5 4
3 4 4 3 5

(a) Formulate the above version of the block’s world as a search problem, by precisely defining the state
space, the initial state, the goal test, the set of possible actions and the path cost.
(b) Assume that the initial configuration is the one shown on the left in the figure above, and consider
a heuristic function defined as the number of blocks that are not in the highest pile (or in one of the
highest piles). Under this setting, show how the A* search strategy expands the first four nodes of
the search tree, avoiding repeated states. As in the previous exercise, when drawing the search tree
you should clearly indicate: the order of expansion of each node; the action corresponding to each
edge of the tree; the state, the path cost and the value of the heuristic of each node.
(c) Define another possible admissible heuristic, and prove its admissibility.

3. Assuming you have to implement search algorithms for solving different problems (like 8-puzzle, route
finding on a map, and the block’s world), define the data structures and the program structure in a
programming language of your choice.
Try to make your program as much modular as possible; in particular, you should distinguish between
problem-independent data structures and procedures, and problem-specific ones. In other words, your
program should be applicable to different problems by defining or redefining only the necessary data
structures and procedures.
For instance, the nodes of a search tree can be represented using a problem-independent data structure
which may contain the representation of a state and of the action that lead to it, the path cost, the value
of the heuristic function, the reference to the parent node, etc. The state of a particular search problem
should be represented instead by a problem-specific data structure. Similarly, the iterative procedure for
searching a solution by expanding a search tree and the different search strategies (like breadth-first and
A*) are problem-independent, whereas the operators implementing the available actions and the goal test
procedure are problem-dependent.
Solution
Exercise 1
The search trees built by the three strategies are shown below. The number of the left of each node
denotes its path cost for breadth- and depth-first search (note however that the path cost is not used by
these strategies to choose the next leaf node to expand), and the sum of its path cost and heuristic for
A*-search. The order of expansion is denoted by the small numbers inside squares. For the sake of clarity,
the search tree obtained after each expansion is shown.
Remember that when several leaf nodes can be chosen for expansion (i.e., when there is more than one
leaf node at the lowest depth for breadth-first search, or at the highest depth for depth-first search, or
with the lowest value of the evaluation function for A*-search – the sum of the path cost and the heuristic
function) a random choice should be made among them; in this exercise we assume that the choice is made
by considering the alphabetical ordering among the corresponding states (e.g., if the choice is among nodes
A, B and F, node A is chosen). This happens at step 9 in the search tree below.
Finally, remember that the goal test is applied when a node is selected for expansion: therefore a solution
is found not when a node containing a goal state is generated (by expanding it parent node), but when it
is selected for expansion.
The search tree built by breadth-first search, step by step, is shown in the figure below (from top to
bottom and from left to right). Note that different nodes can correspond to the same state (this is the
case of states D and G): this means that such a state can be reached from the initial state through different
paths in the state space (i.e., different sequences of actions), possibly with different path costs: therefore
such nodes should be kept distinct in the search tree. Note also that node E has no successors (no other
state can be reached from state E, according to the state space): therefore when it is selected for expansion
(in step 8 ) no children nodes are added to the tree. Finally, note that the solution found by breadth-first
search (S→F→G) is not the one with minimum path cost, as it can happen due to the fact that this search
strategy is not optimal.

1
0 S 0 S 0 S

2
2 A 1 B 3 F 2 A 1 B 3 F

4 C 5 D

0 S 0 S 0 S
3 4
2 A 1 B 3 F 2 A 1 B 3 F 2 A 1 B 3 F
5
4 C 5 D 3 D 5 E 4 C 5 D 3 D 5 E 9 G 4 C 5 D 3 D 5 E 9 G

8 G

0 S 0 S 0 S

2 A 1 B 3 F 2 A 1 B 3 F 2 A 1 B 3 F
6 7 8
4 C 5 D 3 D 5 E 9 G 4 C 5 D 3 D 5 E 9 G 4 C 5 D 3 D 5 E 9 G

8 G 9 G 8 G 9 G 7 G 8 G 9 G 7 G

0 S

2 A 1 B 3 F
9
4 C 5 D 3 D 5 E 9 G

8 G 9 G 7 G
The search tree built by depth-first search is shown below. In this case a solution is found along the
path which is explored first (when the node corresponding to state G is selected for expansion at step
4 ). Therefore no backtracking step is carried out and no already expanded node along “dead ends” is
deleted. Note that also in this case the solution found is not the minimum-cost one (depth-first search is
not optimal).

1
0 S 0 S 0 S

2
2 A 1 B 3 F 2 A 1 B 3 F

4 C 5 D

0 S 0 S

2 A 1 B 3 F 2 A 1 B 3 F
3

4 C 5 D 4 C 5 D
4
8 G 8 G

The search tree built by A*-search is finally shown below. The solution found at step 8 is the minimum-
cost one, according to the fact that A* is optimal when an admissible heuristic is used.

1
0 S 0 S 0 S
2
2+4 A 1+5 B 3+4 F 2+4 A 1+5 B 3+4 F

4+2 C 5+2 D

0 S 0 S 0 S

3
2+4 A 1+5 B 3+4 F 2+4 A 1+5 B 3+4 F 2+4 A 1+5 B 3+4 F
4 5
4+2 C 5+2 D 3+2 D 5+8 E 4+2 C 5+2 D 3+2 D 5+8 E 4+2 C 5+2 D 3+2 D 5+8 E

7+0 G 8+0 G 7+0 G

0 S 0 S 0 S
6
2+4 A 1+5 B 3+4 F 2+4 A 1+5 B 3+4 F 2+4 A 1+5 B 3+4 F
7
4+2 C 5+2 D 3+2 D 5+8 E 9+0 G 4+2 C 5+2 D 3+2 D 5+8 E 9+0 G 4+2 C 5+2 D 3+2 D 5+8 E 9+0 G
8
8+0 G 7+0 G 8+0 G 9+0 G 7+0 G 8+0 G 9+0 G 7+0 G
 Exercise 2

(a) The state space is made up of the set of distinct arrangements of the five blocks into one or more
(up to five) piles. A state can be represented by a set 1 of piles, and each pile can be represented as
a sequence of block numbers, where the numbers from left to right correspond, e.g., to block from
the top to the bottom of the pile. For instance, the two equivalent configurations of piles (states)
shown on the left and in the middle of the above figure are represented by the set {(2, 5, 3), (1, 4)}.
Accordingly, the goal state is represented by (1, 2, 3, 4, 5).
The actions can be formally described as follows: given a state {(b1,1 , . . . , b1,n1 ), . . . , (bp,1 , . . . , bp,np )},
where p denotes P the number of piles (1 ≤ p ≤ 5) and nk the number of blocks in the k-th pile (nk ≥ 1
p
for each k, and k=1 nk = 5), the actions consist of moving one of the p blocks bk,1 (on the top of
one of the piles) either to the table, thus generating a new pile (only if the original pile contains more
then one block, i.e., nk > 1), or atop one of the other p − 1 piles (if any).
Actions can be implemented as a successor function SF : it receives as an argument the description
s of a state, and returns all the pairs (s0 , a) where s0 is one of the states obtained as described above,
and a the description of the corresponding action. Each action can be described by indicating the
number of the block that has been moved, bk,1 , and its new position, i.e., the number of the block
atop of which it has been placed, or the table (which can be denoted by the number 0). For instance,
from state {(2, 5, 3), (1, 4)} the action (2, 0) consists of moving the block 2 to the table, leading to
the state {(5, 3), (2), (1, 4)}, and (1, 2) consists of moving the block 1 atop the block 2, leading to the
state {(1, 2, 5, 3), (4)}.
Finally, since the goal is to reach the target configuration by moving the smallest possible number of
blocks, it follows that the path cost is given by the number of actions that have been carried out to
reach a given state from the initial one, and thus each action has a cost equal to 1.
(b) The search tree obtained by the A* search strategy after the expansion of the first four nodes, using
the heuristic given in the text and avoiding repeated states, is shown in the figure below. For the
sake of clarity, the tree obtained after the expansion of each node is shown.
The A* evaluation function (path cost + heuristic) is shown below each state. The numbers inside
circles denote the order in which the corresponding node has been expanded. Note that the third
node has no successors, since the only action that can be carried out on its state leads to a repeated
state (the one of its parent node). Note also that the are two candidate leaf nodes to be expanded
at the fourth iteration of A* (the second and fourth node from left in the figure, at depth 1), since
they exhibit the same value of the evaluation function, which is lower than the one of the remaining
leaf nodes; in this case a random choice has to be made between the candidate nodes: in the figure
below the node on the right is chosen for expansion.

1 According to the problem definition, the ordering between piles is not relevant.
 root node:
2
5 1
3 4
0+2

2
5 1 1
3 4
0+2

1
2 2 2
5 1 5 5 5 1
2 3 4 3 4 1 3 4 3 4
1+3 1+2 1+1 1+2

2
5 1 1
3 4
0+2

1
2 2 2 2
5 1 5 5 5 1
2 3 4 3 4 1 3 4 3 4
1+3 1+2 1+1 1+2

4
1
2
5
3
2+0
 2
5 1 1
3 4
0+2

1
2 2 2 2
5 1 5 5 5 1
2 3 4 3 4 1 3 4 3 4
1+3 1+2 1+1 1+2

4
1
2 3
5
3
2+0

2
5 1 1
3 4
0+2

1
2 2 2 2 4
5 1 5 5 5 1
2 3 4 3 4 1 3 4 3 4
1+3 1+2 1+1 1+2

4
1 5
2 3 2 2
5 1 1
3 5 3 4 3 4
2+0 2+2 2+1

(c) Another possible admissible heuristic is the following: let n be the number of blocks above which
there is a block different from the one in the goal state; then the heuristic is defined as bn/2c. For
instance, if the goal state is {(1, 2, 3, 4, 5)}, in the state {(2, 5, 3), (1, 4)}:
• there is no block atop block 1, which counts as 0;
• there is no block atop block 2, contrary to the goal state: this counts as 1;
• block 5, instead of block 2, is atop block 3: this counts as 1;
• block 1, instead of block 3, is atop block 4: this counts as 1;
• block 2, instead of block 4, is atop block 5: this counts as 1;
the value of the heuristic function for the state {(2, 5, 3), (1, 4)} is therefore b4/2c = 2; in other words,
at least two blocks have to be moved to reach the goal state.
It is not difficult to see that this heuristic is admissible: by moving one block from any state s0 , at
most two other blocks will have a different block atop in the resulting state s00 , and therefore in s00
at most two more blocks than in s0 can have the correct block atop as in the goal state.

Exercise 3
See the textbook and the lecture slides.