TSP Assignment Instructions

User Manual:

Open the PDF directly: View PDF .
Page Count: 7

AI Assignment - I

Travelling Salesman Problem

Problem

Statement

●Given a file containing the

coordinates of cities and the

distances between them, write

a program to find a good tour

in the allotted time. The cost of

the tour found will figure in the

evaluation

Overview

Assignment deadline

October 4, 2016

Interim deadline(for trial run)

October 10, 2016

Programming languages

●C/C++

●Java

●Python

Format for file upload

Group-No.tar.gz (ex: 1.tar.gz)

General Instructions : Submit a Makefile

Please do not place the makefile in nested folders!

Makefile should produce an executable file named tsp

Makefile making should produce an executable file named

tsp.class

Makefile is not required. Please add the Linux hashbang

#!/usr/bin/python to the file named tsp.

General Instructions :

●You are allowed to read from stdin and write to stdout.

○Example : java tsp < input file > output file (for Java users)

●You are not allowed to run your code for more than 5 minutes.

Make sure that you flush stdout periodically, so that your tours are

written to stdout before it gets killed at time-out (5 min).

●If you get better tour than the last tour, you should write it to

stdout. The last line written to stdout will be considered as your

final tour.

Grading will be completely based on the cost of the tour!

General Instructions : Input from stdin

●Sample input : 100 - 500 cities (Euclidean and Non-Euclidean)

(Input format)

General Instructions : Output to stdout

●Write the space separated indexes of the cities

●Each tour should be in single line.

●Avoid the cycle (Coming back to the origin city),

○Example: 2 6 3 1 8 9 7 5 4 2

(Output format)