|
|
|
|
Dynamic
Programming Supplements
|
|
|
Supplements are PDF files covering subjects not
included in the textbook.
|
|
|
|
Instead of starting at a final state and working backwards, for
many problems it is possible to determine the optimum by an opposite
procedure called forward recursion. Backward recovery is then
used to identify the optimal path. The procedure may be more convenient
for some classes of problems, but for those in which the final
state set is unknown, it is the only feasible approach. Forward
recursion also leads to a very powerful procedure called reaching,
described in the next section. |
|
|
|
Backward and forward recursion are known as pulling methods because
the optimal decision policy d*(s) tells us how to pull ourselves
into a particular state from a predecessor state. Reaching is
an alternative solution technique that combines the forward generation
of states with forward recursion on an acyclic network. In effect,
the optimal decision policy is derived while the state space is
being generated, a concurrent operation. When all the states have
been generated, the optimization is complete. The solution is
found with the backward recovery procedure. |
|
