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