CSE 471/598 – Introduction to Artificial intelligence

Project I – Requirement Specifications

Problem Solving Agent for Traveling Salesman Problem

Deadline: October 6th, 2004 Wednesday 5:00pm

Please keep looking at myASU for discussions and clarifications.

 

 

In this project you will solve the Traveling Salesman Problem using various search algorithms.

 

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 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 generally different heuristics are used to solve this problem.

 

Your LISP program should contain a function named “tsp” which should take three parameters, the input file as the first parameter, the name of the start city as the second parameter, and the name of the search method as the third parameter. The function then should return three values the first is the list of the shortest tour, second is the cost of the tour and the third value should be the time taken for the search.

 

The format for the input file and the output values is given below.  

 

The search methods which your program should support are:

 

  1. Depth First Search (function argument- DFS)
  2. Breadth First Search (function argument- BFS)
  3. Iterative Depth First Search (function argument- IDFS)
  4. Uniform Cost Search (function argument- UCS)
  5. (Extra Credit 25  points – worth 4 final points) Minimum Spanning Tree heuristic (function argument- MST)

 

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

 

In the 5th part the heuristic function should be

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.

Minimum Spanning Tree (MST)

A spanning tree of a graph is a sub-graph 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 search 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.

 

(Spaces are used to separate the name of the cities and the cost matrix given is complete.)

Input File Format

City1 City2 City3 … CityN

d11 d12 d13 … d1N

d21 d22 d23 … d2N

…………………….

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

dN1 dN2 ……..dNN

 

where

City1 … CityN – name of N cities

dij – distance between Cityi and Cityj.

 

Note that dij = dji and all the distances are integers. A value of 0 between two cities indicates that there is no path connecting them.

 

The function “tsp” will be called in the following format:

(tsp “c:\\test.tsp” ‘City1 ‘DFS)

 

And the values returned should be:

 

(City1 City3 …..  CityN)   1000  20

 

Project Submission Guidelines

You need to submit the soft copy of the project via myASU Assignments section.

  • The LISP file should be named {last name}-{first-name}.lisp
  • Submit the file through Assignment section in myASU.
  • Please make sure that the file is in simple text format and not in document (Microsoft Word or some other document) format.
  • The first line in the file should be your name (E.g., it’s a comment).
  • If you want to label portions of your code as solution to part one, part two, etc., or you want to write the problem statement in the lisp file (it is not needed, you can do it if you feel it is convenient for you), please make sure that they are all commented.
  • There should be no syntax errors in the program (like forgotten closing brackets, misplaced semicolon unmatched double quotes, etc. In other words, one can run you program without your presence.)
  • Please try to comment whatever code you have written for debugging purpose. The function execution calls like (tsp “C:\\input.txt” ‘Bavaria ‘DFS) should all be commented.
  • Any malicious (or evil) coding will be severely punished.

 

Also, you are supposed to 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
  • Discussion on any one aspect of the project of your interest. E.g., 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.

 

Grading

 

The distribution of grades for the project:

Code – 80%

Project Report – 20%