- 512,586 hits
Make the frequent cases fast and the rare case correct
Manhattan Tourist Problem – Dynamic Programming
February 19, 2011Posted by on
Imagine walking through Manhattan in New York City. The streets are arranged in a
rectangular grid. You are starting at the northwest corner and will walk south and east to the southeast corner without ever going west or north. Along the way, you have the opportunity to walk by various sites of interest; the number of such sites on each block is indicated by the weight of the path. The question is: What route through the streets will allow you to pass by the largest number of sites of interest?
This problem is well explained in the book An introduction to bioinformatics algorithms By Neil C. Jones, Pavel Pevzner.
The Problem is a simple dynamic programming example and illustrates why a greedy approach does not always work.
Below image is taken from a University lecture . Highly recommend this slide material along with the book explanation to understand this problem.
The Grid shown below illustrate how dynamic programming is better than Greedy approach
Implementation: Python (simpler to initialize matrix)
# Manhattan Tourist Problem using Dynamic programming # The grid used is a 3x3 Grid #From the Input grid form a weight matrix for the Manhattan Avenues along North to South vWeight = [[5,3,0], [3,5,0], [10,3,5], [5,1,2]] #From the Input grid form a weight matrix for the Manhattan Streets along West to East hWeight = [[1,2,5], [2,1,5], [2,3,4], [0,0,0]] # Create a empty matrix which will hold the computed max path taken Manhattan will hold the eventual total path Manhattan = [[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]] Manhattan = 0 # Compute the Horizontal end of each block total path i.e first row for row in range(1, 4): Manhattan[row] = Manhattan[row-1] + vWeight[row-1] # Compute the Vertical end of each block total path i.e first column for col in range(1, 4): Manhattan[col] = Manhattan[col-1] + hWeight[col-1] for row in range(1, 4): for col in range(1, 4): # Computed some sample values to show build up of the Manhattan Matrix #Manhattah = max(Manhattan + vWeight, Manhattan + hWeight) #Manhattan = max(Manhattan + vWeight, Manhattan + hWeight) Manhattan[row][col] = max(Manhattan[row-1][col] + vWeight[col][row-1], Manhattan[row][col-1] + hWeight[row][col-1]) #print MT #print MT print "The Maximum possible path :", Manhattan
labuser@ubuntu:~$ python manhattan.py
The Maximum possible path : 22
The article has only looked into a perfect grid. There is a generalized algorithm described as well where authors represent the improper grid as DAG (Directed Acyclic Graph).
Thanks for Reading !
Algorithm courtesy – An introduction to bioinformatics algorithms By Neil C. Jones, Pavel Pevzner