Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 60
Текст из файла (страница 60)
In the example of Figure 15.2(a), the fastest total time comes from choosing stations 1,3, and 6 from line 1 and stations 2, 4, and 5 from line 2.Figure 15.2: (a) An instance of the assembly-line problem with costs ei, ai,j, ti,j, and xiindicated. The heavily shaded path indicates the fastest way through the factory. (b) Thevalues of fi[j], f*, li[j], and l* for the instance in part (a).The obvious, "brute force" way of minimizing the time through the factory is infeasible whenthere are many stations. If we are given a list of which stations to use in line 1 and which touse in line 2, it is easy to compute in Θ(n) time how long it takes a chassis to pass through thefactory.
Unfortunately, there are 2n possible ways to choose stations, which we see by viewingthe set of stations used in line 1 as a subset of {1, 2, ..., n} and noting that there are 2n suchsubsets. Thus, determining the fastest way through the factory by enumerating all possibleways and computing how long each takes would require Ω(2n) time, which is infeasible whenn is large.Step 1: The structure of the fastest way through the factoryThe first step of the dynamic-programming paradigm is to characterize the structure of anoptimal solution. For the assembly-line scheduling problem, we can perform this step asfollows.
Let us consider the fastest possible way for a chassis to get from the starting pointthrough station S1,j. If j = 1, there is only one way that the chassis could have gone, and so it iseasy to determine how long it takes to get through station S1,j. For j = 2, 3, ..., n, however,there are two choices: the chassis could have come from station S1,j-1 and then directly tostation S1,j, the time for going from station j - 1 to station j on the same line being negligible.Alternatively, the chassis could have come from station S2,j-1 and then been transferred tostation S1,j, the transfer time being t2,j-1. We shall consider these two possibilities separately,though we will see that they have much in common.First, let us suppose that the fastest way through station S1,j is through station S1,j-1.
The keyobservation is that the chassis must have taken a fastest way from the starting point throughstation S1,j-1. Why? If there were a faster way to get through station S1,j-1, we could substitutethis faster way to yield a faster way through station S1,j: a contradiction.Similarly, let us now suppose that the fastest way through station S1,j is through station S2,j-1.Now we observe that the chassis must have taken a fastest way from the starting point throughstation S2,j-1. The reasoning is the same: if there were a faster way to get through station S2,j-1,we could substitute this faster way to yield a faster way through station S1,j, which would be acontradiction.Put more generally, we can say that for assembly-line scheduling, an optimal solution to aproblem (finding the fastest way through station Si,j) contains within it an optimal solution tosubproblems (finding the fastest way through either S1,j-1 or S2,j-1).
We refer to this property asoptimal substructure, and it is one of the hallmarks of the applicability of dynamicprogramming, as we shall see in Section 15.3.We use optimal substructure to show that we can construct an optimal solution to a problemfrom optimal solutions to subproblems. For assembly-line scheduling, we reason as follows.If we look at a fastest way through station S1,j, it must go through station j - 1 on either line 1or line 2. Thus, the fastest way through station S1,j is either••the fastest way through station S1,j-1 and then directly through station S1,j, orthe fastest way through station S2,j-1, a transfer from line 2 to line 1, and then throughstation S1,j.Using symmetric reasoning, the fastest way through station S2,j is either••the fastest way through station S2,j-1 and then directly through station S2,j, orthe fastest way through station S1,j-1, a transfer from line 1 to line 2, and then throughstation S2,j.To solve the problem of finding the fastest way through station j of either line, we solve thesubproblems of finding the fastest ways through station j - 1 on both lines.Thus, we can build an optimal solution to an instance of the assembly-line schedulingproblem by building on optimal solutions to subproblems.Step 2: A recursive solutionThe second step of the dynamic-programming paradigm is to define the value of an optimalsolution recursively in terms of the optimal solutions to subproblems.
For the assembly-linescheduling problem, we pick as our subproblems the problems of finding the fastest waythrough station j on both lines, for j = 1, 2, ..., n. Let fi[j] denote the fastest possible time to geta chassis from the starting point through station Si,j.Our ultimate goal is to determine the fastest time to get a chassis all the way through thefactory, which we denote by f*. The chassis has to get all the way through station n on eitherline 1 or line 2 and then to the factory exit. Since the faster of these ways is the fastest waythrough the entire factory, we have(15.1)It is also easy to reason about f1[1] and f2[1]. To get through station 1 on either line, a chassisjust goes directly to that station. Thus,(15.2)(15.3)Now let us consider how to compute fi[j] for j = 2, 3, ..., n (and i = 1, 2).
Focusing on f1[j], werecall that the fastest way through station S1,j is either the fastest way through station S1,j-1 andthen directly through station S1,j, or the fastest way through station S2,j-1, a transfer from line 2to line 1, and then through station S1,j. In the first case, we have f1[j] = f1[j - 1] + a1,j, and in thelatter case, f1[j] = f2[j - 1] + t2,j-1 + a1,j. Thus,(15.4)for j = 2, 3, ..., n. Symmetrically, we have(15.5)for j = 2, 3, ..., n.
Combining equations (15.2)–(15.5), we obtain the recursive equations(15.6)(15.7)Figure 15.2(b) shows the fi[j] values for the example of part (a), as computed by equations(15.6) and (15.7), along with the value of f*.The fi[j] values give the values of optimal solutions to subproblems. To help us keep track ofhow to construct an optimal solution, let us define li [j] to be the line number, 1 or 2, whosestation j - 1 is used in a fastest way through station Si,j . Here, i = 1, 2 and j = 2, 3, ..., n. (Weavoid defining li[1] because no station precedes station 1 on either line.) We also define l* tobe the line whose station n is used in a fastest way through the entire factory.
The li[j] valueshelp us trace a fastest way. Using the values of l* and li[j] shown in Figure 15.2(b), we wouldtrace a fastest way through the factory shown in part (a) as follows. Starting with l* = 1, weuse station S1,6. Now we look at l1[6], which is 2, and so we use station S2,5. Continuing, welook at l2[5] = 2 (use station S2,4), l2[4] = 1 (station S1,3), l1[3] = 2 (station S2,2), and l2[2] = 1(station S1,1).Step 3: Computing the fastest timesAt this point, it would be a simple matter to write a recursive algorithm based on equation(15.1) and the recurrences (15.6) and (15.7) to compute the fastest way through the factory.There is a problem with such a recursive algorithm: its running time is exponential in n.
Tosee why, let ri(j) be the number of references made to fi[j] in a recursive algorithm. Fromequation (15.1), we have(15.8)From the recurrences (15.6) and (15.7), we have(15.9)for j = 1, 2, ..., n - 1. As Exercise 15.1-2 asks you to show, ri(j) = 2n-j. Thus, f1[1] alone isreferenced 2n-1 times! As Exercise 15.1-3 asks you to show, the total number of references toall fi[j] values is Θ(2n).We can do much better if we compute the fi[j] values in a different order from the recursiveway. Observe that for j ≥ 2, each value of fi[j] depends only on the values of f1[j - 1] and f2[j 1].
By computing the fi[j] values in order of increasing station numbers j—left to right inFigure 15.2(b)—we can compute the fastest way through the factory, and the time it takes, inΘ(n) time. The FASTEST-WAY procedure takes as input the values ai,j, ti,j, ei, and xi , as wellas n, the number of stations in each assembly line.FASTEST-WAY(a, t, e, x, n)1 f1[1] ← e1 + a1,12 f2[1] ←e2 + a2,13 for j ← 2 to n4do if f1[j - 1] + a1,j ≤5then f1[j] ← f1[j6l1[j] ← 17else f1[j] ← f2[j8l1[j] ← 29if f2[j - 1] + a2,j ≤10then f2[j] ← f2[j11l2[j] ← 212else f2[j] ∞ f1[j13l2[j] ← 114 if f1[n] + x1 ≤ f2[n] + x215then f* = f1[n] + x116l* = 117else f* = f2[n] + x218l* = 2f2[j - 1] + t2,j-1 + a1,j- 1] + a1, j- 1] + t2,j-1 + a1,jf1[j - 1] + t1,j-1 + a2,j- 1] + a2,j- 1] + t1,j-1 + a2,jFASTEST-WAY works as follows.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
