21.1. Introduction

Dynamic Programming is an effective algorithm design technique built on Bellman’s Principle of Optimality which states that ‘an optimal sequence of decisions has the property that whatever the initial state and decisions are, the remaining decisions must constitute an optimal decision sequence with regard to the state resulting from the first decision’.

The dynamic programming strategy is applicable to optimization problems, which comprise an objective function that needs to be maximized or minimized, subject to constraints that need to be satisfied. A candidate solution that satisfies the constraints is termed a feasible solution and when a feasible solution results in the best objective function value, it is termed an optimal solution.

The greedy method (discussed in Chapter 20) also works over problems whose characteristics are as defined above and obtains optimal solutions to these problems. How then is a greedy method different from dynamic programming?

A greedy method works in an iterative fashion, selecting objects constituting the solution set one by one and constructing a feasible solution set, which eventually turns into an optimal solution set. However, there are problems where generating a single optimal decision sequence is not always possible and therefore, a greedy method might not work on these problems.

It is here that dynamic programming finds its rightful place. Dynamic programming, unlike the greedy method, generates multiple decision sequences using Bellman’s principle of optimality and eventually delivers the best decision sequence that leads to the optimal solution to the problem. Also, dynamic programming ensures that any decision sequence that is being enumerated but does not show promise of being an optimal solution is not generated. Thus, to favor the enumeration of multiple decision sequences, dynamic programming algorithms are always recursive in principle.

Let P(1, n) denote a problem, which demands an optimal sequence of n decisions as its solution, with an initial problem state S₀. Let (x₁, x₂,...x_n) be the n decision variables with regard to the problem. Let us suppose that from among a set of k decisions {d₁, d₂,...d_k} available for decision variable x₁, a decision x₁ = d_j was taken, which results in a problem state S₁. According to the principle of optimality, whatever be the decision d_j taken on x₁, the remaining decision sequence pertaining to decision variables (x₂, x₃, ...x_n) must constitute an optimal sequence with regard to the problem state S₁.

Generalizing, if S_i is the respective problem state following each of the decisions d_i, 1 ≤ i ≤ k, for the decision variable x₁, and Γ_i are the optimal decision sequences with regard to the rest of the decision variables, for the problem states S_i, then according to the principle of optimality the final optimal decision sequence with regard to the problem whose initial state is S₀, is the best of the decision sequences, d_iΓ_i, 1 ≤ i ≤ k.

It is therefore quite obvious that dynamic programming generates many decision sequences, but the strategy employing the principle of optimality ensures that those sequences which are sub-optimal are not generated, as far as possible. In the worst case, if there are n decision variables each of which has d choices for their respective decisions, then the total number of decision sequences generated would be dⁿ, which is exponential in nature. Despite this observation, dynamic programming algorithms for most problems have reported polynomial time complexity considering the fact that the sub-optimal decision sequences are not generated by the strategy.

It is prudent to apply the principle of optimality in a recursive fashion considering the large sequence of decisions that are generated, each with regard to the problem states arising out of the earlier decisions that are taken. Hence, dynamic programming algorithms are always governed by recurrence relations, solving which one can easily attain the optimal decision sequence for the problem concerned. Adhering to the norms of recursion, the base cases for the recurrence relations need to be constructed from the respective problem definitions.

The solution of the recurrence relations defining a dynamic programming algorithm can be undertaken in two ways, viz., forward approach and backward approach.

In the forward approach, if (x₁, x₂, ...x_n) are the n decision variables on which an optimal decision sequence has to be constructed, then the decision on x_i is made in terms of the optimal decision sequences for x_i+1, x_i+2, ...x_n. On the contrary, in the backward approach, the decision on x_i is made in terms of the optimal decision sequences for x₁, x₂, ...x_i-1. Thus, the forward approach deals with “look ahead” decision making and the backward approach deals with “look back” decision making.

In practice, formulating the recurrence relation for a problem works out easier, when a backward approach is followed. The recurrence relation, however, is solved forwards. For a forward approach based on recurrence relation, the solution of the relation becomes easier when backward solving is undertaken beginning with the last decision.

Another important characteristic of dynamic programming strategy is that the solutions to sub-problems obtained by the respective optimal decision subsequence are preserved thereby avoiding re-computation of values. Therefore, in most cases, the values computed by the recurrence relations can be tabulated, which permits the effective transformation of a recursive process into iterative program code, while implementing dynamic programming algorithms. Thus, most dynamic programming algorithms can be expressed as iterative programs.

The ensuing sections demonstrate the application of dynamic programming to the problems of 0/1 knapsack, traveling salesperson, all-pairs shortest paths and optimal binary search trees.

21.2. 0/1 knapsack problem

The 0/1 knapsack problem is similar to the knapsack problem discussed in section 20.2 of Chapter 20, but with the difference that none of the objects selected may be dismantled while pushing them into the knapsack. In other words, x_i the proportion of objects selected could be either 1 when the object is fully selected for inclusion in the knapsack, or 0, when the object is rejected for it does not completely fit into the knapsack.

The 0/1 knapsack problem is therefore defined as:

subject to

[21.1]

where, O₁, O₂, … O_n indicate n objects, and (p₁, p₂, … p_n) and (w₁, w₂, … w_n) represent their profits and weights, respectively. Here, M is the capacity of the knapsack and (x₁, x₂, … x_n) are the proportion of objects selected, which can be either 0 or 1. The objective is to determine the sequence of objects which will fit into the knapsack and yield maximum profits.

How does dynamic programming work to obtain the recurrence relation that will help obtain the optimal decision sequence?

21.2.1. Dynamic programming-based solution

Let KNAP0/1 (1, n, M) indicate the 0/1 knapsack problem instance, which demands n optimal decisions with regard to its selection of objects that fit into a knapsack whose capacity is M. With regard to x₁, there can only be two decisions. If (x₁ = 0) then the first object is rejected and therefore the optimal decision sequence involves solving the sub-problem KNAP0/1(2, n, M). If (x₁ = 1) then the first object is selected and therefore the optimal decision sequence involves solving the sub-problem KNAP0/1(2, n, M-w1).

Let g_j(y) be the optimal solution (maximal profits) to the sub-problem KNAP0/1(j+1, n, y). The objective is to obtain the optimal solution g₀(M) to the original problem KNAP0/1 (1, n, M). There can only be two decisions with regard to the first decision on x₁, viz., x₁ = 0 or x₁ = 1. Following the principle of optimality, g₀(M) can be computed as:

[21.2]

Here g₁(M) denotes the optimal solution to the rest of the sub-problem, with no profits accrued so far and with M intact, on account of the first decision x₁ = 0. g₁(M-w₁) + p1 denotes the optimal solution to the rest of the sub-problem with a profit of p₁ gained already and a decreased capacity of M-w₁, on account of the first decision x₁ = 1. Generalizing to accommodate the optimal solutions with regard to intermediary sequences for the sub-problems concerned:

[21.3]

It can be seen that the recurrence relation [21.3] models a forward approach and the base cases can be framed using the knowledge that g_n(y) = 0, ∀ y, since n decisions have already been taken by then and therefore there are no profits to be earned.

Solving backward beginning with g_n(y), we obtain g_n-1(y) by substituting i = n-1 in equation [21.3], from g_n-1(y) we obtain g_n-2(y) and so on until we finally arrive at g₀(M) that yields the optimal solution to the 0/1 knapsack problem.

A backward approach to the dynamic programming algorithm for the 0/1 knapsack problem, would try to compute g_n(M) as the optimal solution to the problem KNAP0/1(1, n, M), yielding the following recurrence relation:

[21.4]

Tracking which among the two decisions gave the maximum value can help fix the value of the decision variable x_i concerned. Thus, g₃(60) obtains its maximum value from g₂(20) + 50, which decides on including the object w₃ = 40 into the knapsack and therefore sets x₃ = 1. Proceeding in a similar way, the optimal values of the decision variables turn out to be (x₁, x₂, x₃) = (1, 0, 1). The maximum profit earned is 60 with the knapsack capacity utilized to be 60.

21.3. Traveling salesperson problem

The traveling salesperson problem deals with finding the optimal cost of undertaking a tour that begins with a city, visiting all other cities charted out in the tour once, without revisiting any one of them again, before returning to the city from where the tour started.

Let G = (V, E) where V is the set of vertices and E is the set of edges, be a weighted digraph with c_ij indicating the cost (weight) of edge <i, j>. Let |V| = n, n >1 be the number of vertices. The cost matrix (c_ij) n X n is defined as c_ij > 0, for all i and j, and c_ij = ∞, if edge <i, j> does not exist in E.

A tour of G is a directed cycle that begins from a vertex S and includes all other vertices of G before it ends in vertex S. The cost of the tour is the sum of the costs of all the edges. A minimum cost tour is a tour that reports the minimal cost. The traveling salesperson problem concerns finding the minimum cost tour from a source node S.

21.3.1. Dynamic programming-based solution

The recurrence relation of the dynamic programming-based solution for the traveling salesperson problem can be framed as follows.

Let g(x, y) denote the minimum cost of the tour undertaken from node x, traveling through all other nodes in y before ending the tour at the source node S. Without loss of generality, let us suppose that V = {1, 2, 3, …n} are the n nodes in the weighted digraph and node {1} is the source node.

Following the principle of optimality, the recurrence relation to obtaining the minimum cost tour is given by:

[21.5]

To obtain g(1, V-{1}), a series of decision sequences with regard to the tour moving over to the next node k, 2 ≤ k ≤ n from the source node, need to be recursively computed.

Generalizing, for i ∉ T:

[21.6]

Equation [21.6] can now be used to undertake recursive computations for the intermediary decision sequences. The base case is reached when there are no more nodes to visit during the tour before ending the tour at the source node {1}. The base cases are therefore given by:

[21.7]

21.3.2. Time complexity analysis and applications of traveling salesperson problem

The number of g(i, T) functions that are computed before equation [21.5] is used to compute g(1, V-{1}) is given by:

This is so since for each set T during the intermediary computations, there are (n-1) choices for i. Therefore, the number of distinct sets of T, excluding 1 and i is . Each g(i, T) requires (k-1) comparisons when the cardinality of the set T is k. Hence, the time complexity is given by Θ(n². 2ⁿ).

The traveling salesperson problem finds its application in areas such as planning, scheduling, vehicle routing, logistics and packing, robotics and so forth.

21.4. All-pairs shortest path problem

The all-pairs shortest path problem deals with finding the shortest path between any pair of cities given a network of cities.

Let G = (V, E) be a weighted digraph with n vertices represented by V and edges <i, j> represented by E. Let (C)_n×n denote the cost (weight) matrix where C_ij = 0, for i = j and C_ij = ∞, for < i.j > ∉ E. The all-pairs shortest path problem concerns such a graph G = (V, E) where the vertices V represent cities and the edges E represent the connectivity between the cities, and the cost matrix (C)_n×n represents the distance matrix between the cities. Thus, C_ij denotes the distance between the cities represented by vertices i and j.

It is possible that the distance between two cities i, j connected by a direct edge, can be longer than a path i→k→j, where k is an intermediate city between i and j. The solution to the all-pairs shortest path problem is to obtain a matrix S which gives the minimum distance between cities i and j.

It is possible to solve the all-pairs shortest path problem by repeatedly invoking Dijkstra’s single source shortest path algorithm (discussed in section 9.5.1 of Chapter 9, Volume 2) n times, with each city i as the source, thereby obtaining the shortest paths from city i to all other cities. However, Floyd’s algorithm which will be introduced in the ensuing section employs the principle of optimality over the cost matrix (C)_n×n and obtains the optimal matrix S which obtains the minimum distance between any two cities, in one run.

21.4.1. Dynamic programming-based solution

Floyd’s algorithm adopts dynamic programming to solve the all-pairs shortest path problem. Let S^k(i,j) represent the length of the shortest path from node i to node j passing through no vertex of index greater than k. Then the paths from i to k and k to j must also be shortest paths not passing through a vertex of index greater than (k-1). Making use of this observation, the recurrence relation is framed as:

[21.8]

The shortest path from i to j that does not go through a vertex higher than k, either goes through a vertex k or it does not. If it goes through k, then S^k(i, k) = S^k−1(k, j) and if it does not go through k, then S^k(i, j) = S^k−1(i, j), which explains the recurrence relation for k ≥1.

On the other hand, when k = 0, the shortest path is given by the edges connecting i and j, for all i and j, that is C_ij, which are the base cases for the recurrence relation.

Algorithm 21.1 illustrates Floyd’s algorithm, which employs the recurrence relation described in equation [21.8] to obtain the optimal distance matrix S, which is the solution to the all-pairs shortest path problem.

21.5. Optimal binary search trees

Binary search trees were detailed in Chapter 10, Volume 2. To recall, a binary search tree is a binary tree that can be empty or if non-empty, comprises distinct identifiers representing nodes that satisfy the property of the left child node identifier being less than its parent node identifier and the right child node identifier being greater than its parent node identifier. This leads to the characteristic that all the identifiers in the left subtree of the binary search tree are less than the identifier in the root node and all the identifiers in the right subtree of the binary search tree are greater than the identifier in the root node.

Figure 21.3 illustrates an example binary search tree representing the keys {h, r, e, k, a, f, c, z}. It can be observed that with h as the root node, the keys {a, c, e, f} which form the left subtree are less than key h of the root node and the keys {k, r, z} which form the right subtree are greater than the key h of the root node. Besides, each parent node key is such that the left child node key is less than itself and the right child node key is greater than itself.

Given a set of keys, for each permutation or arrangement of the keys in the list, a binary search tree can be constructed resulting in a variety of binary search tree structures each with its own behavioral characteristics. Thus, each binary search tree could be associated with a cost with regard to successful/unsuccessful searches performed on them, as discussed in illustrative problem 10.4, in Chapter 10, Volume 2. To recollect, if S = {a₁, a₂, a₃, … a_n} is a set of keys and T_k are the set of associated binary search trees that can be constructed out of S, then the cost of a binary search tree is given by:

[21.9]

where p_i, 1 ≤ i ≤ n, is the probability with which a_i is searched for (probability of successful search) and q_j, 0 ≤ j ≤ n, is the probability with which a key X, a_j ≤ X ≤ a_j+1 is unsuccessfully searched for (probability of unsuccessful search) on a binary search tree T_k.

The cost of the binary search tree can also be defined in terms of the depth of the nodes as:

[21.10]

where depth(i) indicates the depth of the external nodes indicated as squares, at which the unsuccessful search logically ends (see section 10.2, Chapter 10, Volume 2, for more details).

Dynamic programming helps to obtain the optimal binary search tree by working over decision sequences and applying the principle of optimality, to select the right node at each stage which will ensure minimal cost.

21.5.1. Dynamic programming-based solution

Given the list of keys S = {a₁, a₂, a₃, … a_n} and the probabilities p_i, 1 ≤ i ≤ n, and q_j, 0 ≤ j ≤ n the objective is to obtain the optimal binary search tree using dynamic programming.

Let T_ij be the minimum cost tree for the subset of keys S_ij = {a_i+1, a_i+2, a_i+3 … a_j} with cost C_ij and root R_ij. By this description and notation, T_ii denotes an empty tree with cost C_ii = 0. Let the weight W_ij of T_ij be defined as:

[21.11]

The weight W_ii of the empty tree T_ii would be q_i.

The tree T_ij consists of a root a_k, i ≤ k ≤ j with its left subtree T_ik-1 representing the minimum cost tree for keys S_ik−1 = {a_i+1, a_i+2, a_i+3, … a_k−1} and right subtree T_kj representing the minimum cost tree for keys S_kj = {a_k+1, a_k+2, a_k+3, … a_j}, as shown in Figure 21.4.

It can be inferred that when (i = k-1) the left subtree is empty and when (k = j) the right subtree is empty.

The construction of T_ij with a_k, T_ik-1 and T_kj, results in the depth of nodes in the left and right subtrees of T_ij increasing by 1, in respect of their earlier depths when they belonged to T_ik-1 and T_kj. The cost C_ij of T_ij defined by equation [21.10], can now be written as:

[21.12]

Since:

[21.13]

we obtain:

[21.14]

To find the optimal cost tree T_ij, we need to choose the root node a_k, i < k ≤ j with T_ik-1 and T_kj as the left and right subtrees, compute the cost and then select the tree with the minimal cost. Therefore, the recurrence relation that computes the minimal cost tree is given by:

[21.15]

The minimum cost tree T_0n for the list S = {a₁, a₂, … a_n} can be obtained by solving for C_0n from the equation [21.15]. The base cases for the recurrence relation are given by C_ii = 0 and W_ii = q_i, 0 ≤ i ≤ n. To compute W_ij in equation [21.15] easily, the following equation derived from equation [21.11] by mere manipulation of the terms, can be used effectively.

[21.16]

21.5.2. Construction of the optimal binary search tree

The optimal binary search tree T_0n for n keys can be easily constructed by tracking that index k at which point min_i<k≤j(C_ij−1 + C_kj) attains its minimum value in equation [21.15], while computing the cost C_ij for the subtree T_ij. Thus, the root R_ij for the subtree T_ij is a_k. This means that the left subtree T_ik-1 of a_k shall comprise the keys {a_i+1, a_i+2, … a_k-1} and the right subtree T_{k, j} shall comprise the keys {a_k+1, a_k+2, … a_kn}, whose root nodes concerned will be arrived at, following similar arguments and computations. Eventually, when C_0n is computed, R_0n = a_k denotes the root node of the optimal binary search tree represented by T_0n.

Algorithm 21.2 illustrates the procedure to obtain the optimal binary search tree, given the list of keys S = {a₁, a₂, a₃, … a_n} and the probabilities p_i, 1 ≤ i ≤ n and q_j, 0 ≤ j ≤ n.

The demonstration of procedure Optimal_BST on a list of keys with known probabilities of successful search and unsuccessful search has been illustrated in example 21.5. It can be seen that the computations with regard to the recurrence relation described by equation [21.15] have been organized in the increasing order of value of j –i, as specified in the algorithm.

21.6. Illustrative problems