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"?

Post new comment

(Note: commenting is not possible on this snapshot.)

Before posting from this form, please consider whether it would be more appropriate to make an inline comment using the Turn commenting on link near the bottom of the window. (Simply click the link, move the cursor over the article, and click on the piece of text on which you want to comment.)

snapshot
Notifications