Tricki
a repository of mathematical know-how

When exhaustive search takes too long and a greedy algorithm is not optimal, consider Dynamic Programming

Stub iconThis article is a stub.This means that it cannot be considered to contain or lead to any mathematically interesting information.

Quick description

Dynamic programming is a "smart exhaust," and is often used to find examples in the case where a greedy algorithm does not return an optimal result. In this article, we describe the criteria needed for a problem to posses a dynamic programming (DP) solution. We also give the general algorithm.

Prerequisites

None

Example 1

The basic example of a problem which admits a DP solution is that of finding minimal weight paths of a fixed length between vertices of a weighted, undirected graph G on vertices \left\{1, ..., n\right\}. If we write the weight between vertex i and j as w_{i,j}, we can collect the weights into a matrix W = \left(w_{i,j}\right). Let m^{(t)}_{i,j} denote the minimal weight path of length t starting at vertex i and ending at vertex j. Then we have the recurrence

 m^{(t+1)}_{i,j} = \min_{k} w_{k,j} + m^{(t)}_{i,k}.(1)

Here we have written path weight additively. This suggests an algorithm to determine the minimal weight paths between any two vertices:

  • Initialize M^{(1)} = W

  • for t=1, 2, ..., T-1 do

    • Determine M^{(t+1)} by (1).

At termination, M^{(T)} contains the weights of the minimal weight paths of length T between any pair of vertices. Determining the actual paths is done in a similar manner, essentially replacing \min with argmin in (1). This algorithm runs in \mathcal O(Tn^2) time and \mathcal O(n^2) space.

General discussion

Remark The recurrence relation (1) is just matrix multiplication formula over the (\min, +) semiring (sometimes called the tropical semiring). This implies that M^{(T)} = W^T over that semiring.

Comments

What is a "smart exhaust"?

What is a "smart exhaust"?