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

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

        時(shí)間:2023-12-19  來(lái)源:合肥網(wǎng)hfw.cc  作者:hfw.cc 我要糾錯(cuò)


        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

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

         

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

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

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

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

        日韩成人一区ftp在线播放| 99精品众筹模特私拍在线| 七次郎在线视频精品视频| 99精品全国免费观看视频| 国产99视频精品一区| 99re在线精品视频免费| 国产精品多人p群无码| 国产在线精品一区二区不卡麻豆| aaa级精品久久久国产片| 日韩视频在线精品视频免费观看| 国产精品久久亚洲一区二区| 精品国产这么小也不放过| 2020久久精品亚洲热综合一本| 亚洲精品国产成人| 精品视频一区二区三三区四区| 午夜精品射精入后重之免费观看| 日韩精品在线免费观看| 亚洲一区精品无码| 伊人久久精品无码二区麻豆| 99re6在线精品免费观看| 久久99精品久久久久久野外| 国产高清在线精品一区二区 | 日韩视频免费一区二区三区| 国产亚洲精品仙踪林在线播放| 国产成人久久精品亚洲小说| 国产精品三级国语在线看| 女同久久另类99精品国产| 无码人妻精品一二三区免费| 含羞草国产亚洲精品岁国产精品| 亚洲精品精华液一区二区 | 亚洲国产精品无码久久久久久曰| 日韩无套内射视频6| 精品乱人伦一区二区| 日韩精品成人a在线观看| 亚洲AV蜜桃永久无码精品| 国产精品无码v在线观看| 久久精品国产一区二区电影| 91麻豆国产福利精品| 国语自产拍精品香蕉在线播放| 精品久久久久久久| 久久99精品久久久久麻豆|