C语言代写｜Assignment 2 Parallel and Distributed Computing

这是一篇澳洲的C语言TSP旅行商问题+报告代码代写

Assignment Description

Objective

This assignment requires you to implement a Branch-and-Bound program for the Travelling Salesman Problem (TSP) in the C programming language, frst sequentially, and then in parallel using MPI. This problem is representative of combinatorial optimization problems. The Branch-and-Bound technique is an exhaustive evaluation technique that tries to make use of knowledge of the underlying problem to reduce the amount of computation.

The Traveling Salesman Problem (TSP)

The objective of TSP is to fnd the shortest route for a traveling salesman so that the salesman visits every one of a set of cities exactly once. (Note: the salesman doesn’t return home in the version you are implementing). This is a hard combinatorial optimization problem since for N cities there are at most N! possible routes (we assume that the cities are fully connected). The input to the problem is given in the form of a matrix. An element of the matrix, dli[I] gives the distance between city i and cityj.

The input to your program is a fle organized as fllws:

N
d[1][2]
d[1][3] d[2][3]
d[1][4] d[2][14] d[3][4]
d[1][N] d[2]IN] d[3][N] .. d[N-1][N]

where N is the number of cities, and d[)lj] is an integer giving the distance between cities i and j. The output from the program should be an ordered list of cities (numbers between 1 and N). Constraint Programming Solutions to Combinatorial Optimization Problems First, consider a simple exhaustive evaluation as a way of solving the TSP. One way you might think about evaluating every possible route is to construct a tree that describes all of the possible routes from the frst city, as shown in the fgure for a four city example.

The fle for this problem would be:
4
5
40 9
1168

So: N= 4, d[1][2] = 5, d[1][3] = 40, d[2][]3]= 9, d[1]14]= 11, d[2][4] = 6, d[31[4]=8

All of the possible routes can be found by traveling from the root to a different leaf node three times, once for each unique path and then back to the root. For example, by taking the middle branch from the root node and the right branch after that, the route 1→3→4→2 is produced, and has a distance of 40+8+6 = 54. There are six unique root to leaf paths in this tree. A simple exhaustive evaluation for this example would then be to fllw the six root to leaf paths and determine the total distance for each path by adding up the distances indicated by each edge in the tree. The route with the smallest distance is then chosen. A better way to traverse each tree is to do it recursively. Here the summation of the earlier parts of each route is not repeated every time that route portion is reused in several routes. The approach uses this type of problem formulation, but with some added itelligence. It uses more knowledge of the problem to prune the tree as much as possible so that less evaluation is necessary.

The basic approach works as follows:

1. Evaluate one route of the tree in its entirety, (say1→2→3→4) and determine the distance of that path. Call this distance the current “constraint” of the problem. The constraint for this path in the above treeis5+9+8= 22.

2. Next, suppose that a second path is partially evaluated, say path1→3, and the partial distance, 40, is already greater than the above margin. If that is the case, then there is no need to complete the traversal of any part of the tree from there on, because all of those possible routes (in this case there are two) must have a distance greater than the bound. In this way the tree is pruned and therefore does not have to be entirely traversed.

3. Whenever any route is discovered that has a better distance than the current constraint, then the constraint is updated to this new value. The approach always remembers the best path it has found so far, and uses that to prevent search down parts of the tree that couldn’t possibly produce better routes.

You can see that for larger trees, this could result in the removal of many possible evaluations.

The objective is to obtain the best speedup possible.

Your program should accept the command-line arguments p and i to specify the number of processors used and the input file respectively. It should also use the above input fle format.

Your programs MUST use command line arguments for input, following this format:

For the sequential implementation:

i- the input fle, in the format specifhed above.

log – if this is given, logging is enabled. If it is omitted, logging is disabled.

So, to run your sequential implementation, you must be able to use the following command, replacing “input fle.txt” with an appropriate input fle:
$./tsp. sequential input. fle.txt
with logging:
$./tsp_ sequential input. fle.txt log
For the parallel implementation:
●p- number of processors
●i- input fle, in the format specifed above
●log: If the word “log” is given on the command line, logging is enabled. If it is not, logging is disabled.
So, to run your parallel implementation, you must be able to use the fllowing command, replacing “input. fle.txt” with an appropriate input fle, and
“num_ processes” with the number of processes your program will use:
$ mpiexec -np num. processes ./tsp. parallel input _fle
with logging:
$ mpiexec -np num. processes ./tsp. parallel input_ fle log
NOTE: this means that you do not need read in the number of processes explicitly in your program, as MPI does this for you.