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/cn.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/cn.aspx?n=bbs/Grad-ProbAsk/M.1476847293.A.776.html 但前两题看题意，我看不出来要用哪种，是不是我哪里没理解到? --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 36.229.66.15 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1726751753.A.C5B.html ※ 编辑: Jaka (36.229.66.15 台湾), 09/19/2024 21:17:23