KIT205 Data Structures and AlgorithmsAssignment 2Due: Friday 1st June, 11:55pmIntroductionMiniMetro (https://dinopoloclub.com/minimetro/) is a game about designing efficient metrotransport. You design your tracks and assign your trains, and then commuters pop up wantingto go somewhere. Each stop has a symbol indicating the type of neighbourhood. Eachcommuter wants to get to a particular type of neighbourhood and will take the first train thatwill get them there quickly.This assignment is about some first steps towards an optimal solution for this game and willinvolve graph algorithms and data structures. The assignment will give you some practiceworking with graph data structures and implementing standard algorithms based onpseudocode. It will also give you some experience developing unique algorithms for specificproblems by extending a standard algorithm.Assignment SpecificationFor this assignment, we will create a simpler and more abstract representation of theproblem. You will be given a set of stops, their neighbourhood type and x,y coordinates. Astop will be represented by the following struct:typedef struct stop{int type;int x;int y;} Stop;You will also be provided with the following function that generates an array of stops.Stop* get_stops(int num_stops);The main task for this assignment is to build a new graph using a subset of these edges thatconnects all stops. You will attempt to build a track of minimal cost, where the cost is afunction of the edge weights (the cost of building the track) and the time taken for simulatedcommuters to complete their journey.You will be provided with a function that calculates the cost for a given graph:float get_score(Graph *self);This function calculates the cost for edges, and then simulated 1000 random trips. Each trip isfrom a random stop to the nearest stop of a random type. It needs to have a workingDijkstra’s algorithm to work properly.Part A Converting the Data into Graph Format (~55%)Your first task is to convert the stop information into a complete weighted graph where everystop is connected to every other stop with the weight calculated as the distance between stops. The distance can be calculated using sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)) where and are the coordinates of two cities (this function will be provided in thebase code).You should store this initial graph using an adjacency list as specified below (given that this is acomplete graph, an adjacency matrix might be preferred, but our algorithms are going to workwith adjacency list representations, so we will stick with that). We are building an undirectedgraph for this problem. To represent this as an adjacency list, each edge from u->v needs tohave a matching edge from v->u.typedef struct edge{int to_vertex;float weight;} Edge;typedef struct edgeNode{Edge edge;struct edgeNode *next;} *EdgeNodePtr;typedef struct edgeList{EdgeNodePtr head;} EdgeList;typedef struct graph {int V;int *vertex_types;EdgeList *edges;} Graph;Part B Dijkstra’s Algorithm (~15%)The get_score function makes use of Dijkstra’s algorithm, so your first step is to implementthis algorithm. You should implement Dijkstra’s algorithm based on the pseudocode onWikipedia (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm). While a priority-queueimplementation might be best for our scenario, you should instead use a simple search to findthe nearest vertex.Once you have correctly implemented this algorithm, you should be able to test it bycalculating a score for the initial fully connected graph.Part C Minimal Spanning Tree (~15%)Next, we want to see if we can improve on this score. Since there is a cost for each edge, itmakes sense to remove as many edges as possible while keeping the graph connected. Aminimal spanning tree should be a good starting place. So, your next task is to implementPrim’s minimal spanning tree algorithm that will take the initial graph and return the MST.There is a little pseudocode for Prim’s algorithm on Wikipedia(https://en.wikipedia.org/wiki/Prim%27s_algorithm), but this is more abstract than thepseudocode for Dijkstra. However, you can base your solution on your solution for Dijkstra.The only things that change are: The way you calculate the nearest unknown vertex. Instead of storing the distancesfound so far, instead store the cost of connecting a vertex. You will also need to knowthe edge that gives this cost, so add an array to keep track of this that stores thevertex to connect to. How you store your solution. We need to build a new graph, so start by initialising anew graph with the same number of vertices as the graph provided, but no edges (butdon’t forget to initialise the edge lists). Then, when you find the nearest unknownvertex, add two (one for each direction) edges into the graph to connect the newvertex. These edges need to have the same weights as the corresponding edges inthe original graph. How to process the nearest unknown vertex. This is very similar to Dijkstra. Justloop through all of the edges from this vertex. If the edge connects to an unknownvertex, and if the weight of this edge is less than the best cost found so far, thenupdate the cost for to-vertex, and store the current vertex to keep KIT205留学生作业代做、代写Data Structures作业、代写Java/Python/C++程序设计作业 代做track of the edgethat gives this cost.You can then check to see if the MST has improved the score.Part D Can You Do Better? (~15%)There is no need for us to use an MST. It is going to give the lowest possible cost for laying thetrack, but it won’t necessarily give good commute times. So, your final task is to see if you canimprove on the MST. You might like to try: Start with an MST, but add in some extra edges Use MST, but try to force it to use edges that you think are useful (e.g. modify theweights that the algorithm uses) A combination of both methods, or something not based on MST at all (maybesomething based on graph colouring would work?)To get good marks for this section, you must make a serious attempt to improve the score (notjust make a random change to the MST algorithm, for example).Base Code, Program Output, and TestingYou will be provided with a Visual Studio base project that contains some utility functions forgenerating stops and simulating commutes to calculate a score. The main function is alreadyset up for you, and comments show where you need to add your own code.As you complete each part of the assignment, there are commented printf statements in themain function that can be uncommented to test your implementation. However, it is best todo additional testing. For the standard graph algorithms in particular, this should be tested ongraphs where the correct solution is known (either because you have calculated it by hand, orbecause you found a suitable example online).Once you start testing with the randomly generated graphs, you might like to use a fixedrandom number seed (e.g. srand(123); ). This will make it easier to compare different runs.The required output for this assignment is very minimal. The necessary printf statementsalready exist in the code, you just need to uncomment them as you complete each part. Witha randomly generated graph of 20 stops, the output might be as follows:base score: 2423.639160mst score: 737.128357my score: 728.430176press enter to exitThe exact output that you get will depend on the random graph generated.Assignment SubmissionAssignments will be submitted via MyLO (an Assignment 2 dropbox will be created). Youshould use the following procedure to prepare your submission: Make sure that your project has been thoroughly tested using the School’s labcomputers Choose “Clean Solution” from the “Build” menu in Visual Studio. This step is veryimportant as it ensures that the version that the marker runs will be the same as theversion that you believe the marker is running. Quit Visual Studio and zip your entire project folder along with a completedassignment cover sheet Upload a copy of the zip file to the MyLO dropboxHistory tells us that mistakes frequently happen when following this process, so you shouldthen: Unzip the folder to a new location Open the project and confirm that it still compiles and runs as expectedo If not, repeat the process from the startKIT205 Data Structures and Algorithms: Assignment 2Synopsis of the task and its contextThis is an individual assignment making up 15% of the overall unit assessment. The assessment criteria for this task are:1. Implement code to construct an adjacency list representation of a graph2. Implement Dijkstra’s algorithm to find shortest paths3. Implement Floyd-Warshall algorithm to find shortest pathsMatch between learning outcomes and criteria for the task:Unit learning outcomesOn successful completion of this unit… Task criteria:On successful completion of this unit, you will be able to:1. Transform a real world problem into a simple abstract form that is suitable for computation2. Implement common data structures and algorithms using a common programming language3. Analyse the theoretical and practical run time and space complexity of computer code in order to select algorithms forspecific tasks4. Use common algorithm design strategies to develop new algorithms when there are no pre-existing solutions5. Create diagrams to reason and communicate about data structures and algorithms1-31-3--1-3Criteria HD (High Distinction) DN (Distinction) CR (Credit) PP (Pass) NN (Fail)You have: You have: You have: You have: You have:1. Implement genericgraph datastructures andalgorithmsWeighting 60% Adjacency list correctly implemented Correctly implemented Dijkstra’salgorithm Correctly implemented Prim’s MSTalgorithm Adjacency list correctlyimplemented Correctly implementedDijkstra’s and/or Prim’salgorithm Adjacency list correctlyimplemented Implemented Dijkstra’sand/or Prim’s algorithmwith some errors Adjacency listcorrectlyimplemented Basic graphtutorial codeattempted2. Apply graph datastructures andalgorithms to solvea specific problemWeighting 40% Correctly built an adjacency list graphto represent the problem Correctly implemented a customfunction to solve the problem Freed all memory when no longerneeded Correctly built an adjacency list graph to represent theproblem Correctly implemented a custom function to solve theproblem Correctly built anadjacency listgraph torepresent theproblem Some attemptto build thegraph for thisproblem转自：http://www.7daixie.com/2019050657139250.html
网友评论