Write an algorithm which given a table of times finds a route by greedily pickin
ID: 661112 • Letter: W
Question
Write an algorithm which given a table of times finds a route by greedily picking the next unvisited stop which is the shortest time away from the current stop. Decompose your problem using different modules to make your algorithm readable. Write all of the modules needed using pseudocode and use comments to make your solution as readable as possible. The main module should use the following signature: Greedy mail problem(T[0..n-1,0..n-1]) INPUT: A table of times, where T[i,j] indicates the time it takes to travel from location ito location j OUTPUT: A list of the locations to be visited using a greedy approach. ASSUMPTIONS: Stop 0 is the depot, i.e. T[0,j] is the time from the depot to stop j.Explanation / Answer
Suppose there are 5 depots to visit for the person: The person can choose 1-2-4-5-3-1 is one solution. 1-4-3-2-5-1 can also be another solution. So any permutaion in which the person travels from start to end to visit each node only once and comes back to the initial point, will be greedy algo. The minimum distance out of all available possible routes aill be our answer. So there will be (n-1)! feasible solutions because after (n-1) factorial , the same 5 nodes are repeated.
If we take it in form of a table for 5 cities:
- 10 9 8 7
10 - 10 5 6
8 10 - 8 9
9 5 8 - 6
7 6 9 6 -
The above table takes 5 stops and shows the distance travelled from one stop to another. But from any node to itself the distance will be 0, for which we write (-).
If a person travels from city 1, then he should travel minimum distance of that row atleast. For example: In first row minimum is 7, in row 2 minimum is 5 and so on
so sum of minimum distances in each row gives the lower bound.
and sum of lowest values in columns gives higher bound.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.