2.7 Dynamic Programming
Dynamic programming computes the values for small
subproblems and stores those values in a
matrix. The stored values are then
used to solve larger subproblems (without incurring the cost of
recomputing the smaller subproblems) and so on until the solution to
the overall problem is found. The term "dynamic
programming" is a bit of a misnomer since it
doesn't involve changing values over time as the
word "dynamic" suggests.This approach relies on having a data structure available to store
the intermediate values as the algorithm proceeds. The data structure
may require a fair amount of computer memory, but the overall speed
of the algorithm often makes the memory cost worthwhile. In this
section, we'll use a Perl multidimensional array,
namely a simple two-dimensional matrix, to solve an approximate
string matching problem.Our algorithm will find a (shorter) pattern in a (longer) text.
We'll start with a two-dimensional array, or matrix.
The columns of the matrix will be associated with the (shorter)
pattern, and the rows of the matrix will be associated with the
(longer) text. The zeroth row and the zeroth column will be
initialized to the appropriate starting values.
We'll then calculate each value in the matrix by
examining adjacent, already calculated values in conjunction with the
characters of the pattern and the text. After the entire matrix has
been filled in, we'll have the answer to our
problem. That is, we'll find the position(s) in the
text that most closely match the pattern, and we'll
do so by simply examining the values in the last row of the matrix. |
لطفا منتظر باشید ...
