日本欧洲视频一区_国模极品一区二区三区_国产熟女一区二区三区五月婷_亚洲AV成人精品日韩一区18p

代寫(xiě)COMP528、代做c/c++,Python程序語(yǔ)言

時(shí)間:2024-07-27  來(lái)源:  作者: 我要糾錯(cuò)



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:
$ ./<program name >. exe <c o o r d i n a t e f i l e n a m e > <o u t p u t fil e n am e >
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

請(qǐng)加QQ:99515681  郵箱:99515681@qq.com   WX:codinghelp




 

標(biāo)簽:

掃一掃在手機(jī)打開(kāi)當(dāng)前頁(yè)
  • 上一篇:CIT 593代做、代寫(xiě)Java/c++語(yǔ)言編程
  • 下一篇:代寫(xiě)COMP4337、代做Python編程設(shè)計(jì)
  • 代做IERG 4080、代寫(xiě)Python程序語(yǔ)言
  • CS202代做、代寫(xiě)Java/Python程序語(yǔ)言
  • 代做SEHH2239、Python程序語(yǔ)言代寫(xiě)
  • COMP3334代做、代寫(xiě)Python程序語(yǔ)言
  • 代寫(xiě)COMP9021、代做Python程序語(yǔ)言
  • 昆明生活資訊

    昆明圖文信息
    蝴蝶泉(4A)-大理旅游
    蝴蝶泉(4A)-大理旅游
    油炸竹蟲(chóng)
    油炸竹蟲(chóng)
    酸筍煮魚(yú)(雞)
    酸筍煮魚(yú)(雞)
    竹筒飯
    竹筒飯
    香茅草烤魚(yú)
    香茅草烤魚(yú)
    檸檬烤魚(yú)
    檸檬烤魚(yú)
    昆明西山國(guó)家級(jí)風(fēng)景名勝區(qū)
    昆明西山國(guó)家級(jí)風(fēng)景名勝區(qū)
    昆明旅游索道攻略
    昆明旅游索道攻略
  • NBA直播 短信驗(yàn)證碼平臺(tái) 幣安官網(wǎng)下載 歐冠直播 WPS下載

    關(guān)于我們 | 打賞支持 | 廣告服務(wù) | 聯(lián)系我們 | 網(wǎng)站地圖 | 免責(zé)聲明 | 幫助中心 | 友情鏈接 |

    Copyright © 2025 kmw.cc Inc. All Rights Reserved. 昆明網(wǎng) 版權(quán)所有
    ICP備06013414號(hào)-3 公安備 42010502001045

    日本欧洲视频一区_国模极品一区二区三区_国产熟女一区二区三区五月婷_亚洲AV成人精品日韩一区18p

              国产色视频一区| 久久久中精品2020中文| 国产午夜久久久久| 欧美精品手机在线| 欧美在线视频免费播放| 亚洲日本理论电影| 韩日精品视频| 欧美系列精品| 欧美伦理影院| 久久久久久自在自线| 亚洲一区二区精品在线| 亚洲国产成人精品久久久国产成人一区 | 欧美老女人xx| 美腿丝袜亚洲色图| 欧美亚洲自偷自偷| 亚洲欧美另类在线| 一本不卡影院| 亚洲精品社区| 亚洲欧洲精品一区二区三区波多野1战4 | 久久激情五月激情| 亚洲综合日韩中文字幕v在线| 亚洲久久成人| 亚洲免费福利视频| 亚洲精品日韩久久| 最新国产拍偷乱拍精品| 伊人精品久久久久7777| 国内精品久久久久国产盗摄免费观看完整版 | 亚洲视频专区在线| 99视频精品在线| 日韩亚洲欧美成人| 夜夜嗨网站十八久久| 日韩视频在线一区| 亚洲桃色在线一区| 亚洲深夜福利网站| 亚洲欧美文学| 欧美一级网站| 久久久国产精品亚洲一区 | 亚洲欧美怡红院| 欧美一区二区三区精品| 久久av在线| 蜜臀av在线播放一区二区三区| 麻豆精品在线观看| 欧美精品在线播放| 欧美三级在线视频| 国产精品欧美久久| 精品av久久707| 日韩视频在线观看| 午夜精品视频| 另类激情亚洲| 欧美视频在线观看视频极品| 国产精品三级视频| 精品69视频一区二区三区| 亚洲精品一区二区三区婷婷月 | 欧美日韩另类综合| 国产精品午夜在线| 亚洲电影一级黄| 亚洲字幕在线观看| 蜜臀va亚洲va欧美va天堂| 国产精品国产三级国产aⅴ浪潮| 国产精品尤物福利片在线观看| 黄色欧美日韩| 亚洲色图在线视频| 久久亚洲一区二区三区四区| 欧美日韩p片| 在线欧美视频| 一区二区不卡在线视频 午夜欧美不卡在 | 午夜亚洲一区| 欧美精品一区二区精品网| 国产伦精品一区二区三区在线观看 | 欧美精品日韩一本| 国产亚洲人成网站在线观看| 99天天综合性| 玖玖综合伊人| 国产一级一区二区| 亚洲香蕉网站| 欧美久久婷婷综合色| 国内精品美女在线观看| 亚洲视频欧美视频| 欧美成人精品三级在线观看| 国产一区二区三区日韩欧美| 亚洲图片激情小说| 欧美精品一区二区久久婷婷| 亚洲第一在线视频| 久久久久久精| 国产午夜一区二区三区| 亚洲一区二区三区视频播放| 欧美国产日韩一区二区在线观看 | 久久这里有精品15一区二区三区| 欧美三级在线| 日韩亚洲综合在线| 蜜臀91精品一区二区三区| 国产一区二区三区在线免费观看 | 国产精品一区二区你懂的| 一区二区三区久久久| 欧美日韩国产首页在线观看| 在线精品福利| 欧美88av| 亚洲激情网站免费观看| 嫩草影视亚洲| 亚洲国产欧美日韩精品| 能在线观看的日韩av| 91久久国产综合久久蜜月精品| 久久―日本道色综合久久| 国产一区日韩欧美| 久久久亚洲国产天美传媒修理工| 国产农村妇女精品一二区| 欧美一区二区在线观看| 国产在线精品自拍| 久久综合伊人77777| 91久久精品国产91久久性色tv| 久热精品视频在线| 91久久久久久久久| 欧美另类高清视频在线| 国产精品99久久久久久宅男| 国产精品久久久一区麻豆最新章节 | 裸体素人女欧美日韩| 亚洲国产人成综合网站| 欧美视频中文字幕在线| 性18欧美另类| 亚洲三级影片| 国产精品一区毛片| 久久综合久久美利坚合众国| 日韩午夜电影av| 国产欧美三级| 欧美国产精品| 亚洲女人天堂av| 尹人成人综合网| 国产精品第13页| 久久久99爱| 亚洲一区二区精品| 伊人婷婷欧美激情| 国产精品高潮呻吟久久| 久久久夜夜夜| 亚洲欧美日韩在线综合| 怡红院av一区二区三区| 欧美激情欧美狂野欧美精品| 亚洲欧美在线免费观看| 亚洲人屁股眼子交8| 国产日产欧美精品| 欧美精品在线看| 久久影视精品| 亚洲欧美成人综合| 亚洲福利小视频| 国产精品网红福利| 欧美激情第六页| 久久精品夜色噜噜亚洲a∨| 日韩视频在线观看免费| 尤物在线观看一区| 国产伦精品一区二区三区高清版 | 欧美午夜一区| 欧美日本一区| 欧美激情综合亚洲一二区| 久久精品亚洲精品国产欧美kt∨| 亚洲无线观看| 亚洲一区二区三区在线看| 亚洲精品乱码久久久久久黑人| 国产在线一区二区三区四区| 国产精品一区在线观看| 欧美小视频在线| 欧美日韩亚洲免费| 欧美日韩精品系列| 欧美精品免费在线观看| 欧美国产视频日韩| 欧美大色视频| 欧美激情精品久久久久久大尺度| 久久精品在这里| 久久久久久网站| 鲁鲁狠狠狠7777一区二区| 美女国产一区| 欧美国产三区| 欧美日韩国产二区| 欧美日韩精品在线播放| 欧美日韩一区二区三区在线视频 | 国产精品久久久久av免费| 国产精品久久看| 国产日韩欧美一二三区| 国产亚洲欧美激情| 极品尤物av久久免费看| 亚洲高清视频一区| 亚洲精品日韩在线观看| 99视频在线精品国自产拍免费观看 | 国产视频亚洲精品| 国产一区视频在线看| 国内揄拍国内精品少妇国语| 亚洲第一色中文字幕| 99视频在线观看一区三区| 亚洲性夜色噜噜噜7777| 久久精品人人做人人爽| 蜜臀91精品一区二区三区| 欧美日韩国产999| 国产精品视频第一区| 韩国欧美一区| 亚洲精品小视频在线观看| 亚洲一区高清| 麻豆freexxxx性91精品| 欧美精品二区三区四区免费看视频| 欧美性一二三区| 国产一区二区日韩精品欧美精品 | 欧美精品一区二区三区在线看午夜 | 亚洲国产精品高清久久久|