Lesson 5.6
The Manhattan Tourist Problem Revisited
Watch the lectureDynamic Programming and Backtracking Pointers
You should now be ready to implement an algorithm solving the Manhattan Tourist Problem. The following pseudocode computes the length of the longest path to node (i, j) in a rectangular grid and is based on the observation that the only way to reach node (i, j) in the Manhattan Tourist Problem is either by moving south (↓) from (i − 1, j) or east (→) from (i, j − 1).
SouthOrEast(i, j)
if i = 0 and j = 0
return 0
x ← −∞, y ← −∞
if i > 0
x ← SouthOrEast(i − 1, j) + weight of the vertical edge into (i, j)
if j > 0
y ← SouthOrEast(i, j − 1) + weight of the horizontal edge into (i, j)
return max{x, y}STOP and Think How many times is SouthOrEast(3, 2) called in the computation of SouthOrEast(9, 7)?
Similarly to RecursiveChange, SouthOrEast suffers from a huge number of recursive calls, and we need to reframe this algorithm using dynamic programming. Remember how DPChange worked from small instances upward? To find the length of a longest path from source (0, 0) to sink (n, m), we will first find the lengths of longest paths from the source to all nodes (i, j) in the grid, expanding slowly outward from the source. At first glance, you may think that we have created additional work for ourselves by solving n × m different problems instead of a single problem. Yet SouthOrEast also solves all these smaller problems, just as RecursiveChange and DPChange both computed MinNumCoins(m) for all values of m < money. The trick behind dynamic programming is to solve the smaller problems once rather than billions of times.
We will henceforth denote the length of a longest path from (0, 0) to (i, j) as si, j.Computing s0, j (for 0 ≤ j ≤ m) is easy, since we can only reach (0, j) by moving right (→) and do not have any flexibility in our choice of path. Thus, s0, j is the sum of the weights of the first j horizontal edges leading out from the source. Similarly, si, 0 is the sum of the weights of the first i vertical edges from the source. See the figure below.
For i > 0 and j > 0, the only way to reach node (i, j) is by moving down from node (i − 1, j) or by moving right from node (i, j − 1). Thus, si, j can be computed as the maximum of two values:
- si - 1, j + weight of the vertical edge from (i - 1, j) to (i, j)
- si, j - 1 + weight of the horizontal edge from (i, j - 1) to (i, j)
Figure: Computing si, 0 and s0, j is easy because there is only one path from the source to (i, 0) and only one path from the source to (0, j).
Now that we have computed s0, 1 and s1, 0, we can compute s1, 1. You can arrive at (1, 1) by traveling down from (0, 1) or right from (1, 0). Therefore, s1, 1 is the maximum of two values:
- s0, 1 + weight of the vertical edge from (0, 1) to (1, 1) = 3 + 0 = 3
- s1, 0 + weight of the horizontal edge from (1, 0) to (1, 1) = 1 + 3 = 4
Since our goal is to find the longest path from (0, 0) to (1, 1), we conclude that s1, 1 = 4. Because we chose the horizontal edge from (1, 0) to (1, 1), the longest path through (1, 1) must use this edge, which we highlight in the figure below.
Figure: Computing s1,1 uses the horizontal edge from (1, 0), which is highlighted.
Similar logic allows us to compute the rest of the values in column 1; for each si, 1, we highlight the edge that we chose leading into (i, 1), as shown in the figure below.
Figure: Computing all values si, 1 in column 1.
Exercise Break Compute all five values of si, 2 in column 2. Check your solution at Cogniterra.
Continuing column-by-column, as shown in the figure at the bottom, we can compute every score si, j in a single sweep of the graph, eventually calculating s4, 4 = 34.
For each node (i, j), we will highlight the edge leading into (i, j) that we used to compute si, j. However, note that we have a tie when we compute s3, 3.
The animation below shows the value si, j being computed at every node of the grid. Each node takes the larger of the score above it plus the vertical edge weight and the score to its left plus the horizontal edge weight; the recurrence beneath the grid is evaluated for whichever node is being scored, and the option that loses fades to gray. Nodes in the top row and the leftmost column have only one way in, so there is nothing to compare. At node (3, 3) both ways in give 22, and the tie is broken horizontally.
To reach (3, 3), we could have used either the horizontal or vertical incoming edge, and so we will highlight both of these edges in the completed graph in the figure below.
STOP and Think We have only thus far discussed how to find the length of a longest path. How could you use the highlighted edges in the figure from the previous step, reproduced below, to reconstruct a longest path?
We now have the outline of a dynamic programming algorithm for finding the length of a longest path in the Manhattan Tourist Problem, called ManhattanTourist. In the following pseudocode, downi, j and righti, j are the respective weights of the vertical and horizontal edges entering node (i, j). We denote the matrices holding (downi, j) and (righti, j) as Down and Right, respectively.
ManhattanTourist(n, m, Down, Right)
s0, 0 ← 0
for i ← 1 to n
si, 0 ← si-1, 0 + downi-1, 0
for j ← 1 to m
s0, j ← s0, j−1 + right0, j-1
for i ← 1 to n
for j ← 1 to m
si, j ← max{si - 1, j + downi-1, j, si, j - 1 + righti, j-1}
return sn, mCode Challenge Find the length of a longest path in the Manhattan Tourist Problem. Solve at Cogniterra or Rosalind.Solve it with the autograderFree to start in the interactive text
- Input: Integers n and m, followed by an n × (m + 1) matrix Down and an (n + 1) × m matrix Right. The two matrices are separated by the "-" symbol.
- Output: The length of a longest path from source (0, 0) to sink (n, m) in the rectangular grid whose edges are defined by the matrices Down and Right.
Exercise Break Modify ManhattanTourist to find the length of the longest path from source to sink in the graph shown below. Check your solution at Cogniterra.
Hint: You may want to try doing this exercise by hand.
