代写Oop|Project代写|代做Network|Python|Algorithm代写|Assignment代写：这是一个基于python语言的OOP编程，涉及了计算机网络、算法设计相关的内容
FIT2004 S2/2018: assignment 4
Total marks: 5
LATE PENALTY:25 % per day
CLASS:You may be interviewed by the tutor who may ask you a series of questions
to assess your understanding of this exercise, and gauge how you implemented it. You
will also be given feedback on your assignment. Failing to attend will result in you
being awarded zero mark for the assignment (unless you have an approved special
consideration). It is required that you implement this exercise strictly usingPython
programming language. Practical work is marked on the time and space complex-
ity of your programand also on your understanding of the program. Aperfect
program with zero understanding implies you will getzeromarks! Forgetting is
not an acceptable explanation for lack of understanding. Markers are not obliged to
mark programs that do not run or that crash.
SUBMISSION REQUIREMENT: You will need to submit a zipped file con-
taining your Python program (namedgetlucky.py) as well as a PDF file briefly
describing your solution and its space and time complexity. The PDF file must give
an outline of your solution (e.g., a high level idea of how did you solve it) and the
worst-casespace and time complexity of your solution. Penalties will be applied if
you fail to submit the PDF file. The zipped file is to be submitted on Moodle before
the deadline.
Important: The assignments will be checked for plagiarism using an advanced pla-
giarism detector and the students will be interviewed by tutors to demonstrate the
understanding of their code. Last year, many students were detected by the plagia-
rism detector and almost all got zero mark for the assignment and, as a result, many
failed the unit. Helping others is NOT okay. Please do not share your solutions
with others. If someone asks you for help, ask them to visit us during consultation
hours for help.
Minimum Detour Path
Ring ring. You take the call. It is Alice on the other side. Alice: I want to have a chat with you. Can I come to your place if you are home? An alarm bell starts ringing in your head Did she get to know about my scrabble 2. project for Cindy?. You worriedly reply: hmmmm…okay, yeah sure, I am home. You spend next 15 minutes thinking about different responses to calm her down. Finally, Alice arrives. To your surprise, she is in a really good mood and is holding a box of sweets and hands it over to you saying Here are some sweets for a sweet friend. Your Algorithm helped me to optimize my ebay listings and maximize the profit. I am so grateful to you. You are happy to hear that your hardwork helped her, and even happier to find out that she does not know about your scrabble 2.0 project. Thanks. I must admit that it took me
c Muhammad Aamir Cheema, Monash University
a while to understand the dynamic programming and solve the problems. And I still think I need to practice more to master the dynamic programming. Anyway, never mind Alice. Alice smiles and says, Practice makes perfect! :). You nod, Yes, you are right! Anyhoo, I hope your ebay business is not taking too much of your time and you are having fun. Alice exhales, The competition is cut throat but I am having fun. I enjoy coming up with new business strategies to compete with other businesses. For example, I am selling some heavy products for which the postage cost is quite high. To attract more customers, I have introduced a promotion that promises free same-day delivery to one lucky customer everyday. To keep the same-day delivery promise and to save the postage cost, I deliver the order myself, take a selfie while delivering the product and post it on our Facebook page to promote my business. This has significantly increased the number of orders I receive. You: Thats interesting. But it must be quite hectic to deliver the order yourself.. Alice: Exactly! Thats why I need your help in choosing the lucky customer. Everyday, I receive many orders from local customers (customers living in Melbourne) and my plan is to choose a customer such that delivering to him/her minimizes the distance I need to drive. For example, if I am going from home to work, I want to find the shortest route from home to work that passes through the delivery address of at least one customer. That will be the lucky customer 😉 You get sarcastic: Thats so transparent Alice 😛 Alice ignores your sarcasm and continues: Well, I have downloaded Melbourne road Network from OpenStreetMap. I have also written a script that obtains all recent orders from ebay and maps the delivery addresses for each order on the map. However, I do not know much about graph algorithms and am not sure how to find the shortest route. You: What a coincidence! We recently learned shortest path algorithms. I was planning to solve some graph problems to improve my understanding. I will be happy to help. Give me the details. Alice is so happy to hear this and explains the detailed requirements which are formally de- scribed below.
Input
The input filesedges.txt andcustomers.txtare provided in the zipped file tester.zip which can be downloaded from Moodle. Below are the first few lines fromedges.txt.
1000
0 1 950
0 2 3590
1 3 3340
2 5 1370
Vertices of the road network have sequential IDs starting from 0. The first line inedges.txt indicates the maximum ID of any vertex in the graph. For example, in the sample graph given inedges.txt, the maximum ID for any vertex is 1000. Every other line inedges.txt corresponds to an edge in the road network: first two columns are the IDs of vertices and the third column is the length of the edge connecting the two vertices. E.g., the second line indicates that there is an edge between the vertices with IDs 0 and 1 and the edge length is 950 meters. All roads in the network are bidirectional, i.e., the graph isnotdirectional.
The filecustomers.txtcontains the locations (delivery addresses) of customers. We assume that each customer is located on one of the vertices in the graph. We also assume that a vertex cannot have more than one customers. Below are the first 3 lines fromcustomers.txtdenoting that we have a customer on each of the vertices with IDs 5,54 and 145.
5
54
145
Task 1: Computing shortest path
The first task is to compute the shortest path and shortest distance between any two given verticessandt. The time complexity of your algorithm must beO(ElogV) and the space complexity must beO(V+E) whereV andEare the total number of vertices and edges in the graph, respectively. You have been provided with a template get_lucky.py which reads the input (IDs of source and target vertices) and provides a functionprint_solution(path,distance,task_id) to help you printing the output in the required format. The function takes three parame- ters, wherepathis a list containing vertices in the order in which they appear in the path, distance is the length of the path andtask_id is the task for which you want to print the solution (which should take the value 1 for task 1 and 2 for task 2). For example, assume that the shortest path between the source vertex 222 and the target vertex 183 is 220 –> 202 –> 186 –> 183with total distance 1580. To print this in the required format, you must create a list path=[220,202,186,183] and callprint_solution(path,1580,1). The function will print the following:
Shortest path: 220 --> 202 --> 186 --> 183
Shortest distance: 1580
YouMUSTuseprint_solutionfunction to print your output.
Task 2: The minimum detour path
The minimum detour path is the shortest route fromstotthat passes through at least one customer. Your algorithm must print the minimum detour path and its total length (called minimum detour distance). The following is a naive approach to find the minimum detour path and minimum detour distance.
# naive algorithm
minDetourDist = infinity
luckyCustomer = -
for each customer c
detourDist = dist(s,c) + dist(c,t) #use Disjkstras algorithm
if detourDist < minDetourDist:
luckyCustomer = c
minDetourDist = detourDist
minDetourPath = path from s to luckyCustomer + path from luckyCustomer to t
print minDetourDist and shortestDetourPath
In the above algorithm the shortest distance/path between two vertices is computed using Dijkstras algorithm. The for l oop in the above algorithm requires calling Dijkstras algorithm 2 C times whereC is the total number of customers. Therefore, the time complexity of the above algorithm isO(CElogV). Your solution must compute the minimum detour path and minimum detour distance inO(ElogV) time complexity andO(V+E) space complexity in the worst-case. Similar to Task 1, you must useprint_solution(path,distance,task_id)function to print your output for the task 2 in the required format. For example, if the source vertex is 222 and the target vertex is 183, the minimum detour path is220 –> 202 –> 186 –> 183 –> 200 –> 183with distance 3240 meters. Here, the customer is located on the vertex 200. To print this in the required format, you must create a listpath=[220,202,186,183,200,183] and callprint_solution(path,3240,2)(note that the value oftask_idis 2). The function will print the following:
Minimum detour path: 220 --> 202 --> 186 --> 183 --> 200(C) --> 183
Minimum detour distance: 3240
Note that the output displays(C)with the vertex 200 denoting that this vertex contains a customer. It is possible that there are more than one minimum detour paths. In this case, you can print any path of your choice. Your answer will be considered correct if the detour path is the minimal, i.e., there does not exist any other path betweenstotthat has a smaller distance and contains at least one customer.
Sample Output
This section provides sample output for different pairs of source and target vertices. You have also been provided with a naive solution innaive-solution.pywhich uses a text file FW.txtthat contains pre-computed all-pairs shortest distances (computed by Floyd-Warshall algorithm) to solve the two tasks. You can runnaive-solution.pyto check sample output for different pairs of source and target vertices. Below are some examples.
Enter source vertex: 220
Enter target vertex: 183
Shortest path: 220 --> 202 --> 186 --> 183
Shortest distance: 1580
Minimum detour path: 220 --> 202 --> 186 --> 183 --> 200(C) --> 183
Minimum detour distance: 3240
As stated earlier, in the minimum detour path, the vertex which has a customer located on it is denoted as(C), i.e., the vertex 200 has a customer located on it. Note that you do not have to worry about printing it as the functionprint_solutiondoes this itself for every vertex which has a customer located on it. Below is another example where the shortest distance is 320 meters and the minimum detour distance is 71520 meters (and the lucky customer is 315).
Enter source vertex: 580
Enter target vertex: 585
Shortest path: 580 --> 585
Shortest distance: 320
Minimum detour path: 580 --> 556 --> 536 --> 512 --> 497 --> 488 --> 481 -->
479 --> 491 --> 535 --> 591 --> 270 --> 239 --> 238 --> 240 --> 241 --> 245
--> 250 --> 255 --> 277 --> 284 --> 297 --> 303 --> 315(C) --> 303 --> 297
--> 284 --> 277 --> 255 --> 250 --> 245 --> 241 --> 240 --> 238 --> 239 -->
270 --> 591 --> 535 --> 491 --> 479 --> 481 --> 488 --> 497 --> 512 --> 536
--> 556 --> 580 --> 585
Minimum detour distance: 71520
It is also possible that the shortest path may be the same as the minimum detour path. See the example below.
Enter source vertex: 947
Enter target vertex: 1000
Shortest path: 947 --> 948 --> 949 --> 951(C) --> 977 --> 995 --> 1000
Shortest distance: 8500
Minimum detour path: 947 --> 948 --> 949 --> 951(C) --> 977 --> 995 --> 1000
Minimum detour distance: 8500
In some cases, a minimum detour path may contain more than one customers. In such case, Alice will manually look at the route and decide the lucky customer herself. Your task is only to return the minimum detour path containing at least one customer. In the example below, the minimum detour path contains two customers (767 and 747).
Enter source vertex: 849
Enter target vertex: 790
Shortest path: 849 --> 848 --> 846 --> 836 --> 831 --> 803 --> 731 --> 714
--> 720 --> 724 --> 727 --> 736 --> 790
Shortest distance: 16880
Minimum detour path: 849 --> 848 --> 846 --> 836 --> 831 --> 837 --> 838
--> 842 --> 852 --> 862 --> 868 --> 886 --> 904 --> 824 --> 815 --> 797
--> 767(C) --> 763 --> 747(C) --> 734 --> 723 --> 722 --> 721 --> 718 -->
717 --> 716 --> 715 --> 714 --> 720 --> 724 --> 727 --> 736 --> 790
Minimum detour distance: 18510
Note that it is also possible that a customer is located on a source or a target vertex. In the example below, the customer is located on the source vertex.
Enter source vertex: 315
Enter target vertex: 255
Shortest path: 315(C) --> 303 --> 297 --> 284 --> 277 --> 255
Shortest distance: 2230
Minimum detour path: 315(C) --> 303 --> 297 --> 284 --> 277 --> 255
Minimum detour distance: 2230
The user may enter the same ID for both source and the target vertices, i.e., Alice may want to start from her home, deliver an item and then return to her home. Below are some examples.
Enter source vertex: 300
Enter target vertex: 300
Shortest path: 300
Shortest distance: 0
Minimum detour path: 300 --> 277 --> 284 --> 297 --> 303 --> 315(C) --> 303
--> 297 --> 284 --> 277 --> 300
Minimum detour distance: 4320
In the example below, the target vertex is the same as the source vertex and a customer is located on the source vertex. Therefore, the shortest distance and minimum detour distance both are 0.
Enter source vertex: 315
Enter target vertex: 315
Shortest path: 315(C)
Shortest distance: 0
Minimum detour path: 315(C)
Minimum detour distance: 0
Things to note
You will lose all marks for a given task if your algorithm does not produce correct results for the task for all sample testcases shown above. Also, heavy penalties are applied if your complexity is worse than the required complexity and you may lose all marks if the complexity is similar to that of the naive algorithm. Your algorithm will also be checked on a different road network and customers file using a variety of test cases. Task 2 is the critical part of the assignment and is worth majority of the marks for this assignment. Therefore, do not assume that you will get around 50% marks by completing only the task 1. You have also been provided with a tester which you can use to ensure that your output matches the sample output. If you have issues using testers, contact your tutors or attend a consultation.