CSE 471/598 – Introduction to Artificial intelligence

Project I – Requirement Specifications

Problem Solving Agent for Traveling Salesman Problem

Deadline: 19th March (Thursday)

 

In this project you will solve the Traveling Salesman Problem using A* search algorithm with Minimum Spanning Tree heuristic.

 

Traveling Salesman Problem (TSP)

The TSP problem is defined as follows: Given a set of cities and distances between every pair of cities, find the shortest way of visiting all the cities exactly once and returning to the starting city.

 

You can imagine the cities as nodes in a completely connected graph and distances as edge cost between the cities. Now the problem is transformed to finding the shortest tour of the graph. This is a well known NP-Complete problem and there are many different heuristics available to obtain approximate solutions.

 

In this project you are going to use A* search strategy to find the optimal solution to the problem and use the Minimum Spanning Tree as the heuristic function.

 

Your program will read an input file that specifies the cities and distances between them and you need to write the solution (shortest tour) in an output file. The format for the input and output files is given below (a sample input file).  

 

A* for solving TSP

 

The following shows one way of solving the problem. You are encouraged to develop your very own implementation to solve the problem.

 

Initial State: Agent in the start city and has not visited any other city

Goal State: Agent has visited all the cities and reached the start city again

Successor Function: Generates all cities that have not yet visited

Edge-cost: distance between the cities represented by the nodes, use this cost to calculate g(n).

h(n): distance to the nearest unvisited city from the current city + estimated distance to travel all the unvisited cities (MST heuristic used here) + nearest distance from an unvisited city to the start city. Note that this is an admissible heuristic function.

 

You may consider maintaining a list of visited cities and a list of unvisited cities to facilitate computations.

 

There are several heuristics proposed in literature to estimate distance needed to travel the remaining unvisited cities. We will use the Minimum Spanning Tree heuristic.

 

 

Minimum Spanning Tree (MST)

A spanning tree of a graph is a subgraph that contains all the vertices of the graph and is a tree. A graph may have many spanning trees; and the minimum spanning tree is the one with the minimum sum of the edge costs of the tree.

 

There are many algorithms developed for finding the minimum spanning tree of a graph. You can use any of the algorithms for this purpose. One of the algorithms that find the minimum spanning tree is described below.

 

Algorithm for MST

It is a greedy approach to find the MST of a graph G.

 
    sort the edges of G in increasing order of cost
    keep a subgraph S of G, initially empty
    for each edge e in sorted order
if the endpoints of e are disconnected in S (i.e., does not form a cycle)
           add e to S
    return S

 

The above approach is called Kruskal’s algorithm which executes in O(|E|log|E|) complexity, where |E| is the number if edges in the graph.

 

The A* algorithm should find the MST of the unvisited cities and use the cost of the minimum spanning tree in computing h(n) shown above. The cost of a spanning tree is the sum of the edge costs of the tree.

 

Input File Format

N

City1 City2 City3 … CityN

d11 d12 d13 … d1N

d21 d22 d23 … d2N

…………………….

………………….....

dN1 dN2 ……..dNN

 

where

N – number of cities

City1 … CityN – name of N cities

dij – distance between Cityi and Cityj.

 

Note that dij = dji and all the distances are integers. City1 is the initial city.

 

Output File Format

City1

City3

……

CityN

City2

……

City1

Time Taken for Execution: 1230 sec

 

Note: The output file specifies the shortest tour with each city in a separate line.

 

Submission and Grading

You need to submit the soft copy of the project via myASU Assignments section and turn in a hardcopy report either in class or  at the CSE department office. The report should be brief and contain the following:

  • Problem Statement
  • Design – Data Structure Design and Algorithm design
  • Sample Input and Output
  • Discussion on any one aspect of the project of your interest. It could be anything like why the MST heuristic is admissible, other admissible heuristics for the problem, advantage/disadvantage of using A* as the search algorithm, any other better search strategy for the problem.

 

The distribution of grades for the project:

Code – 60%

Project Report – 40%