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

Fri Dec 19 10:54:56 CET 2014