The Manhattan Tourist Problem
Explore the Manhattan Tourist Problem and see how it’s represented using directed graphs.
We'll cover the following...
What is the best sightseeing strategy?
Imagine you’re 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’re 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.
Map of Manhattan as a directed graph
We’ll represent the map of Manhattan as a directed graph ManhattanGraph in which we model each intersection as a node and each city block between two intersections as a directed edge indicating the legal direction of travel (↓ or →), as shown in above figure (right). 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 ...