Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 68
Текст из файла (страница 68)
The usual cut-and-paste argument applies. If therewere a subtree T" whose expected cost is lower than that of T′, then we could cut T′ out of Tand paste in T", resulting in a binary search tree of lower expected cost than T, thuscontradicting the optimality of T.We need to use the optimal substructure to show that we can construct an optimal solution tothe problem from optimal solutions to subproblems. Given keys ki, ..., kj, one of these keys,say kr (i ≤ r ≤ j), will be the root of an optimal subtree containing these keys.
The left subtreeof the root kr will contain the keys ki, ..., kr-1 (and dummy keys di-1, ..., dr-1), and the rightsubtree will contain the keys kr+1, ..., kj (and dummy keys dr, ..., dj). As long as we examine allcandidate roots kr, where i ≤ r ≤ j, and we determine all optimal binary search trees containingki, ..., kr-1 and those containing kr+1, ..., kj, we are guaranteed that we will find an optimalbinary search tree.There is one detail worth noting about "empty" subtrees. Suppose that in a subtree with keyski, ..., kj, we select ki as the root.
By the above argument, ki's left subtree contains the keys ki,..., ki-1. It is natural to interpret this sequence as containing no keys. Bear in mind, however,that subtrees also contain dummy keys. We adopt the convention that a subtree containingkeys ki, ..., ki-1 has no actual keys but does contain the single dummy key di-1. Symmetrically,if we select kj as the root, then kj's right subtree contains the keys kj +1, ..., kj; this right subtreecontains no actual keys, but it does contain the dummy key dj.Step 2: A recursive solutionWe are ready to define the value of an optimal solution recursively.
We pick our subproblemdomain as finding an optimal binary search tree containing the keys ki, ..., kj, where i ≥ 1, j ≤n, and j ≥ i - 1. (It is when j = i - 1 that there are no actual keys; we have just the dummy keydi-1.) Let us define e[i, j] as the expected cost of searching an optimal binary search treecontaining the keys ki, ..., kj. Ultimately, we wish to compute e[1, n].The easy case occurs when j = i - 1.
Then we have just the dummy key di-1. The expectedsearch cost is e[i, i - 1] = qi-1.When j ≥ i, we need to select a root kr from among ki, ..., kj and then make an optimal binarysearch tree with keys ki, ..., kr-1 its left subtree and an optimal binary search tree with keys kr+1,..., kj its right subtree. What happens to the expected search cost of a subtree when it becomesa subtree of a node? The depth of each node in the subtree increases by 1. By equation(15.16), the expected search cost of this subtree increases by the sum of all the probabilities inthe subtree. For a subtree with keys ki, ..., kj, let us denote this sum of probabilities as(15.17)Thus, if kr is the root of an optimal subtree containing keys ki, ..., kj, we havee[i, j ] = pr + (e[i, r - 1] + w(i, r - 1)) + (e[r + 1, j] + w(r + 1, j)).Noting thatw(i, j) = w(i, r - 1) + pr + w(r + 1, j),we rewrite e[i, j] as(15.18)The recursive equation (15.18) assumes that we know which node kr to use as the root. Wechoose the root that gives the lowest expected search cost, giving us our final recursiveformulation:(15.19)The e[i, j] values give the expected search costs in optimal binary search trees.
To help uskeep track of the structure of optimal binary search trees, we define root[i, j], for 1 ≤ i ≤ j ≤ n,to be the index r for which kr is the root of an optimal binary search tree containing keys ki, ...,kj. Although we will see how to compute the values of root[i, j], we leave the construction ofthe optimal binary search tree from these values as Exercise 15.5-1.Step 3: Computing the expected search cost of an optimal binary search treeAt this point, you may have noticed some similarities between our characterizations ofoptimal binary search trees and matrix-chain multiplication. For both problem domains, oursubproblems consist of contiguous index subranges. A direct, recursive implementation ofequation (15.19) would be as inefficient as a direct, recursive matrix-chain multiplicationalgorithm. Instead, we store the e[i, j] values in a table e[1 n + 1, 0 n]. The first indexneeds to run to n + 1 rather than n because in order to have a subtree containing only thedummy key dn, we will need to compute and store e[n + 1, n].
The second index needs to startfrom 0 because in order to have a subtree containing only the dummy key d0, we will need tocompute and store e[1, 0]. We will use only the entries e[i, j] for which j ≥ i - 1. We also use atable root[i, j], for recording the root of the subtree containing keys ki, ..., kj. This table usesonly the entries for which 1 ≤ i ≤ j ≤ n.We will need one other table for efficiency. Rather than compute the value of w(i, j) fromscratch every time we are computing e[i, j]—which would take Θ(j - i) additions—we storethese values in a table w[1 n + 1, 0 n]. For the base case, we compute w[i, i - 1] = qi-1 for1 ≤ i ≤ n.
For j ≥ i, we compute(15.20)Thus, we can compute the Θ(n2) values of w[i, j] in Θ(1) time each.The pseudocode that follows takes as inputs the probabilities p1, ..., pn and q0, ..., qn and thesize n, and it returns the tables e and root.OPTIMAL-BST(p, q, n)1 for i ← 1 to n + 12do e[i, i - 1] ← qi-13w[i, i - 1] ← qi-14 for l ← 1 to n5do for i ← 1 to n - l + 16do j ← i + l - 17e[i, j] ← ∞8w[i, j] ← w[i, j - 1] +9for r ← i to j10do t ← e[i, r - 1]11if t < e[i, j]12then e[i, j]13root[i,14 return e and rootpj + qj+ e[r + 1, j] + w[i, j]← tj] ← rFrom the description above and the similarity to the MATRIX-CHAIN-ORDER procedure inSection 15.2, the operation of this procedure should be fairly straightforward.
The for loop oflines 1–3 initializes the values of e[i, i - 1] and w[i, i - 1]. The for loop of lines 4–13 then usesthe recurrences (15.19) and (15.20) to compute e[i, j] and w[i, j] for all 1 ≤ i ≤ j ≤ n. In thefirst iteration, when l = 1, the loop computes e[i, i] and w[i, i] for i = 1, 2, ..., n. The seconditeration, with l = 2, computes e[i, i + 1] and w[i, i +1] for i = 1, 2, ..., n - 1, and so forth. Theinnermost for loop, in lines 9–13, tries each candidate index r to determine which key kr touse as the root of an optimal binary search tree containing keys ki, ..., kj. This for loop savesthe current value of the index r in root[i, j] whenever it finds a better key to use as the root.Figure 15.8 shows the tables e[i, j], w[i, j], and root[i, j] computed by the procedureOPTIMAL-BST on the key distribution shown in Figure 15.7.
As in the matrix-chainmultiplication example, the tables are rotated to make the diagonals run horizontally.OPTIMAL-BST computes the rows from bottom to top and from left to right within each row.Figure 15.8: The tables e[i, j], w[i, j], and root[i, j] computed by OPTIMAL-BST on the keydistribution shown in Figure 15.7. The tables are rotated so that the diagonals runhorizontally.The OPTIMAL-BST procedure takes Θ(n3) time, just like MATRIX-CHAIN-ORDER. It iseasy to see that the running time is O(n3), since its for loops are nested three deep and eachloop index takes on at most n values. The loop indices in OPTIMAL-BST do not have exactlythe same bounds as those in MATRIX-CHAIN-ORDER, but they are within at most 1 in alldirections.
Thus, like MATRIX-CHAIN-ORDER, the OPTIMAL-BST procedure takes Ω(n3)time.Exercises 15.5-1Write pseudocode for the procedure CONSTRUCT-OPTIMAL-BST(root) which, given thetable root, outputs the structure of an optimal binary search tree. For the example in Figure15.8, your procedure should print out the structure•••••••••k2 is the rootk1 is the left child of k2d0 is the left child of k1d1 is the right child of k1k5 is the right child of k2k4 is the left child of k5k3 is the left child of k4d2 is the left child of k3d3 is the right child of k3••d4 is the right child of k4d5 is the right child of k5corresponding to the optimal binary search tree shown in Figure 15.7(b).Exercises 15.5-2Determine the cost and structure of an optimal binary search tree for a set of n = 7 keys withthe following probabilities:i012345670.04 0.06 0.08 0.02 0.10 0.12 0.14qi 0.06 0.06 0.06 0.06 0.05 0.05 0.05 0.05piExercises 15.5-3Suppose that instead of maintaining the table w[i, j], we computed the value of w(i, j) directlyfrom equation (15.17) in line 8 of OPTIMAL-BST and used this computed value in line 10.How would this change affect the asymptotic running time of OPTIMAL-BST?Exercises 15.5-4: ⋆Knuth [184] has shown that there are always roots of optimal subtrees such that root[i, j - 1] ≤root[i, j] ≤ root[i + 1, j] for all 1 ≤ i < j ≤ n.
Use this fact to modify the OPTIMAL-BSTprocedure to run in Θ(n2) time.Problems 15-1: Bitonic euclidean traveling-salesman problemThe euclidean traveling-salesman problem is the problem of determining the shortest closedtour that connects a given set of n points in the plane. Figure 15.9(a) shows the solution to a 7point problem. The general problem is NP-complete, and its solution is therefore believed torequire more than polynomial time (see Chapter 34).Figure 15.9: Seven points in the plane, shown on a unit grid. (a) The shortest closed tour, withlength approximately 24.89. This tour is not bitonic. (b) The shortest bitonic tour for the sameset of points. Its length is approximately 25.58.J. L. Bentley has suggested that we simplify the problem by restricting our attention to bitonictours, that is, tours that start at the leftmost point, go strictly left to right to the rightmostpoint, and then go strictly right to left back to the starting point.
Figure 15.9(b) shows theshortest bitonic tour of the same 7 points. In this case, a polynomial-time algorithm ispossible.Describe an O(n2)-time algorithm for determining an optimal bitonic tour. You may assumethat no two points have the same x-coordinate. (Hint: Scan left to right, maintaining optimalpossibilities for the two parts of the tour.)Problems 15-2: Printing neatlyConsider the problem of neatly printing a paragraph on a printer. The input text is a sequenceof n words of lengths l1, l2, ..., ln, measured in characters. We want to print this paragraphneatly on a number of lines that hold a maximum of M characters each.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
