S(i,j) = max_{k=1...m} [ S(k,j-1) +v(i,j,k) ], | (1) |
In this most general form, the algorithm
is quite expensive.
The cost is on order n*m*m. For a large
number of states the problem quickly becomes
impractical.
The easiest way to reduce
the cost is to limit the number of states that
we must search when moving from one decision to
another.
The next two subsections describe ways
to limit the search that are practical for certain
classes of problems.