推 assassin88:min{C11+C24,C12+C34,C13+C44}取最小之k值，得2。 01/09 23:37
推 imnewlegend:其實不用畫表格這麼辛苦 考試哪有這麼多時間@@ 01/20 04:28
→ imnewlegend:畫表格是幫助知道原理 不是有簡易版作法嗎 01/20 04:29
→ imnewlegend:考前要省點時間 考試才不會慌^^ 01/20 04:30
※ 引述《ssccg (23)》之銘言：
: ※ 引述《bernachom (Terry)》之銘言：
: : 假設
: : {a1,a2,a3,a4}={do,if,rea,while}
: : {p1,p2,p3,p4}={3,3,1,1}
: : {q0,q1,q2,q3,q4}={2,3,1,1,1}
: : 請教一下，該怎麼畫表格呢?
: : 我是先把p和q以三個三個圈起來
: : 表格我看課本是
: : \外部
: : 內部\---------------------
: : |
: : |
: : |
: : 長這個樣子...
: : 是不是識別字是0的，成本和root都是0?
: : 那....成本和加權值要怎麼算呢?
: : 我算加權值是，把圈起來的數都加起來就是了....
: : 成本是不是還要加上左、右最小的數值??
: : 然後....怎麼樣才知道是最佳化呢?
: : 這邊我看了好久...
: : 謝謝指導了
: 遞迴定義(i,j配合下面的表)：
: ╭ qj ,if i >j
: Wi,j = ┤
: ╰ Wi,j-1 + pj + qj ,if i≦j
: ╭ qj ,if i >j
: Ci,j = ┤
: ╰ min { Ci,k-1 + wi,j + Ck+1,j } ,if i≦j
: i≦k≦j
: Ri,j = 上面Ci,j選擇的k，而i>j時無root(空樹)
: algorithm跟DS聖經本的定義有差在failure search cost
: 前者是乘external path length，後者是external path length -1
: 以上面的遞迴定義來說就差在DS版的 Ci,j = 0 ,if i>j
: W的部分可以用圈的算，不過實際用程式實作的時候
: W也會是用填表建出來的，所以這邊一起列出
: : {p1,p2,p3,p4}={3,3,1,1}
: : {q0,q1,q2,q3,q4}={2,3,1,1,1}
: 以下用algorithm書上的填法說明，因為我覺得這個跟程式寫法比較接近
: 直的是i = 1~n+1，橫的是j = 0~n，(i,j)代表內部節點i~j形成的Tree
: 而對角線表示空樹，這邊分三個表，要合一起也可以
: 第一步填入對角線，C 填 qj (i>j的case)，DS版就填0，其他部份兩種版本作法都相同
: C 0 1 2 3 4 W 0 1 2 3 4 R 0 1 2 3 4
: ╭─┬─┬─┬─┬─╮ ╭─┬─┬─┬─┬─╮ ╭─┬─┬─┬─┬─╮
: 1 │ 2│ │ │ │ │ 1 │ 2│ │ │ │ │ 1 │空│ │ │ │ │
: ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
: 2 │ │ 3│ │ │ │ 2 │ │ 3│ │ │ │ 2 │ │空│ │ │ │
: ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
: 3 │ │ │ 1│ │ │ 3 │ │ │ 1│ │ │ 3 │ │ │空│ │ │
: ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
: 4 │ │ │ │ 1│ │ 4 │ │ │ │ 1│ │ 4 │ │ │ │空│ │
: ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
: 5 │ │ │ │ │ 1│ 5 │ │ │ │ │ 1│ 5 │ │ │ │ │空│
: ╰─┴─┴─┴─┴─╯ ╰─┴─┴─┴─┴─╯ ╰─┴─┴─┴─┴─╯
: 第二步填下一條斜線，照上面遞迴的定義，先算W，之後算C
: 例：W1,1 = W1,0 + p1 + q1 = 2+3+3 = 8
: C1,1 = min {C1,k-1 + W1,1 + Ck+1,1} (因為這邊k只有1一個選擇)
: 1≦k≦1
: = C1,0 + W1,1 + C2,1 = 2+8+3 = 13
: R1,1 = k = 1
: C 0 1 2 3 4 W 0 1 2 3 4 R 0 1 2 3 4
: ╭─┬─┬─┬─┬─╮ ╭─┬─┬─┬─┬─╮ ╭─┬─┬─┬─┬─╮
: 1 │ 2│13│ │ │ │ 1 │ 2│ 8│ │ │ │ 1 │空│ 1│ │ │ │
: ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
: 2 │ │ 3│11│ │ │ 2 │ │ 3│ 7│ │ │ 2 │ │空│ 2│ │ │
: ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
: 3 │ │ │ 1│ 5│ │ 3 │ │ │ 1│ 3│ │ 3 │ │ │空│ 3│ │
: ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
: 4 │ │ │ │ 1│ 5│ 4 │ │ │ │ 1│ 3│ 4 │ │ │ │空│ 4│
: ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
: 5 │ │ │ │ │ 1│ 5 │ │ │ │ │ 1│ 5 │ │ │ │ │空│
: ╰─┴─┴─┴─┴─╯ ╰─┴─┴─┴─┴─╯ ╰─┴─┴─┴─┴─╯
: 第三步同理，這邊以C1,2舉例
: k=1 k=2
: C1,2 = min {C1,0 + W1,2 + C2,2 , C1,1 + W1,2 + C3,2 }
: 1≦k≦2
: = min{ 2+12+11 , 13+12+1 } = min{25,26} = 25 (取k=1)
: 簡單的看法是要求那格的最左邊算來第1個配下面第1個、第2個配下面第2個...
: C 0 1 2 3 4 W 0 1 2 3 4 R 0 1 2 3 4
: ╭─┬─┬─┬─┬─╮ ╭─┬─┬─┬─┬─╮ ╭─┬─┬─┬─┬──╮
: 1 │ 2│13│25│ │ │ 1 │ 2│ 8│12│ │ │ 1 │空│ 1│ 1│ │ │
: ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼──┤
: 2 │ │ 3│11│17│ │ 2 │ │ 3│ 7│ 9│ │ 2 │ │空│ 2│ 2│ │
: ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼──┤
: 3 │ │ │ 1│ 5│11│ 3 │ │ │ 1│ 3│ 5│ 3 │ │ │空│ 3│3or4│
: ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼──┤
: 4 │ │ │ │ 1│ 5│ 4 │ │ │ │ 1│ 3│ 4 │ │ │ │空│ 4│
: ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼──┤
: 5 │ │ │ │ │ 1│ 5 │ │ │ │ │ 1│ 5 │ │ │ │ │ 空│
: ╰─┴─┴─┴─┴─╯ ╰─┴─┴─┴─┴─╯ ╰─┴─┴─┴─┴──╯
: 以下就不說明了
: C 0 1 2 3 4 W 0 1 2 3 4 R 0 1 2 3 4
: ╭─┬─┬─┬─┬─╮ ╭─┬─┬─┬─┬─╮ ╭─┬─┬─┬─┬──╮
: 1 │ 2│13│25│32│ │ 1 │ 2│ 8│12│14│ │ 1 │空│ 1│ 1│ 2│ │
: ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼──┤
: 2 │ │ 3│11│17│25│ 2 │ │ 3│ 7│ 9│11│ 2 │ │空│ 2│ 2│ 2 │
: ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼──┤
: 3 │ │ │ 1│ 5│11│ 3 │ │ │ 1│ 3│ 5│ 3 │ │ │空│ 3│3or4│
: ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼──┤
: 4 │ │ │ │ 1│ 5│ 4 │ │ │ │ 1│ 3│ 4 │ │ │ │空│ 4 │
: ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼──┤
: 5 │ │ │ │ │ 1│ 5 │ │ │ │ │ 1│ 5 │ │ │ │ │ 空 │
: ╰─┴─┴─┴─┴─╯ ╰─┴─┴─┴─┴─╯ ╰─┴─┴─┴─┴──╯
: C 0 1 2 3 4 W 0 1 2 3 4 R 0 1 2 3 4
: ╭─┬─┬─┬─┬─╮ ╭─┬─┬─┬─┬─╮ ╭─┬─┬─┬─┬──╮
: 1 │ 2│13│25│32│40│ 1 │ 2│ 8│12│14│16│ 1 │空│ 1│ 1│ 2│ 2 │
: ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼──┤
: 2 │ │ 3│11│17│25│ 2 │ │ 3│ 7│ 9│11│ 2 │ │空│ 2│ 2│ 2 │
: ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼──┤
: 3 │ │ │ 1│ 5│11│ 3 │ │ │ 1│ 3│ 5│ 3 │ │ │空│ 3│3or4│
: ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼──┤
: 4 │ │ │ │ 1│ 5│ 4 │ │ │ │ 1│ 3│ 4 │ │ │ │空│ 4 │
: ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼──┤
: 5 │ │ │ │ │ 1│ 5 │ │ │ │ │ 1│ 5 │ │ │ │ │ 空 │
: ╰─┴─┴─┴─┴─╯ ╰─┴─┴─┴─┴─╯ ╰─┴─┴─┴─┴──╯
: 答案的最小search cost總和即為C1,4
: 可以用 R 建出OBST
: : {a1,a2,a3,a4}={do,if,rea,while}
: 首先T1,4的root = R1,4 = 2 → a2
: ／ ＼
: T1,1 T3,4
: 然後T1,1的root = R1,1 = 1
: T3,4的root = R3,4 = 3或4 → a2 a2
: ／ ＼ ／ ＼
: a1 a3 or a1 a4
: \ /
: a4 a3
=========================================================================
前面是高手回過的
我想請問R的計算部分
為什麼R1,4 = 2 而不是 3 呢?(題目只有說a1<a2<a3<a4)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.46.193.13