Characteristics and approaches.

Characteristics and Approaches

We shall now extract some of the properties and techniques that were used to construct solutions to path problems. The two design methods that dominate this process are:

a. Define the problem in terms of subproblems.
b. Construct the recursive relationship between them.

This is easy to accomplish for shortest path problems. Recalling the graph shown in figure 1 we shall do just this.

Figure 1 - A Network Path Problem

Using the function path(u, v) to represent the shortest distance between nodes u and v, we noted that since one had to go through either node f or g to reach t, then:

path(s, t) = min[path(s, f)+path(f, t), path(s, g)+path(g, t)].

We then worked backwards through the zones of the network to construct optimum solutions from the subproblems which were just going to and from nodes in the zones.

Our next step towards solving the problem is to compute values for subproblems and use them to construct the optimum solution. If

every subsolution of an optimum solution is optimum

then we shall be able to construct optimal solutions from optimal subsolutions. This statement or rule is named the Principle of Optimality by those in the dynamic programming field.

The second example from path problems was the dynamic programming solution to all pairs shortest path problem due to Floyd and Warshall. Here, if we recall that we defined subsets of the vertices in a graph as

A₀ = Æ , A₁ = {v₁}, … , A_i = {v₁, …, v_i}, … , A_n = {v₁, …, v_n}.

and define subproblems involving constrained paths as:

d(A_i, v_j, v_k) = distance from v_j to v_k going through only vertices in A_i,

then the recursive relationship between these subproblems is:

d(A_i+1, u, v) = minimum[ d(A_i, v_j, v_k), d(A_i, v_j, v_i+1)+d(A_i, v_i+1, v_k) ].

Let's consider another dramatic example; computing Fibonacci numbers. They are defined by the recursive relationship:

f_n = f_n-1 + f_n-2

which seems to indicate that we should compute them by a top-down recursive procedure. But, as everyone knows, this would be a hideous mistake. An exponential amount of work would be done if we did this since many of the numbers would be computed over and over again. We instead need to compute them in the order f₁ , f₂ , ... , f_n. In other words, we organize the order in which we compute the subproblems, much the same way that we did with the path problems.

Thus two more steps emerge in our process.

c. Characterize the necessary subproblem space.
d. Determine the order in which to compute subproblems.

All that remains is to fill in the subproblem table. The time needed to do this depends on the second important requirement for superb dynamic programming, namely:

there should be numerous common subproblems.

This, in fact, is what separates good recursive divide and conquer algorithms (such as mergesort) from problems that should be solved with the dynamic programming techniques. If there are a lot of common subproblems and the subproblem space is not too large, we can efficiently solve the problem using dynamic programming.