DP の履歴(No.4)

[ トップ ]   [ 新規 | 一覧 | 検索 | 最終更新 | ヘルプ ]

• 履歴一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• 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.†

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

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

---

     

Site admin: anonymous

PukiWiki 1.5.4 © 2001-2022 PukiWiki Development Team. Powered by PHP 7.4.3-4ubuntu2.23. HTML convert time: 0.008 sec.