Homework 5 Solving Travelling Salesman Problem Using Pthread

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?"

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

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

Input

• t means the number of threads (main thread is not included), 0< t <=20
• n stands for the total number of cities
• s stands for the start point, 0 <= s < n
• n will be guaranteed to<= 10 in Autolab testcases.

For example:

Output

Requirement

• You only allowed to inclue: stdio.h stdlib.h string.h pthread.h
• We will check memory leak using valgrind.
• Comment Rule. You need to have MEANINGFUL comments no less than 25% of the total lines of code you wrote.
• You must create t number of threads and all of them should do reasonable things (Otherwilse we will deduct 50% of your points).
• Of course your program should output the precise value, so Randomized Algorithms and k-Approximation Algorithms will be very likely to fail the test cases.
• Your code must stay in 2 files tsp.c and tsp.h, which will be created by yourself. We will not offer a code template this time.
• We will use the following Makefile:

  CC=gcc
      CFLAGS=-Wpedantic -Wall -Wextra -Werror -std=c89 -pthread
  
      tsp.o: tsp.c tsp.h
        ${CC} ${CFLAGS} tsp.c -o tsp.o

• Memory limit will be 40960KB in Autolab.
• You can test your memory by type ulimit -v 40960 in Terminal and then run ./tsp.o < input_file_name
.

Submission and Grading

• Submit to Autolab with a file named hw5.tar, containing exactly two files: tsp.c tsp.h, it should produce a tsp.o file using our Makefile and can be tested using this command ./tsp.o < input_file_name
• Autolab will just test your code with some small <= 10 testcases, to verify the correctness of your program and it will contribute 60% of the whole points.
• After the autograding deadline, we will run your code on a larger server with higher performance with a bigger testcase to test your speed.
• AC all the testcases in Autolab DOES NOT guarentee your correctness in the larger testcases on the bigger server, if you have something wrong with our code and use some randomized Algorithm or approximation algrithms.
• For the other 40% of points: if you fail on the bigger testcases (like find a sub-optimal sulution), you will got 0 points, for programs which output the right answer, the fastest 20 people will get full points, the top 21~50 will get 80%, top 51~80 get 60%, others get 40%

Hints

• Implement a Brute Force Algorithm (Generate and test all the (n-1)! permutations of routes) and optimize it using pthread might be a safe and reasonable choice.
• Consider a cleverer inplementation of Brute Force algorithm when you generate permutations. (Generate it online or use recursive search.)
• You can also try to model it as Linear Programming
• Dynamic Programming is fast but you may consider how to deal with data concurrency problem, it's very hard to parallelize.
• Approximation and Randomized Algorithm is not recommanded, but not restricted. Though it is more feasible and much faster in practice but it may find suboptimal sulutions.
• If you implement some advanced algorithms and parallelize it additionaly, you can come to jiangchy & nianzhl's office hour, we may give you some bonus if you really did a good job.
• This homework is designed to practice pthread, make full use of threads please, otherwise we will deduct your points.

Submission

Last Modified: Apr. 11th, 2018