Comp3411/9414/9814: Artificial Intelligence- Heuristics Assessment Answer

1HAAD

Computer Assignment Help:

Task:

Question 1: Search Algorithms for the 15-Puzzle

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(Pos),solve(Pos,Sol,G,N),showsol(Sol).

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, start12, start20,start30 and start40. Run each of the following algorithms on each ofthe 5 start states:
(i) [ucsdijkstra]
(ii) [ideepsearch]
(iii) [astar]
(iv) [idastar]

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. Note that you will need to re-start prolog each time you switch to a different search.

(b) Briefly discuss the efficiency of these four algorithms (including both time and memory usage).

Question 2: Heuristic Path Search for 15-Puzzle 

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:

The top row of the table has been filled in for you (to save you from running some rather long computations).
(a) Run [greedy] for start50, start60 and start64, and record the values returned for G and N in the last row of your table (using the Manhattan
Distance heuristic defined in puzzle15.pl).

(b) Now copy idastar.pl to a new file heuristic.pl and modify the code of this new file so that it uses an Iterative Deepening version of the Heuristic
Path Search algorithm discussed in the Week 4 Tutorial Exercise, with
w = 1.2 .

In your submitted document, briefly show the section of code that was
changed, and the replacement code.

(c) Run [heuristic] on start50, start60 and start64 and record the values of G and N in your table. Now modify your code so that the value of w is 1.4, 1.6 ; in each case, run the algorithm on the same three start states and record the values of G and N in your table.

(d) Briefly discuss the tradeoff between speed and quality of solution for these five algorithms.