DP の履歴(No.2) - PukiWiki

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

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

Dynamic Programming by Excel without using VBA macro.†

Finding out the minimal path from the graph
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.

Counter: 2626, today: 1, yesterday: 0