首页
编程语言
数据库
网络开发
Algorithm算法
移动开发
系统相关
金融统计
人工智能
其他
首页
>
> 详细
代写COMP528、代做 Python ,java 编程
In this assignment, you are asked to implement 2 algorithms for the Travelling Salesman
Problem. This document explains the operations in detail, so you do not need previous
knowledge. You are encouraged to start this as soon as possible. Historically, as the dead?line nears, the queue times on Barkla grow as more submissions are tested. You are also
encouraged to use your spare time in the labs to receive help, and clarify any queries you
have regarding the assignment.
1 The Travelling Salesman Problem (TSP)
The travelling salesman problem is a problem that seeks to answer the following question:
‘Given a list of vertices and the distances between each pair of vertices, what is the shortest
possible route that visits each vertex exactly once and returns to the origin vertex?’.
(a) A fully connected graph (b) The shortest route around all vertices
Figure 1: An example of the travelling salesman problem
The travelling salesman problem is an NP-hard problem, that meaning an exact solution
cannot be solved in polynomial time. However, there are polynomial solutions that can
be used which give an approximation of the shortest route between all vertices. In this
assignment you are asked to implement 2 of these.
1.1 Terminology
We will call each point on the graph the vertex. There are 6 vertices in Figure 1.
We will call each connection between vertices the edge. There are 15 edges in Figure 1.z
We will call two vertices connected if they have an edge between them.
The sequence of vertices that are visited is called the tour. The tour for Figure 1(b) is
(1, 3, 5, 6, 4, 2, 1). Note the tour always starts and ends at the origin vertex.
A partial tour is a tour that has not yet visited all the vertices.
2023-2024 1
COMP528
2 The solutions
2.1 Preparation of Solution
You are given a number of coordinate files with this format:
x, y
4.81263062736921, 8.34719930253777
2.90156816804616, 0.39593575612759
1.13649642931556, 2.27359458630845
4.49079099682118, 2.97491204443206
9.84251616851393, 9.10783427307047
Figure 2: Format of a coord file
Each line is a coordinate for a vertex, with the x and y coordinate being separated by a
comma. You will need to convert this into a distance matrix.
0.000000 8.177698 7.099481 5.381919 5.087073
8.177698 0.000000 2.577029 3.029315 11.138848
7.099481 2.577029 0.000000 3.426826 11.068045
5.381919 3.029315 3.426826 0.000000 8.139637
5.087073 11.138848 11.068045 8.139637 0.000000
Figure 3: A distance matrix for Figure 2
To convert the coordinates to a distance matrix, you will need make use of the euclidean
distance formula.
d =
q (xi ? xj )
2 + (yi ? yj )
2
(1)
Figure 4: The euclidean distance formula
Where: d is the distance between 2 vertices vi and vj
, xi and yi are the coordinates of the
vertex vi
, and xj and yj are the coordinates of the vertex vj
.
2023-2024 2
COMP528
2.2 Cheapest Insertion
The cheapest insertion algorithm begins with two connected vertices in a partial tour. Each
step, it looks for a vertex that hasn’t been visited, and inserts it between two connected
vertices in the tour, such that the cost of inserting it between the two connected vertices is
minimal.
These steps can be followed to implement the cheapest insertion algorithm. Assume that the
indices i, j, k etc. are vertex labels, unless stated otherwise. In a tiebreak situation, always
pick the lowest index or indices.
1. Start off with a vertex vi
.
Figure 5: Step 1 of Cheapest Insertion
2. Find a vertex vj such that the dist(vi
, vj ) is minimal, and create a partial tour (vi
, vj
, vi)
Figure 6: Step 2 of Cheapest Insertion
3. Find two connected vertices (vn, vn+1), where n is a position in the partial tour, and
vk that has not been visited. Insert vk between vn and vn+1 such that dist(vn, vk) +
dist(vn+1, vk) ? dist(vn, vn+1) is minimal.
2023-2024 3
COMP528
Figure 7: Step 3 of Cheapest Insertion
4. Repeat step 3 until all vertices have been visited, and are in the tour.
Figure 8: Step 4 of Cheapest Insertion
Figure 9: Final step and tour of Cheapest Insertion. Tour Cost = 11
2.3 Farthest Insertion
The farthest insertion algorithm begins with two connected vertices in a partial tour. Each
step, it checks for the farthest vertex not visited from any vertex within the partial tour, and
then inserts it between two connected vertices in the partial tour where the cost of inserting
it between the two connected vertices is minimal.
2023-2024 4
COMP528
These steps can be followed to implement the farthest insertion algorithm. Assume that the
indices i, j, k etc. are vertex labels unless stated otherwise. In a tiebreak situation, always
pick the lowest index(indices).
1. Start off with a vertex vi
.
Figure 10: Step 1 of Farthest Insertion
2. Find a vertex vj such that dist(vi
, vj ) is maximal, and create a partial tour (vi
, vj
, vi).
Figure 11: Step 2 of Farthest Insertion
3. For each vertex vn in the partial tour, where n is a position in the partial tour, find an
unvisited vertex vk such that dist(vn, vk) is maximal.
Figure 12: Step 3 of Farthest Insertion
2023-2024 5
COMP528
4. Insert vk between two connected vertices in the partial tour vn and vn+1, where n is
a position in the partial tour, such that dist(vn, vk) + dist(vn+1, vk) ? dist(vn, vn+1) is
minimal.
Figure 13: Step 4 of Farthest Insertion
5. Repeat steps 3 and 4 until all vertices have been visited, and are in the tour.
Figure 14: Step 3(2) of Farthest Insertion
Figure 15: Step 4(2) of Farthest Insertion
2023-2024 6
COMP528
Figure 16: Final step and tour of Farthest Insertion. Tour Cost = 11
3 Running your programs
Your program should be able to be ran like so:
./
. exe
Therefore, your program should accept a coordinate file, and an output file as arguments.
Note that C considers the first argument as the program executable.
Both implementations should read a coordinate file, run either cheapest insertion or farthest
insertion, and write the tour to the output file.
3.1 Provided Code
You are provided with code that can read the coordinate input from a file, and write the
final tour to a file. This is located in the file coordReader.c. You will need to include this
file when compiling your programs.
The function readNumOfCoords() takes a filename as a parameter and returns the number
of coordinates in the given file as an integer.
The function readCoords() takes the filename and the number of coordinates as parameters,
and returns the coordinates from a file and stores it in a two-dimensional array of doubles,
where coords[i ][0] is the x coordinate for the ith coordinate, and coords[i ][1] is the y
coordinate for the ith coordinate.
The function writeTourToFile() takes the tour, the tour length, and the output filename
as parameters, and writes the tour to the given file.
2023-2024 7
University of Liverpool Continuous Assessment 1 COMP528
4 Instructions
? Implement a serial solution for the cheapest insertion and the farthest insertion. Name
these: cInsertion.c, fInsertion.c.
? Implement a parallel solution, using OpenMP, for the cheapest insertion and the far?thest insertion. Name these: ompcInsertion.c, ompfInsertion.c.
? Create a Makefile and call it ”Makefile” which performs as the list states below. With?out the Makefile, your code will not grade on CodeGrade (see more in section 5.1).
– make ci compiles cInsertion.c and coordReader.c into ci.exe with the GNU com?piler
– make fi compiles fInsertion.c and coordReader.c into fi.exe with the GNU compiler
– make comp compiles ompcInsertion.c and coordReader.c into comp.exe with the
GNU compiler
– make fomp compiles ompfInsertion.c and coordReader.c into fomp.exe with the
GNU compiler
– make icomp compiles ompcInsertion.c and coordReader.c into icomp.exe with
the Intel compiler
– make ifomp compiles ompfInsertion.c and coordReader.c into ifomp.exe the Intel
compiler.
? Test each of your parallel solutions using 1, 2, 4, 8, 16, and 32 threads, recording
the time it takes to solve each one. Record the start time after you read from the
coordinates file, and the end time before you write to the output file. Do all testing
with the large data file.
? Plot a speedup plot with the speedup on the y-axis and the number of threads on the
x-axis for each parallel solution.
? Plot a parallel efficiency plot with parallel efficiency on the y-axis and the number of
threads on the x-axis for each parallel solution.
? Write a report that, for each solution, using no more than 1 page per solution,
describes: your serial version, and your parallelisation strategy
? In your report, include: the speedup and parallel efficiency plots, how you conducted
each measurement and calculation to plot these, and sreenshots of you compiling and
running your program. These do not contribute to the page limit
2023-2024 8
COMP528
? Your final submission should be uploaded onto CodeGrade. The files you
upload should be:
– Makefile
– cInsertion.c
– fInsertion.c
– ompcInsertion.c
– ompfInsertion.c
– report.pdf
5 Hints
You can also parallelise the conversion of the coordinates to the distance matrix.
When declaring arrays, it’s better to use dynamic memory allocation. You can do this by...
int ? o n e d a r ra y = ( int ?) malloc ( numOfElements ? s i z e o f ( int ) ) ;
For a 2-D array:
int ?? twod a r ra y = ( int ??) malloc ( numOfElements ? s i z e o f ( int ? ) ) ;
for ( int i = 0 ; i < numOfElements ; i ++){
twod a r ra y [ i ] = ( int ?) malloc ( numOfElements ? s i z e o f ( int ) ) ;
}
5.1 Makefile
You are instructed to use a MakeFile to compile the code in any way you like. An example
of how to use a MakeFile can be used here:
{make command } : { t a r g e t f i l e s }
{compile command}
c i : c I n s e r t i o n . c coordReader . c
gcc c I n s e r t i o n . c coordReader . c ?o c i . exe ?lm
Now, in the Linux environment, in the same directory as your Makefile, if you type ‘make ci‘,
the compile command is automatically executed. It is worth noting, the compile command
must be indented. The target files are the files that must be present for the make command
to execute.
2023-2024 9
COMP528
6 Marking scheme
1 Code that compiles without errors or warnings 15%
2 Same numerical results for test cases 20%
3 Speedup plot 10%
4 Parallel Efficiency Plot 10%
5 Parallel efficiency up to 32 threads 15%
6 Speed of program 10%
11 Clean code and comments 10%
12 Report 10%
Table 1: Marking scheme
7 Deadline
2023-2024 10
联系我们
QQ:99515681
邮箱:99515681@qq.com
工作时间:8:00-21:00
微信:codinghelp
热点文章
更多
data程序辅导 、讲解 c/c++编程...
2024-05-17
data程序辅导 、讲解 python编...
2024-05-17
program讲解 、c/c++,python程...
2024-05-17
辅导 math 3333 3.0 - winter ...
2024-05-17
讲解 seng6110 programming as...
2024-05-17
辅导 seng6110 object oriente...
2024-05-17
辅导 comp828: statistical pr...
2024-05-17
讲解 culture and society调试...
2024-05-17
讲解 comp 4911 winter 2024 a...
2024-05-17
讲解 lh physical iiib / 03 3...
2024-05-17
讲解 3032ict big data analyt...
2024-05-17
辅导 comp4702 report辅导 留学...
2024-05-17
辅导 fin2020 hw6辅导 c/c++编...
2024-05-17
讲解 civ4100: autonomous veh...
2024-05-17
辅导 feeg6008 advanced photo...
2024-05-17
讲解 acc207 econometrics in ...
2024-05-17
辅导 npsc1003 writing portfo...
2024-05-17
讲解 math 3333 3.0 section a...
2024-05-17
辅导 busn 37103 data-driven ...
2024-05-17
辅导 218.203 measurement pri...
2024-05-17
热点标签
fina211
dts002tc
n1574
ecn6620
mth208
ifb209tc
accg8126
mgt6128
eco320
soft3202
n1577
n1587
elec9731
stsci 4060
ierg2080
ai4003
125.701
econ333
sesm6050
cse101
fin2020
bpln0025
ebu4201
comp30023
swen30006
comp809
phys5032
cpt304
econ20120
fit3152
mec208
fit2004
econ2101
fit9137
n1542
econ0051
engi4547
econ1048
eengm2510
fit1008
7033mkt
ec2066
cct380h5f
man00019m
mech265001
csc4140
math6119
comp1710
fina864
csys5020
busi4412
math5007
2702ict
dts204tc
cosc2673
ecmt2150
comp2003j
bff3121–
comu7000
stat6118
comp814
acc202
ematm0067
bit233
ecs776p
600543
comp3400
inf6028
bman30702
math0002
msci242l
mgt11001
com00177m
bman71282
fit2001
cpt210
econ7030
159.342 ‐ operating
mang6134
math1005/math6005
geog5404m
comp1710/6780
infs 2042
159.341
econ7310
comp3221
comp10002
cpt206
ecmt1010
finm081
econ2005
cpt202
fit3094
socs0030
data7201
data2x01
mn-3507
mat246h1
ib2d90
ib3j80
acc207
comp90007
compx518-24a
fit1050
info1111
acct2201
buad801
compsci369
cse 332s
info1110
math1033
scie1000
eeee2057
math4063
cmt219
econ5074
eng5009
csse2310/csse7231
ec333
econ0001
cpt204
elec4630
ma117
dts104tc
comp2017
640481
csit128
eco000109m
finc5090
ggr202h5f
nbs8295
4ssmn902
chc6171
dsa1002
ebu6304
mec206
csci-ua.202
comp1021
ma416
iom209
com6511
bism7202
idepg001
cpt106
comp1212
ecom209
fnce3000
fmhu5002
psyc10003
fina2222
be631-6-sp/1
finc2011
37989
5aaob204
citx1401
econ0028
bsan3204
comp9123
math1062
mn-3526
cmt218
itp122
qbus6820
ecmt1020
had7002h
cmt309
asb-3715
elec373
cpt204-2324
be631-6-sp
bus0117
soft3202/comp9202
basc0057
mecm30013
aem4060
acb1120
comp2123
econ2151
ecmt6006
inmr77
com 5140
ocmp5328
comp1039
econ3016
mast10007
buss6002
comp4403
finm1416
csc-30002
6qqmn971
fin668
mnfg309
inft2031
cits1402
comp2011
eecs 3221
ct60a9600
com336
8pro102
econ7300
联系我们
- QQ: 99515681 微信:codinghelp
© 2024
www.7daixie.com
站长地图
程序辅导网!