Biomedical Engineering Reference
In-Depth Information
Dynamic programming can address this computational and time dilemma by creating a matrix to
store the values for
A
i
,
B
j
, and
MaxValue
for each combination of
i
and
j
. Instead of solving one
complex CPU- and RAM-intensive problem, the task is decomposed into hundreds or even thousands
of easily and quickly solved problems. For example, consider the solution matrix for
MaxValue
in
Figure 8-8
. The solution set to
MaxValue
computed earlier for
A
1
appears in the first row of the
matrix. Examining only this first row, it can be seen that there are two solutions to
MaxValue
,
B
5
and
B
10
, each of which results in a value of 8.
Figure 8-8. Solution Matrix for
MaxValue
for
A
i
and
B
j
. The solution to
MaxValue
is
A
3
and
B
3
with
MaxValue
= 12.
With the completed solution matrix available for examination, it's a trivial matter to locate the best
values for
i
and
j
, second-best, and so on. The same approach can be extended to any number of
dimensions. For example, consider adding a third variable, as in
Figure 8-9
. The equation for
MaxValue
now takes the form:
MaxValue = f
(
A
i
,
B
j
,
C
k
)
Figure 8-9. Dynamic Programming Problem with Added Dimensionality.
Values for
A
i
,
B
j
, and
C
k
are contained in the tree structure (left). The
exhaustive solution to
MaxValue
involves evaluating every combination of
i
,
j
, and
k
.