Arti cial Intelligence (CSC 662) – Spring 2020 Instructor:
Programming Assignment
Submission deadline: Apr. 3, 2020 – noon { Oral presentation: Apr. 6, 2020
This assignment has 2 questions, for a total of 20 points.
Given a list of cities and the distances between each pair of cities, the traveling salesman problem (TSP) asks to nd the shortest possible route that visits each city only once and returns to the origin city.
The TSP can be solved via the minimum spanning tree (MST) heuristic, which is used to estimate the cost of completing a tour, given that a partial tour has already been constructed. The MST cost of a set of cities is the smallest sum of the link costs of any tree that connects all the cities. Use Prim’s algorithm for constructing the MST.
1. For each of the following questions, give a pseudocode of the proposed algorithm, and analyze its time and space complexities.
(a)
(b)
3 points
3 points
Design an algorithm to solve the TSP based on A* algorithm.
Design an algorithm to solve the TSP based on a hill-climbing approach.
(c) 3 points TSP.
Design an RBFS (Recursive Best First Search) algorithm to solve the
2. Use one of the following programming languages for your implementation: Java, Python, C++, C, or MATLAB.
(a)
8 points Implement the proposed algorithms and evaluate their performances on:
i. The datasets a280.xml and att48.xml.
(b) 3 points Compare the performance results of the three algorithms and discuss their strength and weaknesses.
The les to submit are:
– Program source code for each algorithm.
– A detailed report (yourName.pdf) of your answers to the questions, including pseu-docode of the algorithms, performance evaluation and discussion of the results.
Your code must compile without any error or warning and run. Put all the required les in a compressed le (yourName.zip) and send it by email to menai@ksu.edu.sa.
Your source code and your report will be checked by a plagiarism detection system.