Suppose you are trying to navigate a set of roads to get from point A to point B

Question

Suppose you are trying to navigate a set of roads to get from
point A to point B. Assume that the roads are on a grid. All roads are
one-way roads, and point either straight north or straight east. Your job is
to get from the southwest corner to the northeast corner of the grid.
At each intersection, there are trac lights, each of which has some delay
associated with it. Let di;j represent the delay caused by the intersection at
position (i; j) of the grid. At each intersection, you can go north or go east.
Note: when calculating the total delay, include the delays associated with
the rst (southwest) and last (northeast) intersections on your route.

Design a dynamic programming algorithm to determine the path of roads
you should take to get from the southwest corner to the northeast corner of
the grid with the smallest total delay. (Hint: if you want to get to location
(i; j), where could you have been immediately before?)
If you want to draw a DAG and explain your solution in terms of it, you can,
but you can use other solutions if you prefer.

Explanation / Answer

(N-1, M-1)

0,0

For M rows and N column
We will move from 0,0 to n-1, m-1

Lets delay[i][j] gives the delay of redlight.
delay[0][0] will belong to southwest bottom corner.. and so on..

Sample delay Matrix

1

9

7

5

2

6

3

4

8

If we create a matrix cost[N][M], where means cost[i][j] means lowest delay incurred to reach from 0,0 to I,j.

So cost[0][0] = delay[0][0];

Now Leftmost column can be travelled only by moving upwards from 0,0.

Hence

For(i=1, i<M; i++)

                Cost[i][0] = cost[i-1][0] + delay[i][0]

Similarly, for the bottom row, it can be travelled only if we move to right from 0,0.

For(j=1, j<N; j++)

                Cost[0][j] = cost[0][j-1] + delay[0][j]

Now consider 1,1 Light, We can reach light 1,1 from either 0,1 by moving right or 1,0 by moving up.
Hence the cost[1][1] will be delay[1][1] + min( cost[1][0], cost[0],[1]).

Similarly in this was, we can fill the matrix cost, from 1,1 to M-1, N-1

for(int i=1, i<M; i++) {
                for(int j=1; j<N; j++) {
                                cost[i][j] = delay[i][j] + min(cost[i][j-1], cost[i-1][j])
                }
}

Sample Cost Matrix Now

9

18

22

8

9

15

3

7

15

Now when cost as filled up, to print the path, start from 0,0 and check among 0,1 and 1,0 where cost is less.. take that path.

i=0, j=0;

While(i!=M-1 && j!= N-1) {
                // if we are on top row, we can just go to right
                if(i==M-1)
                                print “GO Right”; j++;
                                continue loop;
                // if we are on rightmost column, we can just go up
                if(j==N-1)
                                print “GO Right”; j++;
                                continue loop;


                if(cost[i + 1][j] > cost[i][j+1])
                                print “Go up”; Also, i++
                else
                                print “Go Right”, Also, j++
}

This was we can reach to Northeast corner.


Sample Path will be

Start from 0,0 => Move right => move up => Move Right => Move up. => Reached 3-1, 3-1

(N-1, M-1)

0,0

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.