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爱在线视频这里只有精品_窝窝午夜看片成人精品_日韩精品久久久毛片一区二区_亚洲一区二区久久

          欧美黄色成人网| 樱桃视频在线观看一区| 欧美一区二区精品久久911| 亚洲第一页在线| 国产精品国产成人国产三级| 久久先锋资源| 欧美专区第一页| 亚洲视频第一页| 亚洲精品国产精品乱码不99| 国精品一区二区| 国产精品午夜久久| 欧美揉bbbbb揉bbbbb| 欧美成人在线免费观看| 久久精品国产69国产精品亚洲| 亚洲小说欧美另类社区| 99www免费人成精品| 最新国产の精品合集bt伙计| 激情成人中文字幕| 国产人久久人人人人爽| 国产精品一区2区| 国产精品福利片| 国产精品国产一区二区| 欧美午夜视频网站| 国产精品美女黄网| 国产精品久久综合| 国产精品日韩久久久| 国产精品v一区二区三区| 欧美日韩直播| 国产乱码精品一区二区三区五月婷| 欧美深夜影院| 国产精品久久久久久久久借妻| 欧美日韩国产综合视频在线观看| 欧美99久久| 欧美日韩精品免费观看视一区二区| 欧美全黄视频| 国产精品v一区二区三区| 国产精品萝li| 国产三级欧美三级| 亚洲福利一区| 亚洲视频999| 小黄鸭精品密入口导航| 小黄鸭精品密入口导航| 久久精品亚洲一区二区三区浴池| 久久性天堂网| 午夜精品美女久久久久av福利| 在线视频一区观看| 亚洲欧美日韩精品在线| 亚洲视频在线看| 免费在线观看成人av| 99riav国产精品| 亚洲性线免费观看视频成熟| 在线亚洲伦理| 亚洲女同同性videoxma| 午夜精品区一区二区三| 久久久久九九九| 欧美日本不卡| 久久精品国产成人| 一本色道久久综合亚洲精品不卡 | 国产精品自拍一区| 国产一区二区av| 91久久久久久久久| 亚洲视频你懂的| 性欧美激情精品| 欧美福利小视频| 国产亚洲va综合人人澡精品| 亚洲国产视频一区二区| 亚洲丝袜av一区| 欧美成人激情视频免费观看| 国产精品乱码人人做人人爱| 又紧又大又爽精品一区二区| 亚洲性xxxx| 免费在线观看成人av| 国产嫩草一区二区三区在线观看| 亚洲日本成人网| 久久久.com| 国产精品国产三级国产a| 在线免费观看日本一区| 欧美一区二区精品久久911| 欧美二区在线观看| 国产一区二三区| 亚洲免费在线视频| 欧美精品成人一区二区在线观看| 国产精品一香蕉国产线看观看 | 另类尿喷潮videofree| 国产精品久久久亚洲一区| 91久久精品国产91性色| 久久人人看视频| 国产亚洲一区二区三区在线观看| 一本到高清视频免费精品| 欧美成人激情视频| 影音先锋久久久| 欧美伊人久久大香线蕉综合69| 欧美巨乳在线| 亚洲茄子视频| 欧美国产日韩免费| 亚洲国产欧美一区| 免费欧美日韩国产三级电影| 樱桃成人精品视频在线播放| 久久精品一区四区| 国产专区综合网| 欧美一区午夜视频在线观看| 国产精品日产欧美久久久久| 一区二区三区产品免费精品久久75| 欧美福利视频在线| 91久久精品久久国产性色也91| 久久五月激情| 亚洲高清视频中文字幕| 久久人人爽人人爽| 亚洲国产欧美日韩精品| 欧美理论电影网| 一区二区精品| 国产精品美腿一区在线看| 亚洲欧美日韩成人| 国产主播一区| 欧美国产第一页| 亚洲免费av片| 国产精品嫩草99av在线| 欧美一区二区在线视频| 伊人伊人伊人久久| 欧美精品一区二区三区在线看午夜| 亚洲毛片av| 国产精品国产三级国产aⅴ入口| 亚洲午夜精品久久久久久浪潮 | 国产日韩欧美黄色| 蜜桃av噜噜一区| 亚洲午夜免费福利视频| 国产日本欧美一区二区三区在线 | 亚洲区国产区| 国产精品成人观看视频免费 | 欧美视频一区二区在线观看 | 久久精品在这里| 99在线热播精品免费| 国产伦精品一区二区三区照片91 | 一区二区三区日韩精品| 黑丝一区二区三区| 欧美日韩国产在线观看| 欧美一区二区三区免费大片| 亚洲人成网站影音先锋播放| 国产精品乱码人人做人人爱| 久久人人爽人人爽爽久久| 亚洲视频精品| 亚洲高清资源| 国产一区999| 国产精品国产三级国产专播精品人 | 国产一区二区av| 国产精品高清网站| 欧美+日本+国产+在线a∨观看| 欧美夜福利tv在线| 亚洲视频电影图片偷拍一区| 亚洲国产片色| 精品1区2区| 国产视频久久| 国产伦理一区| 国产精品日日摸夜夜摸av| 你懂的亚洲视频| 久久综合一区二区| 久久精品国产一区二区三区| 亚洲一区综合| 亚洲天堂网在线观看| 日韩视频在线一区| 亚洲精品视频免费| 亚洲国产精品综合| 亚洲国产精品热久久| 精品96久久久久久中文字幕无| 国产婷婷成人久久av免费高清 | 国产欧美一区二区精品仙草咪 | 性做久久久久久久久| 亚洲一区二区高清| 亚洲综合精品四区| 午夜欧美精品久久久久久久| 午夜视频在线观看一区二区三区| 一区二区三区免费在线观看| 一区二区三区国产| 亚洲欧美成aⅴ人在线观看| 午夜精品一区二区在线观看| 亚洲一区在线看| 欧美一区在线视频| 久久男人资源视频| 欧美大胆成人| 欧美日韩国产限制| 国产精品嫩草99a| 国产一区二区在线观看免费播放 | 国产一区二区成人| 在线高清一区| 亚洲伦伦在线| 午夜精品久久久久久久蜜桃app| 性欧美暴力猛交另类hd| 久久蜜桃资源一区二区老牛 | 亚洲裸体视频| 在线一区二区日韩| 久久精品国产亚洲aⅴ| 蜜臀久久99精品久久久久久9| 老巨人导航500精品| 欧美日韩精品一区| 国产婷婷精品| 一区二区精品在线| 久久午夜精品一区二区| 欧美日本乱大交xxxxx| 国内精品久久久久久| 在线观看av不卡|