QUESTION

write a code and Implement the shortest path between nodes algorithm as a function in Python. Include a docstring. We have provided the reverse_in_place() code as given in the answer to Exercise 4.7.7. Make sure that your function inputs are in the order warehouse, start, end.

# The reverse_in_place code appears in Exercise 4.7.7 answer def reverse_in_place(values: list) -> None: """Reverse the order of the values.

Postconditions: post-values = [pre-values[len(pre-values) - 1], ..., pre-values[1], pre-values[0]] """ left_index = 0 right_index = len(values) - 1 while left_index

# Write your function code here

# Test code shortest_path_tests = [ # case, warehouse, start, end, shortest path ('neighbouring zones', warehouse, 'S', 'Y', ['S','Y']), ('zone neighbouring despatch', warehouse, 'despatch', 'D', ['despatch','D']), ('zone neighbouring despatch shortest path not direct', warehouse, 'despatch','Z', ['despatch','D','Z']), ('distant zones', warehouse, 'U', 'D', ['U','A','despatch','D']), ('distant zones opposite direction', warehouse, 'D', 'U', ['D','despatch','A','U']), ('two different shortest paths, choice depends on dijkstra', warehouse, 'Z', 'P', ['Z','D','P']), ] test(shortest_path, shortest_path_tests) # Add any explanatory comments here

Question

In this part we explore the problem of taking the quickest route from despatch to visit a given set of zones in any order (to fetch the requested items) before returning to despatch.

For example, the quickest route from despatch to visit D and Z in any order before returning to despatch is: despatch, D, Z, D, despatch.

State why this problem is not the travelling salesman problem (TSP).

question

We could use brute force to generate all possible candidate routes and choose the quickest one. State why this is not a practical option for routes through a large number of zones.

Q4(b)(iii) (7 Marks)

We can approach the problem in a greedy way by visiting the zones in the order they are listed.

Here is a greedy algorithm that visits the zones in the order in which they are listed, taking the shortest path to the next zone in the list each time:

let listed zones be the list of at least two zones to visit

visit the first zone in listed zones by the shortest path from despatch

for each zone in listed zones visit the next zone in the list by the shortest path from the previous zone in the list

return to despatch by the shortest path from the last zone in listed zones

Find a counter-example list of three zones for the example warehouse graph to show that this greedy algorithm is not correct. Explain how you arrived at your counter-example.

Give the route the greedy algorithm will take, explaining why it's that route. Give the quickest route you can find for your counter-example.

Calculate, by looking at the graph, how many seconds the route taken by the greedy algorithm will take, and how many seconds your quickest route will take.

Q4(b)(iv) (4 marks)

An alternative greedy way to approach this problem is to visit the closest (in time) zone in the set from the current zone by the shortest path at each step.

Here is a greedy algorithm that visits the closest (in time) zone in the set from the current zone by the shortest path each time, removing the zone from the set once it has been visited:

let zones to visit be the set of at least two zones to visit

let current be despatch

while zones to visit is not empty:

let nearest be the nearest zone in zones to visit to current

visit nearest by the shortest path from current

remove nearest from zones to visit

let current be nearest

return to despatch by the shortest path from current

What route will this greedy algorithm take for the counter-example you found in part (b)(iii)? Explain why it's that route.

Which of the two greedy algorithms appears to be a better solution for the problem of taking the quickest route from despatch to visit a given set of zones in any order before returning to despatch? Give a reason.

What else do you need to analyse to support your design choice between the two greedy algorithms?