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.

unzip prolog_search.zip

cd prolog_search

Start prolog and load puzzle15.pl and ucsdijkstra.pl by typing

[puzzle15].

[ucsdijkstra].

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:

(i) [ucsdijkstra]

(ii) [ideepsearch]

(iii) [astar]

(iv) [idastar]

1

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:

Attachments:

assign2.pdf