99爱在线视频这里只有精品_窝窝午夜看片成人精品_日韩精品久久久毛片一区二区_亚洲一区二区久久

合肥生活安徽新聞合肥交通合肥房產(chǎn)生活服務(wù)合肥教育合肥招聘合肥旅游文化藝術(shù)合肥美食合肥地圖合肥社保合肥醫(yī)院企業(yè)服務(wù)合肥法律

COMP528代寫、代做c/c++編程設(shè)計

時間:2023-12-19  來源:合肥網(wǎng)hfw.cc  作者:hfw.cc 我要糾錯


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 deadline 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.

202**024 1

COMP528

2 The solutions

2.1 Preparation of Solution

You are given a number of coordinate files with this format:

x, y

4.81263062**6921, 8.3**19930253777

2.**156816804616, 0.39593575612759

1.13649642931556, 2.2**59458630845

4.4**7**99682118, 2.9749120444**06

9.8****616851393, 9.107****070**

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.0870**

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.0870** 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

.

202**024 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.

202**024 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.

202**024 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

202**024 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

202**024 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:

./<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 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.

202**02**

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 farthest insertion. Name these: ompcInsertion.c, ompfInsertion.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 (see more in section 5.1).

– make ci compiles cInsertion.c and coordReader.c into ci.exe with the GNU compiler

– 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 ** 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

202**024 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.

202**024 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 ** threads 15%

6 Speed of program 10%

11 Clean code and comments 10%

12 Report 10%

Table 1: Marking scheme

7 Deadline

202**024 10

請加QQ:99515681 或郵箱:99515681@qq.com   WX:codehelp

 

掃一掃在手機(jī)打開當(dāng)前頁
  • 上一篇:MA2552代做、代寫Matlab編程語言
  • 下一篇:代寫選股公式 代做通達(dá)信量中尋莊副圖指標(biāo)
  • 無相關(guān)信息
    合肥生活資訊

    合肥圖文信息
    急尋熱仿真分析?代做熱仿真服務(wù)+熱設(shè)計優(yōu)化
    急尋熱仿真分析?代做熱仿真服務(wù)+熱設(shè)計優(yōu)化
    出評 開團(tuán)工具
    出評 開團(tuán)工具
    挖掘機(jī)濾芯提升發(fā)動機(jī)性能
    挖掘機(jī)濾芯提升發(fā)動機(jī)性能
    海信羅馬假日洗衣機(jī)亮相AWE  復(fù)古美學(xué)與現(xiàn)代科技完美結(jié)合
    海信羅馬假日洗衣機(jī)亮相AWE 復(fù)古美學(xué)與現(xiàn)代
    合肥機(jī)場巴士4號線
    合肥機(jī)場巴士4號線
    合肥機(jī)場巴士3號線
    合肥機(jī)場巴士3號線
    合肥機(jī)場巴士2號線
    合肥機(jī)場巴士2號線
    合肥機(jī)場巴士1號線
    合肥機(jī)場巴士1號線
  • 短信驗證碼 豆包 幣安下載 AI生圖 目錄網(wǎng)

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

    Copyright © 2025 hfw.cc Inc. All Rights Reserved. 合肥網(wǎng) 版權(quán)所有
    ICP備06013414號-3 公安備 42010502001045

    99爱在线视频这里只有精品_窝窝午夜看片成人精品_日韩精品久久久毛片一区二区_亚洲一区二区久久

          国产精品一区在线播放| 性色av香蕉一区二区| 国产日韩在线看| 久久天天躁狠狠躁夜夜爽蜜月| 日韩一级二级三级| 国产综合色产在线精品| 国产精品久久91| 欧美日本不卡高清| 蘑菇福利视频一区播放| 欧美怡红院视频| 一区二区三区偷拍| 亚洲美女av黄| 亚洲欧洲精品一区二区三区 | 欧美精品偷拍| 免费精品99久久国产综合精品| 亚洲欧美精品中文字幕在线| 99精品欧美一区| 亚洲欧洲日本mm| 亚洲第一中文字幕| 伊甸园精品99久久久久久| 国产欧美激情| 国产精品高潮呻吟久久| 欧美日韩一区在线观看| 欧美日本在线看| 欧美久久久久久久久| 欧美暴力喷水在线| 免费在线观看精品| 欧美.www| 欧美国产先锋| 欧美日韩美女在线| 欧美日韩在线精品一区二区三区| 欧美另类变人与禽xxxxx| 欧美国产日韩亚洲一区| 欧美激情精品久久久久久大尺度 | 久久亚裔精品欧美| 久久国产日韩欧美| 久热精品视频在线观看| 久久综合给合| 欧美精品日本| 国产精品捆绑调教| 国产亚洲欧洲一区高清在线观看 | 国产精品视频导航| 国内精品久久久久久影视8 | 在线观看国产日韩| 欧美三级乱码| 欧美区国产区| 麻豆精品一区二区av白丝在线| 久久久午夜精品| 午夜国产一区| 欧美影院视频| 亚洲视频网在线直播| 亚洲欧美在线免费观看| 久久综合中文色婷婷| 久久久久久尹人网香蕉| 欧美福利一区二区| 国产精品久久久久久久久婷婷| 国产乱理伦片在线观看夜一区 | 国内精品久久久久久| 亚洲福利视频专区| 亚洲综合欧美| 欧美成人自拍| 国产一区二区精品久久| 亚洲靠逼com| 午夜视频一区| 欧美日韩国产色视频| 国语自产精品视频在线看| 亚洲精品久久久久久久久久久久| 亚洲一区区二区| 欧美—级在线免费片| 国产精品欧美一区喷水| 亚洲精品欧美一区二区三区| 亚洲欧美日韩成人高清在线一区| 欧美+亚洲+精品+三区| 国产精品素人视频| 99re在线精品| 女人色偷偷aa久久天堂| 国产亚洲欧美一区在线观看| 一区二区三区视频在线观看| 美女脱光内衣内裤视频久久网站| 国产精品久久久久久久午夜| 最新日韩中文字幕| 免费高清在线一区| 激情一区二区三区| 欧美一区二区三区久久精品茉莉花 | 久久一区二区三区超碰国产精品| 国产精品久久久久久亚洲调教 | 欧美精品一区二区三区蜜桃 | 久久嫩草精品久久久久| 国产精品日韩一区二区三区| 一本色道久久综合亚洲精品婷婷| 欧美精品粉嫩高潮一区二区| 亚洲国产精品成人精品| 久久一日本道色综合久久| 国产日韩1区| 亚洲视频在线二区| 欧美系列电影免费观看| 一区二区不卡在线视频 午夜欧美不卡在| 美国十次了思思久久精品导航| 国产一区三区三区| 久久精品视频一| 国产一区在线播放| 久久精品一区中文字幕| 黄色日韩网站视频| 麻豆精品视频在线观看| 亚洲成人自拍视频| 欧美精品尤物在线| 一区二区三区国产| 国产精品福利在线观看| 亚洲女女做受ⅹxx高潮| 国产精品一区毛片| 久久久久久久久一区二区| 亚洲国产精品成人综合| 欧美成人国产一区二区| 亚洲精选在线观看| 国产精品视频大全| 久久天堂成人| 日韩亚洲一区二区| 亚洲国产精品尤物yw在线观看| 一区二区在线视频播放| 亚洲欧美日韩精品综合在线观看| 国产亚洲一区精品| 欧美电影免费观看| 久久精品视频免费| 亚洲一区精品在线| 亚洲破处大片| 精品91在线| 国产一区二区成人| 欧美日韩中文精品| 黑人中文字幕一区二区三区| 久久婷婷麻豆| 久久成人羞羞网站| 久久成人一区二区| 亚洲三级视频| 国产精自产拍久久久久久| 这里只有精品丝袜| 午夜欧美精品| 性做久久久久久| 午夜精品久久久久久久男人的天堂| 在线视频亚洲| 亚洲一区欧美激情| 久久先锋影音av| 99riav1国产精品视频| 国产一区二区日韩精品欧美精品| 欧美好吊妞视频| 久久久久国产精品www| 亚洲一区免费网站| 亚洲国内高清视频| 激情综合色丁香一区二区| 欧美视频在线一区| 欧美高清自拍一区| 久久久久国产精品麻豆ai换脸| 日韩一区二区免费看| 亚洲国产日韩欧美在线动漫| 国产婷婷色综合av蜜臀av| 国产精品成人一区| 欧美视频在线观看 亚洲欧| 欧美高清一区| 欧美福利一区二区| 麻豆精品在线视频| 乱人伦精品视频在线观看| 欧美在线影院在线视频| 亚洲欧美日韩国产精品 | 午夜精品久久久久久久99樱桃 | 亚洲精品一区二区三区蜜桃久| 精品动漫3d一区二区三区免费| 国产欧美精品一区二区三区介绍| 欧美亚州一区二区三区| 欧美视频成人| 欧美日韩亚洲网| 欧美四级伦理在线| 国产精品成人aaaaa网站| 国产精品成人va在线观看| 欧美性天天影院| 国产精品激情| 国产一区二区三区久久久久久久久| 国产精品亚洲综合天堂夜夜| 国产日韩欧美视频| 激情小说另类小说亚洲欧美| 1769国内精品视频在线播放| 亚洲第一视频网站| 亚洲免费av片| 亚洲一区久久| 久久国产一区二区| 男女av一区三区二区色多| 欧美精品aa| 国产精品每日更新| 国产一区二区三区av电影| 在线不卡亚洲| 亚洲天堂av电影| 久久大香伊蕉在人线观看热2| 老司机午夜精品视频| 欧美精品日本| 国产精品一区二区在线观看网站| 国内精品久久久久影院薰衣草 | 亚洲国产欧美一区二区三区同亚洲| 亚洲精品综合精品自拍| 亚洲欧美中文在线视频| 麻豆免费精品视频| 国产精品伦子伦免费视频| 韩日午夜在线资源一区二区|