12.1 Overview of Dynamic Programming

We start our discussion with a simple DP algorithm for computing shortest paths in a graph.

In general, the solution to a DP problem is expressed as a minimum (or maximum) of possible alternate solutions. Each of these alternate solutions is constructed by composing one or more subproblems. If r represents the cost of a solution composed of subproblems x₁, x₂, ..., x_l, then r can be written as

The function g is called the composition function, and its nature depends on the problem. If the optimal solution to each problem is determined by composing optimal solutions to the subproblems and selecting the minimum (or maximum), the formulation is said to be a DP formulation. Figure 12.2 illustrates an instance of composition and minimization of solutions. The solution to problem x₈ is the minimum of the three possible solutions having costs r₁, r₂, and r₃. The cost of the first solution is determined by composing solutions to subproblems x₁ and x₃, the second solution by composing solutions to subproblems x₄ and x₅, and the third solution by composing solutions to subproblems x₂, x₆, and x₇.

DP represents the solution to an optimization problem as a recursive equation whose left side is an unknown quantity and whose right side is a minimization (or maximization) expression. Such an equation is called a functional equation or an optimization equation. In Equation 12.1, the composition function g is given by f (j) + c(j, x). This function is additive, since it is the sum of two terms. In a general DP formulation, the cost function need not be additive. A functional equation that contains a single recursive term (for example, f (j)) yields a monadic DP formulation. For an arbitrary DP formulation, the cost function may contain multiple recursive terms. DP formulations whose cost function contains multiple recursive terms are called polyadic formulations.

The dependencies between subproblems in a DP formulation can be represented by a directed graph. Each node in the graph represents a subproblem. A directed edge from node i to node j indicates that the solution to the subproblem represented by node i is used to compute the solution to the subproblem represented by node j. If the graph is acyclic, then the nodes of the graph can be organized into levels such that subproblems at a particular level depend only on subproblems at previous levels. In this case, the DP formulation can be categorized as follows. If subproblems at all levels depend only on the results at the immediately preceding levels, the formulation is called a serial DP formulation; otherwise, it is called a nonserial DP formulation.

Based on the preceding classification criteria, we define four classes of DP formulations: serial monadic, serial polyadic, nonserial monadic, and nonserial polyadic. These classes, however, are not exhaustive; some DP formulations cannot be classified into any of these categories.

Due to the wide variety of problems solved using DP, it is difficult to develop generic parallel algorithms for them. However, parallel formulations of the problems in each of the four DP categories have certain similarities. In this chapter, we discuss parallel DP formulations for sample problems in each class. These samples suggest parallel algorithms for other problems in the same class. Note, however, that not all DP problems can be parallelized as illustrated in these examples.