Source code online books for professionals by professionals



Download 4,67 Mb.
Pdf ko'rish
bet130/266
Sana31.12.2021
Hajmi4,67 Mb.
#213682
1   ...   126   127   128   129   130   131   132   133   ...   266
Bog'liq
2 5296731884800181221

Figure 7-4.  A set of random intervals where at most four mutually compatible intervals (for example, a, c, e and g) can 
be found
There are two obvious candidates for greedy selection here: If we go from left to right on the timeline, we might 
want to start with either the interval that starts first or the one that ends first, eliminating any other overlapping 
intervals. I hope it is clear that the first alternative can’t work (Exercise 7-18), which leaves us to show that the other 
one does work.
The algorithm is (roughly) as follows:
 
1.  Include the interval with the lowest finish time in the solution.
 
2.  Remove all of the remaining intervals that overlap with the one from step 1.
 
3.  Any remaining intervals? Go to step 1.
Running this algorithm on the interval set in Figure 
7-4
 results in the highlighted set of intervals (ace and g).  
The resulting solution is clearly valid; that is, there aren’t any overlapping intervals in it. This will be the case in 
general; we need show only that it’s optimal, that is, that we have as many intervals as possible. Let’s try to apply the 
idea of staying ahead.
Let’s say our intervals are, in the order in which they were added, i
1
 … i
k
, and that the hypothetical, optimal 
solution gives the intervals j
1
 … j
m
. We want to show that k = m. Assume that the optimal intervals are sorted by 
finishing (and starting) times.
15
 To show that our algorithm stays ahead of the optimal one, we need to show that for 
any r £ k, the finish time of i
r
 is at least as early as that of j
r
, and we can prove this by induction.
For r = 1, it is obviously correct: The greedy algorithm chooses i
1
, which is the element with the minimum finish 
time. Now, let r > 1 and assume that our hypothesis holds for r - 1. The question then becomes whether it is possible 
for the greedy algorithm to “fall behind” at this step. That is, is it possible that the finish time for i
r
 could now be 
greater than that of j
r
? The answer is clearly no, because the greedy algorithm could just as well have chosen j
r
 (which 
is compatible with j
r-1
, and therefore also with i
r-1
, which finishes at least as early).


Chapter 7 

 Greed Is Good? prove It! 
157
So, the greedy algorithm keeps up with the best, all the way to the end. However, this “keeping up” dealt only with 
finishing times, not the number of intervals. We need to show that keeping up will yield an optimal solution, and we 
can do so by contradiction: If the greedy algorithm is not optimal, then m > k. For every r, including r = k, we know 
that i
r
 finishes at least as early as j
r
. Because m > k, there must be an interval j
r+1
 that we didn’t use. This must start after 
j
r
, and therefore after i
r
, which means that we could have—and, indeed, would haveincluded it. In other words, we 
have a contradiction.
No Worse Than Perfect
This is a technique I used in showing the greedy choice property for Huffman’s algorithm. It involves showing that you 
can transform a hypothetical optimal solution to the greedy one, without reducing the quality. Kleinberg and Tardos 
call this an exchange argument. Let’s put a twist on the interval problem. Instead of having fixed starting and ending 
times, we now have a duration and a deadline, and you’re free to schedule the intervals—let’s call them tasks—as you 
want, as long as they don’t overlap. You also have a given starting time, of course.
However, any task that goes past its deadline incurs a penalty equal to its delay, and you want to minimize the 
maximum of these delays. On the surface, this might seem like a rather complex scheduling problem (and, indeed, 
many scheduling problems are really hard to solve). Surprisingly, though, you can find the optimum schedule through 
a super-simple greedy strategy: Always perform the most urgent task. As is often the case for greedy algorithms, the 
correctness proof is a bit tougher than the algorithm itself.
The greedy solution has no gaps in it. As soon as we’re done with one task, we start the next. There will also be 
at least one optimal solution without gaps—if we have an optimal solution with gaps, we can always close these up, 
resulting in earlier finish times for the later tasks. Also, the greedy solution will have no inversions (jobs scheduled 
before other jobs with earlier deadlines). We can show that all solutions without gaps or inversions have the same 
maximum delay. Two such solutions can differ only in the order of tasks with identical deadlines, and these must be 
scheduled consecutively. Among the tasks in such a consecutive block, the maximum delay depends only on the last 
task, and this delay doesn’t depend on the order of the tasks.
The only thing that remains to be proven is that there exists an optimal solution without gaps or inversions
because it would be equivalent to the greedy solution. This proof has three parts:
If the optimal solution has an inversion, there are two consecutive tasks where the first has a 

later deadline than the second.
Switching these two removes one inversion.

Removing this inversion will not increase the maximum delay.

The first point should be obvious enough. Between two inverted tasks, there must be some point where the 
deadlines start decreasing, giving us the two consecutive, inverted tasks. As for the second point, swapping the tasks 
clearly removes one inversion, and no new inversions are created. The third point requires a little care. Swapping tasks 

Download 4,67 Mb.

Do'stlaringiz bilan baham:
1   ...   126   127   128   129   130   131   132   133   ...   266




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish