College OS C Project -- Sequentially generate all possible solutions to the minimum cost path

Project 2 You need to write a program that computes the minimum cost path that goes through n cities. The path has to go through every city once and only once. The path can start with any city and end on any city. The cost to travel between a pair of cities is described in a matrix. The cost to go from city j to city k is in row j, column k of the matrix. The cost to go from city j to city k may be different than the cost to travel from city k to city j, therefore, the matrix does not need to be symmetric. This is a hard problem to solve. Formally it is a NP-hard problem. No good algorithms currently exist to solve this problem efficiently. (In fact, no efficient algorithms currently exist that can, provably, get close to the optimal solutions.) We are going to solve it with an inefficient algorithm. To speed up this inefficient algorithm we are going to use various techniques including threads. Part I (20%) Sequentially generate all possible solutions to the minimum cost path problem. For each solution compute the cost. Return a solution with minimum cost. Each solution is a permutations of the cities. For example, if we have 5 cities, 3-4-0-1-2 is a path through the cities. We need to generate and test the cost of every permutation of cities. A good systematic way to do that is to generate the permutations is lexicographic order. For example, if n=3 0,1,2 : 0,2,1 : 1,0,2 : 1,2,0 : 2,0,1 : 2,1,0 I will give you a function next_permutation that takes a permutation as input and generates the next lexicographic permutation. If there are no more permutations next_permutation returns 0. I will give you other various functions including build_matrix that builds the cost matrix. The distances in the matrix are filled with random floats uniformly chosen from 1 to 10. The main diagonal is filled with 0 since these locations do not correspond to costs. Before you call build_matrix you need to call init_random u ## Deliverables 1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done. 2) Installation package that will install the software (in ready-to-run condition) on the platform(s) specified in this bid request. 3) Complete ownership and distribution copyrights to all work purchased. The functions you need (which are described in the above document) are in the following files: path_lib1.h, path_lib1.c. Do not modify either of these files. We reserve the right to make changes in the files. If we make changes in this file we will place the new file on this website and give them a new version number. Always use the highest version number. Your simulation programs should use the include preprocessor directive to include the header file path_lib.h. This will allow the C compiler to do proper type checking for these functions. In addition, when you compile your program, these functions must be linked with your code. For example, for part II use the following command: remus% cc -o path2 path2.c path_lib1.c -lm -mt For part III use: remus% cc -o server server.c path_lib1.c -lm -lsocket -lnsl remus% cc -o path3 path3.c path_lib1.c -lm -lsocket -lnsl The -lm parameter is needed since path_lib1.c uses math functions that need to be linked into the executable. The -mt is need to use the pthreads threading library of Sun. The -lsocket and -lnsl are needed for sockets. Also, use cc instead of gcc. I've noticed some problems in gcc with threads on remus and we want to use a couple of Sun specific functions. Here are some sample programs to help with the libraries you must use to complete your projects. The programs include some documentation, but you should use the man pages to get additional information. This contains a program thread.c that should help you work with threads. I've added some code to return performance data. Here are some simple socket programs. You need to run server.c as a server on romulus and run client.c as a client on remus. Specifying the number of cities and a seed to the client causes the random matrix to be sent from remus to romulus. Romulus then sends back a simple path. You need to link in path_lib1.c to get these programs to compile. Here is an Sun executable version of path1 that you can use to verify your code works. Here is an Sun executable version of path4 that you can use to verify your code works for larger problems. ## Platform Unix, telnet