DP

ExcelEx

Dynamic Programming by Excel without using a VBA macro. †

Takashi Yamanoue, Fukuyama University, 26 Jan. 2016. †

• Finding out the minimal path from the start node to the goal node in a graph with labeled directed arcs.
• 
  Fig. 1.
• The sheet... dp-1.xlsx

Input †

• Node IDs. Each node ID is represented by a number. The start node ID should be 1. Node IDs should be sorted.
  • Each line represents one node.
• Previous nodes for each node. The maximum number of previous nodes should be 4.
• Arc values from the previous nodes*. 1000 (represents infinite) is assigned when there is no corresponding arc.

Format of the Input †

• 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) †

• 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 †

• The minimal value from the start node to the goal node.
• The minimal path from the start node to the goal node.

Key expressions †

J13 †

=IF(B13<>0,VLOOKUP(B13,$A$13:$N$21,14)+F13,1000)

• 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 †

=IF(A13=1,0,MIN(J13:M13))

• Find out the minimal value from the previous nodes to this node.
• Copy this expression to the area of N13:N21.

O13 †

=IF(N13=0,0,MATCH(N13,J13:M13))

• 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 †

=IF(O13=0,0,INDEX(B13:E13,1,O13))

• Find out the previous node (selected node) which minimizes the total value from the start node to this node.
• Copy this expression to the area of P13:P21

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 the area of Q13:Q21

References †

• 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
• Writing a program by Excel
  • http://lecture.ecc.u-tokyo.ac.jp/~shagiya/excel.pdf
• Writing codes for a programming contest by excel
  • http://d.hatena.ne.jp/kita_yuta/20111220/1324405195