The Manhattan tourist problem – Dynamic programming activity

  1. Imagine walking through Manhattan in New York City. You don’t have much time, but at least you want to walk past some interesting places. On a scale from 0 to 10 with 10 being the highest, tell how interested you would be in walking past the following places:

___ FAO Schwartz Toy Store___ Chinatown

___ WorldTradeCenter memorial___ View of the Statue of Liberty

___ Carnegie Hall___ EmpireStateBuilding

___ A musical on Broadway___ Times Square

______

Fill in your own. Some places are more interesting to some people than to others, that’s OK.

  1. The streets in Manhattanare arranged in a rectangular grid, similar to what you see below. You are starting at the northwest corner and will walk south and east to the southeast corner without ever going west or north. Follow the arrows, but make a choice at every intersection you come to. Along the way, you have the opportunity to walk by different places of interest, and the rating of the place on each block is shown next to the arrow. The question is: What route through the streets will give you the highest total score for all the places you pass by?
  1. Take a minute to try a few paths through the city and sum up the score of the places you pass by. Don’t write all over it, though. What is the largest number you get? How sure are you that you found the best path?
  1. The idea of dynamic programming is to solve smaller problems and to use those solutions to build solutions of larger problems. You could call the overall problem the 4-5 problem, since there are 4 intersections down and 5 across. What would the 2-2 problem be? What would its solution be? Write the best score in the 2-2 circle. What is the 3-1 problem? Write the score. How can you use the solution of the 2-2 problem and the 3-1 problem to solve the 3-2 problem? Now solve the 4-1 problem and then the 4-2 problem.
  1. You can leave a record of the best score for the smaller problems by writing numbers in the circles above. Write out in a sentence what these numbers mean:
  1. Once you have written in numbers above and to the left of a circle that is still empty, you can find the best score for the empty circle and fill that in. You can keep doing that all across the grid until you know the best score for the 4-5 problem.
  1. Now think back – what was the LAST step that got you the best score for the 4-5 problem? Now you know the LAST street to walk down. Now what was the last step to solve the 3-5 problem? Keep working backwards to the beginning, and you’ve found the best path!

Developed by Craig L. Zirbel, see