1
Dynam ic Programming
explained, we focus our research on forward type of algorithms
The subproblems in the DP structure are called states. All states together
form the so-called state space, this state space can be divided in stages containing
states which represent sub-problems of the same size.
Definition 1.1
A sub-problem, or state, is defined by
ξ
φ
. The subscript
φ
defines the specifics
of the sub-problem.
◻
Definition 1.2
Let
ς
denote a solution. With
ς
φ
we define a solution to the sub-problem, or
state, ξ
φ
. By
ˇ
ξ
φ
we denote an optimal solution to state ξ
φ
.
◻
Definition 1.3
By
ςi
we denote an expansion in the forward DP algorithm from solution
ς
with
i
. This is a new solution of a larger sub-problem. The definition of
i
depends on the specific problem.
◻
We can write the principle of optimality in terms of these state definitions.
Proposition 1.4
When the value of an optimal solution
ˇ
ξ
φ
for a state
ξ
φ
can be expressed
using only the value of optimal solutions of other states
ξ
0
φ
0
and the expansion
i
such that
ˇ
ξ
0
φ
0
i
results in a solution in
ξ
φ
, the principle of optimality
holds.
◻
Proof
This is essentially the principle of optimality where the definition of
the state ξ
φ
defines a sub-problem.
∎
Corollary 1.5
If the principle of optimality holds, the feasibility of the expansion
ς
φ
i
for
a solution
ς
φ
∈ξ
φ
only depends on
ξ
φ
and
i
, not on the specific solution
ς
φ
.
◻
In the rest of this section we illustrate, using three simple problems, the basics
of DP and some important properties.
1.1.1 Fibonacci numbers
One of the most well-known recurrence relations is the relation between the
Fibonacci numbers. The Fibonacci numbers are defined by
F
n
=F
n−1
+F
n−2
and
F
0
=
0
, F
1
=
1. These numbers are named after Leonardo Pisano, known as
Fibonacci, who described them in 1202 [97], see [109] for a recent translation.
The definition used here, starting with
F
0
, is from Lucas [80] who generalized this
sequence. The recurrence relation follows directly from the definition, problem
F
n
can be found directly from the solutions of subproblems
F
n−1
and
F
n−2
. The
relation between the different subproblems is described in figure 1.1, where the
green and blue lines represent F
n−1
and F
n−2
, respectively.
6
我的内容管理
展开
