首页
编程语言
数据库
网络开发
Algorithm算法
移动开发
系统相关
金融统计
人工智能
其他
首页
>
> 详细
辅导 COMP528、讲解 c/c++,Python程序语言
University of Liverpool Assignment 1 Resit COMP528
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 begin work on this as soon as possible to avoid the queue
times on Barkla closer to the deadline. We would be happy to clarify anything you do not
understand in this report.
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.
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
(0, 2, 4, 5, 3, 1, 0). 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 1University of Liverpool Assignment 1 Resit COMP528
2 The solutions
2.1 Preparation of Solution
You are given a number of coordinate ffles 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 ffle
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 =
p
(xi − xj )
2 + (yi − yj )
2
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 2University of Liverpool Assignment 1 Resit COMP528
2.2 Smallest Sum Insertion
The smallest sum insertion algorithm starts the tour with the vertex with the lowest index.
In this case that is vertex 0. Each step, it selects a currently unvisited vertex where the
total edge cost to all the vertices in the partial tour is minimal. It then inserts it between
two connected vertices in the partial tour where the cost of inserting it between those two
connected vertices is minimal.
These steps can be followed to implement the smallest sum 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.
4
Figure 5: Step 1 of Smallest Sum Insertion
2. Find a vertex vj such that
Pt=Length(partialtour)
t=0
dist(vt
, vj ) is minimal.
Figure 6: Step 2 of Smallest Sum Insertion
3. Insert vj 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, vj ) + dist(vn+1, vj ) - dist(vn, vn+1) is
minimal.
4. Repeat steps 2 and 3 until all of the vertices have been visited.
2023-2024 3University of Liverpool Assignment 1 Resit COMP528
Figure 7: Step 3 of Smallest Sum Insertion
4
(a) Select the vertex
(b) Insert the vertex
Figure 8: Step 4 of Smallest Sum Insertion
(b) Insert the vertex
Figure 9: Step 5 of Smallest Sum Insertion
2023-2024 4University of Liverpool Assignment 1 Resit COMP528
4
(b) Insert the vertex
Figure 10: Step 6 of Smallest Sum Insertion
(a) Select the vertex
(b) Insert the vertex
Figure 11: Step 7 of Smallest Sum Insertion
2023-2024 5University of Liverpool Assignment 1 Resit COMP528
2.3 MinMax Insertion
The minmax insertion algorithm starts the tour with the vertex with the lowest index. In this
case that is vertex 0. Each step, it selects a currently unvisited vertex where the largest edge
to a vertex in the partial tour is minimal. It then inserts it between two connected vertices
in the partial tour where the cost of inserting it between those two connected vertices is
minimal.
These steps can be followed to implement the minmax 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 12: Step 1 of Minmax Insertion
2. Find a vertex vj such that M ax(dist(vt
, vj )) is minimal, where t is the list of elements
in the tour.
Figure 13: Step 2 of Minmax Insertion
3. Insert vj 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, vj ) + dist(vn+1, vj ) - dist(vn, vn+1) is
minimal.
4. Repeat steps 2 and 3 until all of the vertices have been visited.
2023-2024 6University of Liverpool Assignment 1 Resit COMP528
Figure 14: Step 3 of Minmax Insertion
(a) Select the vertex
4
(b) Insert the vertex
Figure 15: Step 4 of Minmax Insertion
(a) Select the vertex
(b) Insert the vertex
Figure 16: Step 5 of Minmax Insertion
2023-2024 7University of Liverpool Assignment 1 Resit COMP528
(a) Select the vertex
4
(b) Insert the vertex
Figure 17: Step 6 of Minmax Insertion
(b) Insert the vertex
Figure 18: Step 7 of Minmax Insertion
2023-2024 8University of Liverpool Assignment 1 Resit COMP528
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 smallest sum insertion or MinMax insertion, and
write the tour to the output file.
3.1 Provided Code
You are provided with the file coordReader.c, which you will need to include this file when
compiling your programs.
1. readNumOfCoords(): This function takes a filename as a parameter and returns the
number of coordinates in the given file as an integer.
2. readCoords(): This function 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.
3. writeTourToFile(): This function takes the tour, the tour length, and the output
filename as parameters, and writes the tour to the given file.
4 Instructions
• Implement a serial solution for the smallest sum insertion and the MinMax insertion.
Name these: ssInsertion.c, mmInsertion.c.
• Implement a parallel solution, using OpenMP,for the smallest sum insertion and the
MinMax insertion algorithms. Name these: ompssInsertion.c, ompmmInsertion.c.
• Create a Makefile and call it ”Makefile” which performs as the list states below. Without
the Makefile, your code will not grade on CodeGrade.
– make ssi compiles ssInsertion.c and coordReader.c into ssi.exe with the GNU
compiler
– make mmi compiles mmInsertion.c and coordReader.c into mmi.exe with the
GNU compiler
2023-2024 9University of Liverpool Assignment 1 Resit COMP528
– make ssomp compiles ompssInsertion.c and coordReader.c into ssomp.exe with
the GNU compiler
– make mmomp compiles ompmmInsertion.c and coordReader.c into mmomp.exe
with the GNU compiler
– make issomp compiles ompssInsertion.c and coordReader.c into issomp.exe with
the Intel compiler
– make immomp compiles ompmmInsertion.c and coordReader.c into immomp.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 screenshots of you compiling and
running your program. These do not contribute to the page limit.
• Your final submission should be uploaded onto CodeGrade. The files you
upload should be:
1. Makefile
2. ssInsertion.c
3. mmInsertion.c
4. ompssInsertion.c
5. ompmmInsertion.c
6. report.pdf
7. The slurm script you used to run your code on Barkla.
2023-2024 10University of Liverpool Assignment 1 Resit COMP528
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}
s s i : s s I n s e r t i o n . c coordReader . c
gcc s s I n s e r t i o n . c coordReader . c −o s s i . exe −lm
Now, on the command line, if you type ‘make ssi‘, 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.
This command may work for you and it may not. The point is to allow you to compile
however you like. If you want to declare the iterator in a for loop, you would have to add the
compiler flag −std=c99. −fopenmp is for the GNU compiler and −qopenmp is for the
Intel Compiler. If you find that the MakeFile is not working, please get in contact as soon
as possible.
Contact: h.j.forbes@liverpool.ac.uk
2023-2024 11University of Liverpool Assignment 1 Resit COMP528
6 Marking scheme
1 Code that compiles without errors or warnings 15%
2 Same numerical results for test cases (tested on CodeGrade) 20%
3 Speedup plot 10%
4 Parallel Efficiency Plot 10%
5 Parallel efficiency up to 32 threads (tests on Barkla yields good efficiency
for 1 Rank with 1, 2, 4, 8, 16, 32 OMP threads)
15%
6 Speed of program (tests on Barkla yields good runtime for 1, 2, 4, 8, 16,
32 ranks with 1 OMP thread)
10%
7 Clean code and comments 10%
8 Report 10%
Table 1: Marking scheme
The purpose of this assessment is to develop your skills in analysing numerical programs and
developing parallel programs using OpenMP. This assessment accounts for 40% of your final
mark, however as it is a resit you will be capped at 50% unless otherwise stated by the Student
Experience Team. Your work will be submitted to automatic plagiarism/collusion detection
systems, and those exceeding a threshold will be reported to the Academic Integrity Officer for
investigation regarding adhesion to the university’s policy https://www.liverpool.ac.uk/
media/livacuk/tqsd/code-of-practice-on-assessment/appendix_L_cop_assess.pdf.
7 Deadline
The deadline is 23:59 GMT Friday the 2nd of August 2024. https://www.liverp
ool.ac.uk/aqsd/academic-codes-of-practice/code-of-practice-on-assessment/
2023-2024 12
联系我们
QQ:99515681
邮箱:99515681@qq.com
工作时间:8:00-21:00
微信:codinghelp
热点文章
更多
辅导 ecos3010、讲解 java/pyt...
2024-09-07
辅导 data编程、讲解 python设...
2024-09-07
辅导 nur5000 theoretical bas...
2024-09-07
辅导 the impact of minimum w...
2024-09-07
讲解 marketing 301 fall 2024...
2024-09-07
讲解 marketing 301 fall 2024...
2024-09-07
辅导 environmental and natur...
2024-09-07
讲解 tcse1icb individual ass...
2024-09-07
讲解 principles of journalis...
2024-09-07
讲解 lngs1002 2024 assignmen...
2024-09-07
讲解 ece 498 ma: cmos ic des...
2024-09-07
讲解 opre 6369/mis 6369.0w1 ...
2024-09-07
辅导 cmn 4148a – communicat...
2024-09-07
讲解 22748 financial reporti...
2024-09-07
辅导 inft6201 – big data as...
2024-09-07
辅导 cse3smt software measur...
2024-09-07
辅导 corporate and internati...
2024-09-07
辅导 assessment 2 – group a...
2024-09-07
讲解 college writing extende...
2024-09-07
辅导 lin328 basic acoustics ...
2024-09-07
热点标签
mktg2509
csci 2600
38170
lng302
csse3010
phas3226
77938
arch1162
engn4536/engn6536
acx5903
comp151101
phl245
cse12
comp9312
stat3016/6016
phas0038
comp2140
6qqmb312
xjco3011
rest0005
ematm0051
5qqmn219
lubs5062m
eee8155
cege0100
eap033
artd1109
mat246
etc3430
ecmm462
mis102
inft6800
ddes9903
comp6521
comp9517
comp3331/9331
comp4337
comp6008
comp9414
bu.231.790.81
man00150m
csb352h
math1041
eengm4100
isys1002
08
6057cem
mktg3504
mthm036
mtrx1701
mth3241
eeee3086
cmp-7038b
cmp-7000a
ints4010
econ2151
infs5710
fins5516
fin3309
fins5510
gsoe9340
math2007
math2036
soee5010
mark3088
infs3605
elec9714
comp2271
ma214
comp2211
infs3604
600426
sit254
acct3091
bbt405
msin0116
com107/com113
mark5826
sit120
comp9021
eco2101
eeen40700
cs253
ece3114
ecmm447
chns3000
math377
itd102
comp9444
comp(2041|9044)
econ0060
econ7230
mgt001371
ecs-323
cs6250
mgdi60012
mdia2012
comm221001
comm5000
ma1008
engl642
econ241
com333
math367
mis201
nbs-7041x
meek16104
econ2003
comm1190
mbas902
comp-1027
dpst1091
comp7315
eppd1033
m06
ee3025
msci231
bb113/bbs1063
fc709
comp3425
comp9417
econ42915
cb9101
math1102e
chme0017
fc307
mkt60104
5522usst
litr1-uc6201.200
ee1102
cosc2803
math39512
omp9727
int2067/int5051
bsb151
mgt253
fc021
babs2202
mis2002s
phya21
18-213
cege0012
mdia1002
math38032
mech5125
07
cisc102
mgx3110
cs240
11175
fin3020s
eco3420
ictten622
comp9727
cpt111
de114102d
mgm320h5s
bafi1019
math21112
efim20036
mn-3503
fins5568
110.807
bcpm000028
info6030
bma0092
bcpm0054
math20212
ce335
cs365
cenv6141
ftec5580
math2010
ec3450
comm1170
ecmt1010
csci-ua.0480-003
econ12-200
ib3960
ectb60h3f
cs247—assignment
tk3163
ics3u
ib3j80
comp20008
comp9334
eppd1063
acct2343
cct109
isys1055/3412
math350-real
math2014
eec180
stat141b
econ2101
msinm014/msing014/msing014b
fit2004
comp643
bu1002
cm2030
联系我们
- QQ: 99515681 微信:codinghelp
© 2024
www.7daixie.com
站长地图
程序辅导网!