Find Jobs
Hire Freelancers

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

$30-75 USD

Terminado
Publicado hace casi 21 años

$30-75 USD

Pagado a la entrega
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
ID del proyecto: 2932726

Información sobre el proyecto

1 propuesta
Proyecto remoto
Activo hace 21 años

¿Buscas ganar dinero?

Beneficios de presentar ofertas en Freelancer

Fija tu plazo y presupuesto
Cobra por tu trabajo
Describe tu propuesta
Es gratis registrarse y presentar ofertas en los trabajos
Adjudicado a:
Avatar del usuario
See private message.
$63,75 USD en 14 días
5,0 (18 comentarios)
3,5
3,5

Sobre este cliente

Bandera de UNITED STATES
United States
0,0
0
Miembro desde may 6, 2003

Verificación del cliente

¡Gracias! Te hemos enviado un enlace para reclamar tu crédito gratuito.
Algo salió mal al enviar tu correo electrónico. Por favor, intenta de nuevo.
Usuarios registrados Total de empleos publicados
Freelancer ® is a registered Trademark of Freelancer Technology Pty Limited (ACN 142 189 759)
Copyright © 2024 Freelancer Technology Pty Limited (ACN 142 189 759)
Cargando visualización previa
Permiso concedido para Geolocalización.
Tu sesión de acceso ha expirado y has sido desconectado. Por favor, inica sesión nuevamente.