📛 👨🏿‍🚀 👨🏽‍🍳 The book “Perfect Algorithm. Greedy Algorithms and Dynamic Programming

Hello, habrozhiteli! In the new book, Tim Rafgarden talks about greedy algorithms (the planning problem, minimal spanning trees, clustering, Huffman codes) and dynamic programming (the backpack problem, sequence alignment, shortest paths, optimal search trees). This post presents an excerpt "Developing a greedy algorithm."

Greedy algorithms appear to be well suited to the task of scheduling work, minimizing the weighted sum of completion times. The output has an iterative structure, where the work is processed one at a time. Why not use a greedy algorithm that iteratively decides which job will be next?

The first step of our plan is to solve two special cases of the general problem. Our solutions to these cases will show how a greedy algorithm might look like in the general case. Then we narrow down the domain to one candidate algorithm and prove that it is this candidate that solves the problem correctly. The process by which we come to this algorithm is more important for remembering than the algorithm itself; this process is repeatable and you can use it in your own applications.

13.3.1. Two special cases

Let's assume that for the task of minimizing the weighted sum of completion dates, in fact, there is a correct greedy algorithm. What would it look like if we assume that all works have the same length (but possibly different weights) or, conversely, have the same weight (but possibly different lengths)?

13.2

(1) , ?
(2) , ?
) ;
) ;
) ;
) ;
( . 13.3.3.)

13.3.2.

In general, the work may have different weights and different lengths. Whenever our two rules of thumb — to prefer shorter work and work with higher weights — are fortunate for a couple of jobs to coincide, we know which one to plan first (shorter with higher weights). But what if these two rules give conflicting advice? What should we do with one short work with low weight and one long work with high weight?

What will be the simplest greedy algorithm that will work as it should? Each work has two parameters, and the algorithm should look at both. The best option would be to develop a formula that compiles the length and weight of each work into a single mark (contribution), so that planning work from the highest to the lowest mark is guaranteed to minimize the amount of weighted completion dates. If such a formula exists, then from our two particular cases it follows that it should have two properties: (i) leaving the length fixed, it should increase by the weight of the work; (ii) leaving the weight fixed, it should decrease from the length of the work (recall that the higher the mark, the better). Spend a minute brainstorming several formulas that have both of these properties.

Perhaps the simplest function, which increases in weight and decreases in length, is the difference between them:
proposal No. 1 for the mark of the work.

The indicated mark could be negative, but this does not pose any obstacles to the consistent construction of works from the highest to the lowest mark . However, there are many other options. For example, the ratio of two parameters is another candidate:

Proposal No. 2 for marking the work.

These two functions for calculating the mark lead to two different greedy algorithms.

GREEDY DIFFERENCE GREEDYDIFF

Plan work in descending order
(arbitrarily breaking the coincidence of values).

GREEDYRATIO

( ).

Thus, already our first case study illustrates the first topic of the greedy paradigm (section 13.1.2): to propose for the task several competing greedy algorithms is usually not difficult. But which of the two algorithms, if any, is correct? A quick way to exclude one of them is to find an instance in which two algorithms display different schedules with different values of the objective function. For any algorithm whose results are worse in this example, we can conclude that it is not always optimal. In two special cases with works of the same weight or the same length, both algorithms act correctly. The simplest possible example of the exclusion of one of them may be an instance of a task in which two works have different weights and lengths,as a result, both algorithms plan to work in opposite orders. That is, we are looking for two works whose order in difference is opposite to their order in relation. Example:

The first work has a larger large ratio

but a larger difference (–2 vs. –1). Thus, the algorithm GreedyDiffplans the second work first, while the algorithm GreedyRatioplans the opposite.

EXERCISE 13.3

What is the sum of the weighted completion dates in the schedules deduced by the GreedyDiffand algorithms, respectively GreedyRatio?

a) 22 and 23
b) 23 and 22
c) 17 and 17
d) 17 and 11
(For a solution and explanation, see section 13.3.3.)

We moved forward by excluding the algorithm GreedyDifffrom further consideration. However, the result of exercise 13.3 does not directly lead to the fact that the algorithm GreedyRatiowill always be optimal. As far as we know, there are other cases when this algorithm produces an non-optimal schedule. You should always be skeptical of an algorithm that is not accompanied by a proof of its correctness, even if this algorithm does the right thing in several test cases and is extremely skeptical of greedy algorithms.

In our case, the algorithm GreedyRatio, in fact, is guaranteed to minimize the amount of weighted completion dates.

Theorem 13.1 (the correctness of the algorithm GreedyRatio) . For each set of positive work weightsand positive job lengths, the algorithm GreedyRatiodisplays a schedule with the smallest possible sum of weighted completion dates.

This logical statement is not obvious, and you should not trust him without receiving evidence. In accordance with the third theme of the greedy paradigm (section 13.1.2), this proof takes up the entire next section.

, . .

. — , ( ). — , , , . «» ( ) , .

The remaining theme of the greedy paradigm is the simplicity of run-time analysis (section 13.1.2). Here, of course, it is. The GreedyRatio algorithm only sorts the jobs by relation, which takes O (n log n) time, where n is the number of jobs in the input (see footnote 1 on p. 24).

13.3.3. Exercise Solutions 13.2–13.3

The solution to exercise 13.2 The

correct answer is: (a) . First, suppose that all n jobs have the same length, say 1. Then each schedule has exactly the same set of deadlines - {1, 2, 3, ..., n} - and the only question is what kind of job gets completion date and what is the deadline. Our semantics for work weights certainly imply that work with greater weight should receive shorter completion times, and this is true. For example, you would not want to plan work with a weight of 10 third (with a deadline of 3) and work with a weight of 20 fifth (with a deadline of 5); you would be better off changing the positions of these two works, which would reduce the sum of the weighted completion deadlines by 20 (as you can see for yourself).

The second case, in which all works have the same weight, is slightly thinner. Here you want to give preference to shorter work. For example, consider two jobs of unit weight with lengths of 1 and 2. If you first plan a shorter work, then the completion deadlines will be 1 and 3 with a total of 4. In the reverse order, the deadlines will be 2 and 3 with the worst outcome 5. In general, the planned the work first contributes to the completion time of all work, since all work must wait for the completion of the first. All things being equal, planning the shortest work first minimizes this negative impact. The second job contributes to all completion dates except the first job, so the second shortest job should be scheduled for the next, etc.

Exercise 13.3 Solution

The correct answer is: (b). The algorithm GreedyDiffplans a second job first. The deadline for completing this work is

whereas the deadline for completing another work is

Sum of the weighted deadlines for completion then

The algorithm GreedyRatioplans the first work first, resulting in deadlines

and the sum of weighted deadlines equal to

Since the algorithm GreedyDifffails to calculate the optimal schedule for this example , it is not always correct.

»More information about the book can be found on the publisher’s website
» Contents
» Excerpt

For Khabrozhiteley 25% discount on the coupon - Algorithms

Upon payment of the paper version of the book, an electronic book is sent by e-mail.

The book “Perfect Algorithm. Greedy Algorithms and Dynamic Programming »

13.3.1. Two special cases

13.3.2.

13.3.3. Exercise Solutions 13.2–13.3

More articles: