Question 1: Search Algorithms for the 15-Puzzle (2 marks)
In this question you will construct a table showing the number of states
expanded when the 15-puzzle is solved, from various starting positions, using
four different searches:
(i) Uniform Cost Search (with Dijkstra’s Algorithm)
(ii) Iterative Deepening Search
(iii) A*Search (using the Manhattan Distance heuristic)
(iv) Iterative Deepening A*Search
Go to the Course Web Site, Week 3 Prolog Code: Path Search, scroll to the
Activity at the bottom of the page and click on “prolog search.zip”.
Unzip the file and change directory to prolog search, e.g.
Start prolog and load puzzle15.pl and ucsdijkstra.pl by typing
Then invoke the search for the specified start10 position by typing
start10(S), solve(S,P,G,N), showsol(P).
When the answer comes back, just hit Enter/Return. This version of UCS
uses Dijkstra’s algorithm which is memory efficient, but is designed to return
only one answer. Note that the length of the path is returned as G, and the
total number of states expanded during the search is returned as N.
(a) Draw up a table with four rows and five columns. Label the rows as UCS,
IDS, A* and IDA*
, and the columns as start10, start20, start27,
start35 and start43. Run each of the following algorithms on each of
the 5 start states:
In each case, record in your table the number of nodes generated during
the search. If the algorithm runs out of memory, just write “Mem”
in your table. If the code runs for five minutes without producing output,
terminate the process by typing Control-C and then “a”, and write
“Time” in your table.
(b) Briefly discuss the time and space efficiency of these four algorithms.
Question 2: Deceptive Starting States (1.5 marks)
Consider the two starting states start49 and start51.
(a) Print state start49 and calculate its heuristic value by typing
start49(S), showpos(S), h(S,H).
Do the same for start51 and copy the result into your solutions.
(b) Use [idastar] to search, starting from start51, and report the number
of nodes that are expanded.
(c) When [idastar] is used to search from start49, the number of nodes
expanded is 178880187. Briefly explain why the search from start49
expands so many more nodes than the search from start51, even though
the true path length is very similar.
Question 3: Heuristic Path Search (2 marks)
In this question you will be exploring an Iterative Deepening version of the
Heuristic Path Search algorithm discussed in the Week 4 Tutorial. Draw up
a table in the following format: