Project代做 | Python代做 | Algorithm – Minimum Detour Path

Project代做 | Python代做 | Algorithm – 这个是利用python解决Minimum Detour Path问题

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. projectfor 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 Algorithmhelped 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 Networkfrom 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
``````

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