Dynamic Programming Basic Concepts

Stage

The point at which a decision is made is known as a stage. The end of a stage marks the beginning of the immediate succeeding stage. For instance, in the salesmen allocation problem, each territory represents a stage; in the shortest route problem, each city represents a stage.

State

Conceptually, the variable that links two stages in a multistage decision problem is called a state variable. At any stage, the values that state variables can take describe the status of the problem. These values are referred to as states. For example, in the shortest route problem, a city is referred to as state variable.

Principle of Optimality

The principle of optimality states that the optimal decision from any state in a stage to the end, is independent of how one actually arrives at that state.

Optimal Policy

A policy which optimizes the value of an objective function is called an optimal policy.