DP のバックアップ差分(No.5)

バックアップ一覧
現在との差分を表示
ソースを表示
バックアップを表示
DP へ行く。
- 1 (2016-01-24 (日) 21:17:29)
- 2 (2016-01-24 (日) 22:12:06)
- 3 (2016-01-25 (月) 18:01:59)
- 4 (2016-01-25 (月) 18:19:48)
- 5 (2016-01-26 (火) 01:19:50)
- 6 (2016-01-26 (火) 12:31:39)
- 7 (2016-01-26 (火) 22:10:50)

追加された行はこの色です。
削除された行はこの色です。

[[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.
- Calculate the sum of, the arc value (this value) between this node and the previous node, and the value of the previous node which shows the minimal value from the start node to the previous node. 
- Copy this expression to the area of J13:M21. 
*** 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.
- Copy this expression to the area of N13:N21.
*** 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.
- Find out the previous arc which minimize the value. It is the selected arc. The arc is identified by the place between J*:M*. When the arc is in the column of J*, it is the 1st arc. When the arc is in the column M*, it is the 4th arc.
- Copy this expression to the area of O13:O21
*** 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.
- Find out the previous node (selected node) which minimize the total value from the start node to this node.
- Copy this expression to the area of P13:P21
*** 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.
- Copy this expression to the area of Q13:Q21
** 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