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 .
Search WWH ::




Custom Search