ExcelEx
Dynamic Programming by Excel without using a VBA macro.†
- Finding out the minimal path from the start node to the goal node in a graph with labeled directed arcs.
- The sheet...
dp-1.xlsx
Input†
- Node numbers. The start node should be 1. Nodes numbers should be sorted.
- Previous node numbers for each node number. The muximum previous nodes number should be 4.
- Arc values from the previous nodes to each node. All values, include arc values and intermediate values, should be less than 1000.
Output†
- The minimal value from the start node to the goal node.
- The minimal path from the start node to the goal node.
Key excpressions†
J13†
=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†
=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†
=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†
=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†
=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†
- Wikipedia Dynamic programming
- Dynamic programming from an excel perspective.
Counter: 2626,
today: 1,
yesterday: 0
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
