In other problems splitting the steps introduced artificially. For example, a continuous control process can be viewed as a discrete, conditionally divided it into several time periods - the steps. Based on the terms of each specific problem, the step size is selected so that at each step to get a simple optimization problem, and provide the required accuracy.
The method of dynamic programming is that the optimal control is built step by step. At each step of optimizing control only of this step. However, at each step of the selected control in the aftermath, as management, optimizing the objective function for this step can lead to sub-optimal effect of the process. Control at each step must be optimal from the point of view of the whole process.
Illustration of the above is the problem of choosing the shortest way to go from point A to point B, and if the route is to go through some items. In Fig. These two points are marked by circles, and interconnecting roads - segments, near which carry a distance.

From the point of view of the interests of each optimization only next step, select the shortest path from a given point to the next - we should move on the route that passes through the points A, Aj, A3, A2, A4, B. The length of the route is 34. Such a path from A to B is not the shortest. For example, a route that passes through the points A, A3, A ^ B, has a shorter, equal to the present example the multi-step operation shows that the management at each step should be chosen with regard to its impact on the upcoming steps. This is the basic rule of the DP, formulated by R. Bellman, called the principle of optimality.
Copyright ©