ISourceCode

Make the frequent cases fast and the rare case correct

Manhattan Tourist Problem – Dynamic Programming

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

Algorithm :

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[3][3] 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][0] = 0
# Compute the Horizontal end of each block total path i.e first row
for row in range(1, 4):
	Manhattan[row][0] = Manhattan[row-1][0] + vWeight[0][row-1]
# Compute the Vertical end of each block total path i.e first column	
for col in range(1, 4):
	Manhattan[0][col] = Manhattan[0][col-1] + hWeight[0][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[1][1] = max(Manhattan[0][1] + vWeight[1][0], Manhattan[1][0] + hWeight[1][0])
		#Manhattan[1][2] = max(Manhattan[0][2] + vWeight[2][0], Manhattan[1][1] + hWeight[1][1])
			
		Manhattan[row][col] = max(Manhattan[row-1][col] + vWeight[col][row-1], Manhattan[row][col-1] + hWeight[row][col-1])

#print  MT[1][1]
#print  MT[1][2]

print  "The Maximum possible path :", Manhattan[3][3]

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: