OBST問題, 在學習時, 看過兩種BST Cost算法 例如: 範例,給: i 0 1 2 3 4 5 pi / 0.08 0.15 0.05 0.1 0.12 qi 0.04 0.1 0.08 0.1 0.06 0.12 第一種:失敗節點視為下一層(簡稱下層): 範例產生的樹如下: p4 p2 p5 p1 p3 q4 q5 q0 q1 q2 q3 cost = 1(.1)+2(.15+.12)+3(.08+.05+.06+.12)+4(.04+.1+.08+.1) = 2.85 第二種:失敗節點視為同個節點(簡稱同層): 範例產生的樹如下(括號內表示同個點): (p2) (q0 p1 q1) (p4) (q2 p3 q3) (q4 p5 q5) cost = 1(.15)+2(.04+.08+.1+.1)+3(.08+.05+.1+.06+.12+.12) = 2.38 同層的DP關係式如下: * w(i,i)=qi, w(i,j)=w(i,j-1)+pj+qj * e(i,i)=0, eij=wij+min(r=i+1..j)e(i,r-1)+e(r,j) 下層的DP關係式如下: * w(j+1,j)=qj, w(i,j)=w(i,j-1)+pj+qj * e(j+1,j)=qj, e(i,j)=wij+min(r=i..j)e(i,r-1)+e(r+1,j) 兩種算出來答案是不同 看的的說法通常會說 沒特別提示 就視為同層 (https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1268193734.A.D0B.html 我的問題是 如何判斷是某些題目問的是下層 例如: 111成大 Given a sequence K=(k1,k2,k3,k4,k5) of five distinct keys in sorted order (so that k1<k2<k3<k4<k5) and six dummy keys d0,d1,d2,d3,d4,d5, representing values not in K, we have a probability pi for ki and a probability qi for di. Determine the cost of an optimal binary search tree for K with the following probabilities: i 0 1 2 3 4 5 pi / 0.08 0.15 0.05 0.1 0.12 qi 0.04 0.1 0.08 0.1 0.06 0.12 找到的解答: 下層 https://i.imgur.com/DhqdU0H.png https://i.imgur.com/ciVTura.png e15=w15+min(r=4)e13+e55 = 1+ 1.37+.48 = 2.85 106成大 Given a sequence K = (k1, k2, ..., k6) of 6 distinct keys in sorted order with probabilities 0.06, 0.08, 0.10, 0.04, 0.12, 0.14. Some searches may be for values not in K, and so we also have 7 dummy keys, d0, d1, . .., d6, with probabilities 0.07, 0.07, 0.07, 0.07, 0.06, 0.06, 0.06. 找到的解答: 下層 e16=w16+min(r=3)e12+e46= 1+ .76+1.23 = 2.99 95成大 Given a sequence K=<k1,k2...kn> of n distinct keys in sorted order such that k1<k2<...<kn, and we wish to build a binary search tree from these keys. For each key ki, we have a probability pi, that a search will be for ki. Some searches may be for values not in K, and so we also have n+1 "dummy keys" d0,d1,d2,..,dn, representing values not in K. In particular, d0 represents all values less than k1, dn represents all values greater than k, and for i=1,2,...,n-1, the dummy key di, represents al values between ki, and ki+1. For each dummy key di, we have a probability qi, that a search will correspond to di. Each key ki is an internal node, and each dummy key di is a leaf. Every search is either successful (finding some key ki) or unsuccessful (finding some dummy key di), and so we have Σ(上n下i=0)pi+Σ(上n下i=0)qi=1. The expected cost or a search tree T is E[search cost in T] = Σ(上n下i=1)(depthT(ki)+1)*pi+Σ(上n下i=0)(depthT(di)+1)*qi = 1+Σ(上n下i=1)depthT(ki)*pi+Σ(上n下i=0)depthT(di)*qi where depthT denotes a node's depth in the tree T. Given five keys with p1=0.15, p2=p4=q5=q1=0.10, p3=q0=q2=q3=q4=0.05, p5=0.20, compute the corresponding small lest search cost. 找到的解答: 下層 https://i.imgur.com/1c5gQDL.png e15=w15+min(r=2)e11+e35= 1 + .45+1.3 = 2.75 e15=w15+min(r=4)e13+e55= 1 + 1.25+.5 = 2.75 (兩種可能) 112成大 We are given a sequence K=<k1, k2,...,kn> of n distinct keys in sorted order (so that k1<k2<...<kn), and we wish to build a binary search tree from these keys. For each key ki, we have a probability pi that a search will be for ki. Some searches may be for values not in K, and so we also have n+1 "dummy keys" d0, d1,..., dn representing values not in K. In particular, d0 represents all values less than k1, dn represents all values greater than kn, and for i= 1,2,...,n-1, the dummy key di represents all values between ki and k(i+1). For each dummy key di, we have a probability qi that a search will correspond to di. Determine the cost and structure of an optimal binary search tree in the expected cost of search time for a set of n = 7 keys with the following probabilities: i 0 1 2 3 4 5 6 7 pi / .04 .06 .08 .02 .10 .12 .14 qi .06 .06 .06 .06 .05 .05 .05 .05 找到的解答: 同層 https://i.imgur.com/4x6hUVW.png 97清大 Let n= 5 and (a1, a2, a3, a4, a5) = (do, for, if, return, while) be an identifier set. Let (p1, p2, p3, p4, p5) = (1,1,3,3,2) and (q0, q1, q2, q3, q4, q5) = (2,3,1,2,1,1) be the probabilities for the successful and unsuccessful search of identifiers, respectively. Note that the p's and q's have been multiplied by 20 for convenience. What is the cost of the optimal binary search tree for (do, for, if, return, while)? 找到的解答: 同層 https://i.imgur.com/9Xx2H7H.png e05=w05+min(r=3)e02+e35 = 20 + 13+13 = 46 98交大 Suppose that we have n records, ai, i = 1,...,n, and these n records are stored in the nodes in a binary search tree. We call this kind of node the data node and each node (record) is associated with an access probability pi. If a search in the binary search tree reaches an external node between ai and a(i+1), we say that the search reaches a failure node. There are n+1 failure nodes. Each failure node is associated with a probability qi, i = 0,. ..,n. A node (data node or failure node) contributes cost p*h to the total search cost where p is the associated probability and h is the depth of the node. The binary search tree stores these n records is an optimal binary search tree if the total cost (Σ(i)pi*hi + Σ(j)qj*hj) is the least. Which of the following statements are true. (a) Suppose there are 4 records with key values (10,15,20,25), pi are (3/16, 3/16, 1/16, 1/16), and qi are (2/16, 3/16, 1/16, 1/16, 1/16), the optimal binary search tree is as shown in Figure 3-2. 15 10 20 25 (b) Suppose there are 4 records with key values (10, 15,20, 25), pi are (3/16, 3/16, 1/16, 1/16), and qi are (2/16, 3/16, 1/16, 1/16, 1/16), the optimal binary search tree is as shown in Figure 3-3. 20 15 25 10 找到的解答: 同層 https://i.imgur.com/swXpvmx.png 前三題跟後三題，差別在哪才會用到同層的算法? 第三題有(95成大)有寫"dummy key di is a leaf"可能比較好懂 以前的文有說題目會定義清楚 (https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1476847293.A.776.html 但前兩題看題意，我看不出來要用哪種，是不是我哪裡沒理解到? --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.229.66.15 (臺灣) ※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1726751753.A.C5B.html ※ 編輯: Jaka (36.229.66.15 臺灣), 09/19/2024 21:17:23