Homework 5 Solving Travelling Salesman Problem Using Pthread

Computer Architecture I ShanghaiTech University

Travelling Salesman Problem

Introduction of TSP

The travelling salesman problem (TSP) asks the following question:

"Given a list of cities and the distances between each pair of cities,
what is the shortest possible route that visits each city and returns to the origin city?"

(You want to "link" these cities to form a shortest route)

It is actually an NP-complete problem (there's NO polynomial algrithms to solve this problem), It is important in operations research and theoretical computer science and also has many kinds of applications such as planning, logistics, and the manufacture of microchips, etc...

Check this wikipedia link for more details.

Problem Setup

Welcome to the NP-complete world, in this homework, you will try to solve this really hard problem use some strategy and accelerate using pthreads. You are a travelling salesman, given a map and start point, and you need to find the shortest route which starts at the given point, goes over all these cities only once (except the start city) and finally goes back.

You should implement a travelling salesman problem(TSP) solver in C.


The first line of input contains 3 integers t,n and s
The next n lines represent a symmetric adjacency matrix A (because the edges are undirected).
A[i][j] represents the distance between the cities i and j, for all valid i, j, 1000>=A[i][j]>=0 and they are all integers.
A distance of 0 means their is no road between city i,j

For example:

2 4 0
0 100 100 100
100 0 35 25
100 35 0 30
100 25 30 0


One single integer tells the total length of the route if it's feasible, -1 otherwise. The following example won't necessary be the right answer.


Submission and Grading



Submission in Autolab is not yet open - Should be open soon.

Last Modified: Apr. 11th, 2018