※ 引述《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