![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
[[ExcelEx]] * Dynamic Programming by Excel without using a VBA macro. [#k8ac001e] - Finding out the minimal path from the start node to the goal node in a graph with labeled directed arcs. - &ref(DP/dp-1-img.jpg,50%); &br; Fig. 1. - The sheet... &ref(DP/dp-1.xlsx); ** Input [#f6744253] - Node IDs. Each node ID is represented by a number. The start node ID should be 1. Node IDs should be sorted. -- Each line represent one node. - Previous nodes for each node. The maximum number of previous nodes should be 4. - Arc value from the previous node*. 1000 (represents infinite) is assigned when there is no corresponding arc. *** Format of the Input [#id6a75c1] - In a line which corresponding to a node, the column A represents the Node ID. - Column B to E represents previous nodes. - Column F to I represents arc values from the previous nodes to this node. *** Example (Fig. 1)[#k3d4854e] - The cell A13 represents a node ID. The ID is one. So this node is the start node. - The cell A19 represents the node, the ID of which is 7. Previous nodes of this node (7) are 4 and 5. They are shown by the cell B19 and C19. The arc value from the node 4 to this node(7) is 10, which is shown by the cell F19. The arc value from the node 5 to this node is 4, which is shown by the cell G19. ** Output [#g3e710b2] - The minimal value from the start node to the goal node. - The minimal path from the start node to the goal node. ** Key excpressions [#s5d8268b] *** J13 [#xe0335cd] =IF(B13<>0,VLOOKUP(B13,$A$13:$N$21,14)+F13,1000) - Calculate the arc value between this node and the previous node, plus the value (minimal value from the start node from the node) of the previous node. - Copy this expression to all of this column. *** N13 [#d744f0cc] =IF(A13=1,0,MIN(J13:M13)) - Find out the minimal value from the previous nodes to this node. - Copy this expression to all of this column. *** O13 [#hd19795a] =IF(N13=0,0,MATCH(N13,J13:M13)) - Find out the previous arc index which minimize the value. - Copy this expression to all of this column. *** P13 [#k0befaa9] =IF(O13=0,0,INDEX(B13:E13,1,O13)) - Find out the previous node which minimize the value. - Copy this expression to all of this column. *** Q13 [#d88ce4e1] =IF(P13=0,"",IF(P13=1,"1-"&TEXT(A13,"#####"),VLOOKUP(P13,$A$13:$Q$21,17)&"-"&TEXT(A13,"#####"))) - Construct the minimal path from the start node to this node. - Copy this expression to all of this column. ** References [#lfb15418] - Wikipedia Dynamic programming -- https://en.wikipedia.org/wiki/Dynamic_programming - Dynamic programming from an excel perspective. -- https://www.researchgate.net/publication/262281816_Dynamic_programming_from_an_excel_perspective ---- #counter
