Dynamic Programming         Sat Sep 30 06:59:20 EDT 2006
Problem Help

A dynamic programming algorithm is an algorithm with two
characteristics:

A.  A problem P is parameterized in such a way that some
    parametric set of subproblems can be solved recur-
    sively.  For example, the original problem P might
    be parameterized as P(i,m) for some integers 0 <= i
    < N, 0 <= m < N.  And each problem P(i,m) for 0 < m
    might be solvable fairly quickly (say in time pro-
    portional to N) from the solutions to all the pro-
    blems P(i,m-1) for 0 <= i < N,  while the problems
    P(i,0) are readily solvable.

    An example is the problem of finding the length of
    the shortest path from node 0 to node N-1 in an un-
    directed graph with nodes 0, 1, ..., N-1 and edges
    each of which have some length > 0.  Then let P(i,m)
    be the problem of finding the length of the shortest
    path from node 0 to node i that has no more than m
    edges.  Then we want to solve P(N-1,N-1), because
    any path with more than N-1 edges would have a cycle
    that could be removed to make the path shorter.
    
    Treat two nodes that are NOT connected as if they
    were connected by an edge whose length is infinity
    (or some number much larger than any possible short-
    est path).  Then P(0,0) == 0 and P(i,0) = infinity
    for 0 < i < N.  And for m > 0, P(i,m) is the minimum
    of P(k,m-1)+edge_length(k,i) for all nodes 0 <= k
    < N.

    Note that if the length of every present edge is 1,
    this problem is just the breadth first search
    problem with N-1 as the only goal node (see the help
    file on breadth_first_search).  It can be modified
    to have a set of goal nodes, and is easier to pro-
    gram than breadth first search.  But dynamic pro-
    gramming does not generally work as well as breadth
    first search if the nodes cannot be organized into a
    simple array.

B.  The solution to one of the parameterized problems
    (e.g. P(i,m)) is typically used very many times in
    computing the solution to the final problem recur-
    sively, so it is important to remember this solution
    as a table entry and not recompute it every time it
    is needed.

    Indeed, in our example P(k,m-1) is used to compute
    P(i,m) for every i, therefore it is used N times.


The word `programming' in `dynamic programming' refers
to describing the table of subproblem solutions and
the order in which the table will be computed.

Dynamic programming can also be used to compute an
actual shortest path, and not just the length of such a
path.  There are two ways of doing this:

C. For each P(i,m) record in P_previous(i,m) the last
   node k that is just before i on some shortest path
   from node 0 to node i.  This can be computed when
   computing P(i,m):

	when setting P(i,m) = P(k,m-1)
	                    + edge_length(k,i)
	     also set P_previous(i,m) = k

D. After computing P(i,m) for all i and m, backtrack
   to build an end segment of the path as follows:

   	initially the end segment is just the node N-1
	          and m = N-1
	while 0 is not the first node in the end
	      segment:
	    let i be the first node in the end segment
	    find a k such that
	    	P(i,m) = P(k,m-1) + edge_length(k,i)
	        and add k to the beginning of the end
		segment
	    set m = m-1

The first step in solving any dynamic programming
problem is to parameterize the problem.  But notice
that in our example, the parameter m is not even hinted
at by the original problem statement, which is just to
find the distance between 0 and N-1.  We say that m is a
`hidden parameter'.  The essence of solving a dynamic
programming problem is to find the hidden parameter
(or parameters) that are needed to make a fast recursive
algorithm.


The Traveling Salesman Problem
--- --------- -------- -------

Some `intractable' problems have good dynamic program-
ming solutions WHEN THE PROBLEM PARAMETERS ARE SMALL
ENOUGH.  An example is the traveling salesman problem:
find the shortest path from node 0 to node N-1 that
visits all the nodes just once.  The subproblem for this
is P(i,S): find the shortest path from node 0 to node i
that visits every node in the set S of nodes just once.
Then P(i,{0,1,...,N-1}) is the answer.

However to compute the answer one needs to solve the
subproblem for 2**N values of S, and there are on the
order of N*(2**N) subproblems overall.  For N <= 15 this
is doable.


File:		dynamic_programming
Author:		Bob Walton <walton@deas.harvard.edu>
Date:		See top of file.

The authors have placed this file in the public domain;
they make no warranty and accept no liability for this
file.

RCS Info (may not be true date or author):

    $Author: walton $
    $Date: 2006/09/30 10:58:15 $
    $RCSfile: dynamic_programming,v $
    $Revision: 1.11 $