-1- 20bits ::: http://20bits.com/articles/introduction-to-dynamic-programming/
Excerpt{The code is cool!}:
Optimal Substructure
A problem is said to have optimal substructure if the globally optimal solution can be constructed from locally optimal solutions to subproblems. The general form of problems in which optimal substructure plays a roll goes something like this. Let's say we have a collection of objects called A. For each object o in A we have a "cost," c(o). Now find the subset of A with the maximum (or minimum) cost, perhaps subject to certain constraints.We are given an input array a. I'm going to use Python notation so that a[0:k] is the subarray starting at 0 and including every element up to and including k-1. Let's say we know the subarray of a[0:i] with the largest sum (and that sum). Using just this information can we find the subarray of a[0:i+1] with the largest sum?
Let a[j:k+1] be the optimal subarray, t the sum of a[j:i], and s the optimal sum. If t+a[i] is greater than s then set a[j:i+1] as the optimal array and set s = t. If t + a[i] is negative, however, the contiguity constraint means that we cannot include a[j:i+1] in our subarray since any such subarray will have a smaller sum than a subarray without it. So, if t+a[i] is negative set t = 0 and set the left-hand bound of the optimal subarray to i+1.
To visualize consider the array [1,2,-5,4,7,-2].
Set s = -infinity, t = 0, j = 0, bounds = (0,0) (1 2 -5 4 7 -2 (1)| 2 -5 4 7 -2 (set t=1. Since t > s, set s=1 and bounds = (0,1)) (1 2)|-5 4 7 -2 (set t=3. Since t > s, set s=3, and bounds = (0,2)) 1 2 -5(| 4 7 -2 (set t=-2. Since t < 0, set t=0 and j = 3 ) 1 2 -5 (4)| 7 -2 (set t=4. Since t > s, set s=4 and bounds = (3,4)) 1 2 -5 (4 7)|-2 (set t=11. Since t > s, set s=11 and bounds = (3,5)) 1 2 -5 (4 7) -2| (set t=9. Nothing happens since t < s)This requires only one pass through the array and at each step we're only keeping track of three variables: the current sum from the left-hand edge of the bounds to the current point (t), the maximal sum (s), and the bounds of the current optimal subarray (bounds). In Python:
def msum2(a):
bounds, s, t, j = (0,0), -float('infinity'), 0, 0
for i in range(len(a)):
t = t + a[i]
if t > s: bounds, s = (j, i+1), t
if t < 0: t, j = 0, i+1
return (s, bounds)
bounds, s, t, j = (0,0), -float('infinity'), 0, 0
for i in range(len(a)):
t = t + a[i]
if t > s: bounds, s = (j, i+1), t
if t < 0: t, j = 0, i+1
return (s, bounds)
The Knapsack Problem
Say there are n paintings with weights w1, ..., wn and market values v1, ..., vn. Define A(i,j) as the maximum value that can be attained from considering only the first i items weighting at most j pounds as follows.Obviously A(0,j) = 0 and A(i,0) = 0 for any i ≤ n and j ≤ W. If wi > j then A(i,j) = A(i-1, j) since we cannot include the ith item. If, however, wi ≤ j then A(i,j) then we have a choice: include the ith item or not. If we do not include it then the value will be A(i-1, j). If we do include it, however, the value will be vi + A(i-1, j - wi). Which choice should we make? Well, whichever is larger, i.e., the maximum of the two.
Expressed formally we have the following recursive definition
This problem exhibits both overlapping subproblems and optimal substructure and is therefore a good candidate for dynamic programming. The subproblems overlap because at any stage (i,j) we might need to calculate A(k,l) for several k < i and l < j. We have optimal substructure since at any point we only need information about the choices we have already made.
The recursive solution is not hard to write:
def A(w, v, i,j):
if i == 0 or j == 0: return 0
if w[i-1] > j: return A(w, v, i-1, j)
if w[i-1] <= j: return max(A(w,v, i-1, j), v[i-1] + A(w,v, i-1, j - w[i-1]))
Remember we need to calculate A(n,W). To do so we're going to need to create an n-by-W table whose entry at (i,j) contains the value of A(i,j). The first time we calculate the value of A(i,j) we store it in the table at the appropriate location. This technique is called memoization and is one way to exploit overlapping subproblems. There's also a Ruby module called memoize which does it for Ruby. if i == 0 or j == 0: return 0
if w[i-1] > j: return A(w, v, i-1, j)
if w[i-1] <= j: return max(A(w,v, i-1, j), v[i-1] + A(w,v, i-1, j - w[i-1]))
To exploit the optimal substructure we iterate over all i <= n and j <= W, at each step applying the recursion formula to generate the A(i,j) entry by using the memoized table rather than calling A() again. This gives an algorithm which takes O(nW) time using O(nW) space and our desired result is stored in the A(n,W) entry in the table.
Everyday Dynamic Programming
The above examples might make dynamic programming look like a technique which only applies to a narrow range of problems, but many algorithms from a wide range of fields use dynamic programming. Here's a very partial list.- The Needleman-Wunsch algorithm, used in bioinformatics.
- The CYK algorithm which is used the theory of formal languages and natural language processing.
- The Viterbi algorithm used in relation to hidden Markov models.
- Finding the string-edit distance between two strings, useful in writing spellcheckers.
- The D/L method used in the sport of cricket.
Graphs: Dijkstra's Algorithm
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
## {{{ http://code.activestate.com/recipes/119466/ (r1)
# Dijkstra's algorithm for shortest paths
# David Eppstein, UC Irvine, 4 April 2002
# http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/117228
from priodict import priorityDictionary
def Dijkstra(G,start,end=None):
"""
Find shortest paths from the start vertex to all
vertices nearer than or equal to the end.
The input graph G is assumed to have the following
representation: A vertex can be any object that can
be used as an index into a dictionary. G is a
dictionary, indexed by vertices. For any vertex v,
G[v] is itself a dictionary, indexed by the neighbors
of v. For any edge v->w, G[v][w] is the length of
the edge. This is related to the representation in
where Guido van Rossum suggests representing graphs
as dictionaries mapping vertices to lists of neighbors,
however dictionaries of edges have many advantages
over lists: they can store extra information (here,
the lengths), they support fast existence tests,
and they allow easy modification of the graph by edge
insertion and removal. Such modifications are not
needed here but are important in other graph algorithms.
Since dictionaries obey iterator protocol, a graph
represented as described here could be handed without
modification to an algorithm using Guido's representation.
Of course, G and G[v] need not be Python dict objects;
they can be any other object that obeys dict protocol,
for instance a wrapper in which vertices are URLs
and a call to G[v] loads the web page and finds its links.
The output is a pair (D,P) where D[v] is the distance
from start to v and P[v] is the predecessor of v along
the shortest path from s to v.
Dijkstra's algorithm is only guaranteed to work correctly
when all edge lengths are positive. This code does not
verify this property for all edges (only the edges seen
before the end vertex is reached), but will correctly
compute shortest paths even for some graphs with negative
edges, and will raise an exception if it discovers that
a negative edge has caused it to make a mistake.
"""
D = {} # dictionary of final distances
P = {} # dictionary of predecessors
Q = priorityDictionary() # est.dist. of non-final vert.
Q[start] = 0
for v in Q:
D[v] = Q[v]
if v == end: break
for w in G[v]:
vwLength = D[v] + G[v][w]
if w in D:
if vwLength < D[w]:
raise ValueError, \
"Dijkstra: found better path to already-final vertex"
elif w not in Q or vwLength < Q[w]:
Q[w] = vwLength
P[w] = v
return (D,P)
def shortestPath(G,start,end):
"""
Find a single shortest path from the given start vertex
to the given end vertex.
The input has the same conventions as Dijkstra().
The output is a list of the vertices in order along
the shortest path.
"""
D,P = Dijkstra(G,start,end)
Path = []
while 1:
Path.append(end)
if end == start: break
end = P[end]
Path.reverse()
return Path
## end of http://code.activestate.com/recipes/119466/ }}}
♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥
No comments:
Post a Comment