Find Jobs
Hire Freelancers

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

$30-75 USD

已完成
已发布将近 21 年前

$30-75 USD

货到付款
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: 2932726

关于此项目

1条提案
远程项目
活跃21 年前

想赚点钱吗?

在Freelancer上竞价的好处

设定您的预算和时间范围
为您的工作获得报酬
简要概述您的提案
免费注册和竞标工作
颁发给:
用户头像
See private message.
$63.75 USD 在14天之内
5.0 (18条评论)
3.5
3.5

关于客户

UNITED STATES的国旗
United States
0.0
0
会员自5月 6, 2003起

客户认证

谢谢!我们已通过电子邮件向您发送了索取免费积分的链接。
发送电子邮件时出现问题。请再试一次。
已注册用户 发布工作总数
Freelancer ® is a registered Trademark of Freelancer Technology Pty Limited (ACN 142 189 759)
Copyright © 2024 Freelancer Technology Pty Limited (ACN 142 189 759)
加载预览
授予地理位置权限。
您的登录会话已过期而且您已经登出,请再次登录。