description
Algebraic dynamic programming (ADP) is a style of dynamic programming
that gives rise to a systematic approach to the development of DP
algorithms. It allows one to design, reflect upon, tune and even test
DP algorithms on a more abstract level than the recurrences that used
to be all that was available to deal with dynamic programming
algorithms. Four steps based on mathematical concepts guide the
algorithm design. Many tricks that have been invented by
practitioners of DP can be expressed as general techniques in ADP. The
common aspects of related algorithms can be cleanly separated from
their differences. On the implementation side, ADP exactly reproduces
the classical DP recurrences. In principle, nothing is lost in terms
of efficiency. All this together makes us feel that Dynamic
Programming is more and more becoming a discipline, rather than a
"matter of experience, talent and luck". How can this be
achieved?
Any DP algorithm evaluates a search space of candidate solutions under
a scoring scheme and an objective function. The classical DP
recurrences reflect the four aspects of search space construction,
scoring, choice, and efficiency in an indiscriminate fashion. In any
systematic approach, these concerns must be separated. The algebraic
approach to be presented here proceeds as follows:
The search space of the problem at hand is described by a yield
grammar, which is a tree grammar generating a string language.
The ADP developer takes the view that for a given input sequence,
"first" the search space is constructed, leading to an enumeration of
all candidate solutions. This is a parsing problem, solved by a
standard device called a tabulating yield parser. The developer
can concentrate on the design of the grammar.
Evaluation and choice are captured by an evaluation algebra.
It is important (and in contrast to traditional presentations of DP
algorithms) that this algebra comprises all aspects relevant to
the intended objective of optimization, but is independent of the
description of the search space. The ADP developer takes the view
that a "second" phase evaluates the candidates enumerated by the first
phase, and makes choices according to the optimality
criterion.
Of course, the interleaving of search space construction and
evaluation is essential to prevent combinatorial explosion. This
interleaving is contributed by the ADP method in a way transparent to
the developer.
By the separate description of search space and evaluation, ADP
produces modular and therefore re-usable algorithm components. Often,
related optimization problems over the same search space can be solved
merely by a change of the algebra. More complex problems can be
approached with a better chance of success, and there is no loss of
efficiency compared to ad-hoc approaches. Avoiding the formulation of
explicit recurrences is a major relief, an effect captured by early
practitioners of ADP in the slogan "No subscripts, no errors!".
people
start
1998
|
