The Analysis of Forward and Backward Dynamic Programming for Multistage Graph

4th International Conference on Operational Research

Sitinjak, Anna Angela^1 ; Pasaribu, Elvina^1 ; Simarmata, Justin E.^1 ; Putra, Tedy^1 ; Mawengkang, Herman^1

Department of Mathematics, University of Sumatera Utara, Indonesia^1

关键词: Complex problems;    Decision rules;    Final decision;    Forward and backward method;    Forward-and-backward;    Minimum cost;    Optimal solutions;    Optimization approach;   

Others  :  https://iopscience.iop.org/article/10.1088/1757-899X/300/1/012010/pdf
DOI  :  10.1088/1757-899X/300/1/012010

来源: IOP

【 摘 要 】

Dynamic programming is an optimization approach that divides the complex problems into the simple sequences of problems in which they are interrelated leading to decisions. In the dynamic programming, there is no standard formula that can be used to make a certain formulation. In this paper we use forward and backward method to find path which have the minimum cost and to know whether they make the same final decision. Convert the problem into several successive sequential stages starting on from stages 1,2,3 and 4 for forward dynamic programming and the step back from stage 4.3,2,1 for backward dynamic programming and interconnected with a decision rule in each stage. Find the optimal solution with cost principle at next stage. Based on the characteristics of the dynamic programming, the case is divided into several stages and the decision is has to be made (xk) at each stage. The results obtained at a stage are used for the states in the next stage so that at the forward stage 1, f1(s) is obtained and used as a consideration of the decision in the next stage. In the backward, used firstly stage 4, f4(s) is obtained and used as a consideration of the decision in the next stage. Cost forward and backward always increase steadily, because the cost in the next stage depends on the cost in the previous stage and formed the decision of each stage by taking the smallest fkvalue. Therefore the forward and backward approaches have the same result.