Lesson 5.3
The Manhattan Tourist Problem
Watch the lectureThe Manhattan Tourist Problem
What is the best sightseeing strategy?
Imagine you are a tourist in Midtown Manhattan, and you want to see as many sights as possible on your way from the corner of 59th Street and 8th Avenue to the corner of 42nd Street and 3rd Avenue (figure below). However, you are short on time, and at each intersection, you can only move south (↓) or east (→). You can choose from many different paths through the map, but no path will visit all the sights. The challenge of finding a legal path through the city that visits the most sights is called the Manhattan Tourist Problem.
Figure: A simplification of Midtown Manhattan. You start at the intersection of 59th Street and 8th Avenue in the northwest corner and end at the intersection of 42nd Street and 3rd Avenue in the southeast corner, traveling only south or east between intersections. The attractions shown are: Carnegie Hall (1), Tiffany & Co. (2), the Sony Building (3), the Museum of Modern Art (4), the Four Seasons Hotel (5), St. Patrick's Cathedral (6), the General Electric Building (7), Radio City Music Hall (8), Rockefeller Center (9), the Paramount Building (10), the New York Times Building (11), Times Square (12), the General Society of Mechanics and Tradesmen (13), Grand Central Terminal (14), and the Chrysler Building (15).
We will represent the map of Manhattan as a directed graph ManhattanGraph in which we model each intersection as a node and represent each city block between two intersections as a directed edge indicating the legal direction of travel (↓ or →), as shown below. We then assign each directed edge a weight equal to the number of attractions along the corresponding block. The starting (blue) node is called the source node, and the ending (red) node is called the sink node. Adding the weights along a path from the source to the sink yields the number of attractions along that path; therefore, to solve the Manhattan Tourist Problem, we need to find a maximum-weight path connecting the source to the sink (also called a longest path) in ManhattanGraph.
Figure: The directed graph ManhattanGraph in which every edge is weighted by the number of attractions along that city block (edge weights equal to 0 are not shown).
We can model any rectangular grid of streets using a similar directed graph; the figure below shows the graph for a hypothetical city with even more attractions. In contrast to the Cartesian plane, we orient the axes of this grid down and to the right. Therefore, the blue source node is assigned the coordinates (0, 0), and the red sink node is assigned the coordinates (n, m).
This discussion implies the following generalization of our original problem.
Manhattan Tourist Problem: Find a longest path in a rectangular city.
- Input: A weighted n × m rectangular grid with n + 1 rows and m + 1 columns.
- Output: A longest path from source (0,0) to sink (n, m) in the grid.
Figure: An n × m city grid represented as a graph with weighted edges for n = m = 4. The bottom left node is indexed as (4, 0), and the upper right node is indexed as (0, 4).
Exercise BreakHow many different paths are there from source to sink in a 16 × 12 rectangular grid? Solve at Cogniterra.
Note: Keep in mind that according to our notation, a 16 × 12 grid contains 17 × 13 = 221 nodes.
Applying a brute force approach to the Manhattan Tourist Problem is impractical because the number of paths is huge. A sensible greedy approach would choose between the two possible directions at each node (→ or ↓) according to how many attractions you would see if you moved only one block south versus moving one block east. For example, in the figure below, we start off by moving east from (0, 0) rather than south because the horizontal edge has three attractions, while the vertical edge has only one. Unfortunately, this greedy strategy may miss the longest path in the long run.
STOP and Think Find a longer path in the graph below.
Sightseeing in an arbitrary directed graph
In reality, the streets in Midtown Manhattan do not form a perfect rectangular grid because Broadway Avenue cuts diagonally across the grid, but the network of streets can still be represented by a directed graph. In fact, the Manhattan Tourist Problem is just a special case of the more general problem of finding the longest path in an arbitrary directed graph, such as the ones shown below.
Longest Path in a Directed Graph Problem: Find a longest path between two nodes in an edge-weighted directed graph.
- Input: An edge-weighted directed graph with source and sink nodes.
- Output: A longest path from source to sink in the directed graph.
STOP and Think What is the length of a longest path between the source and sink in the directed graph shown on the right in the figure below?
If a directed graph contained a directed cycle (e.g., the four central edges of weight 1 in the graph below), then a tourist could traverse this cycle indefinitely, revisiting the same attractions over and over again and creating a path of huge length. For this reason, the graphs that we will consider in this chapter do not contain directed cycles; such graphs are called directed acyclic graphs (DAGs).
Longest Path in a DAG Problem: Find a longest path between two nodes in an edge-weighted DAG.
- Input: An edge-weighted DAG with source and sink nodes.
- Output: A longest path from source to sink in the DAG.
STOP and Think Do you see any similarities between the Longest Path in a DAG Problem and the Longest Common Subsequence Problem?
