tutorial2.dvi
COMP9414: Artificial Intelligence
Tutorial 2: Search
1. This exercise concerns the route-finding problem using the Romania map from Russell &
Norvig (Artificial Intelligence: A Modern Approach) as an example.
Bucharest
Giurgiu
Urziceni
Hirsova
Eforie
Neamt
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Sibiu
Fagaras
Pitesti
Rimnicu Vilcea
Vaslui
Iasi
Straight−line distance
to Bucharest
0
160
242
161
77
151
241
366
193
178
253
329
80
199
244
380
226
234
374
98
Giurgiu
Urziceni
Hirsova
Eforie
Neamt
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Sibiu Fagaras
Pitesti
Vaslui
Iasi
Rimnicu Vilcea
Bucharest
71
75
118
111
70
75
120
151
140
99
80
97
101
211
138
146 85
90
98
142
92
87
86
Define the route-finding problem (from Arad to Bucharest) as a state space search problem
(give short descriptions of the state space, etc. in English). What order are nodes in the
search graph expanded (give the associated states) for each of the following algorithms when
searching for a (shortest) path between Arad and Bucharest? Assume the successors of a
state are returned in alphabetical order. Make sure you understand the key properties of
the different algorithms listed below.
To clarify, for breadth-first search, stop the search when a node with the goal state is
generated and use a check to ensure that nodes with the same state as a previously expanded
node are not added to the frontier. For the other search algorithms, stop the search when a
node with the goal state is expanded; for uniform-cost search include a check that nodes with
the same state as a previously expanded nodes are not added to the frontier (as in breadth-
first search) and a test so that only one node for a given state is stored on the frontier (that
with the shortest path to that state), and for depth-first search and its variants use cycle
checking along a path to avoid repeated states that can lead to infinite branches.
(i) Depth-first search (efficient use of space but may not terminate)
(ii) Breadth-first search (space inefficient, guaranteed to find a solution)
(iii) Uniform-cost search (similar to breadth-first, but order nodes by cost)
(iv) Iterative deepening depth-first search (space efficient, but repeated work)
(v) Greedy best-first search (efficient, not guaranteed optimal solution)
(vi) A∗ search with straight-line distance heuristic (inefficient, guaranteed optimal solution)
Which algorithm is suitable in practice for solving route-finding problems such as this?
2. This version of the map (from the first edition of the book) differs from that in the second
edition of the book in that the heuristic value for Fagaras is 178 rather than 176, and that for
Pitesti is 98 rather than 100 (also Drobeta is mistakenly spelt as Dobreta). What difference
does this make?
3. Programming. Consider the Python code for generic search algorithms searchGeneric.py.
(i) Try running the various search algorithms to make sure you understand their properties
(as above), their implementations and the relationships between the algorithms. You
can edit searchTest.py to call the search methods on the Romania map problem.
(ii) The supplied code adds successors to the frontier in the order they are defined in the
associated definition of the Romania map in searchProblem.py. By experimenting
with different orderings of the successors (such as alphabetical ordering, as above),
determine how sensitive the algorithms are to this ordering.
(iii) (Harder) Although breadth-first search is a special case of A∗ search (explain how!),
write a class BreadthFirstSearcher extending Searcher in searchGeneric.py that
implements breadth-first search directly, i.e. maintains a set of states from nodes pre-
viously expanded and only adds a neighbour of an expanded node to the frontier if its
state is not in the explored set or in a node already on the frontier, and terminates
when a goal state is generated (not expanded). You will need to code the constructor
and the search method.