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

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.

Login or register to post comments
2362 reads

Comments

What is a "smart exhaust"?

Mon, 15/06/2009 - 23:44 — Sharon (not verified)

What is a "smart exhaust"?