dynamic-programming
Gewogen activiteitenselectie
Zoeken…
Gewogen taakplanningalgoritme
Gewogen taakplanningalgoritme kan ook worden aangeduid als gewogen activiteitselectie-algoritme.
Het probleem is, gezien bepaalde taken met hun starttijd en eindtijd, en een winst die u maakt wanneer u de taak voltooit, wat is de maximale winst die u kunt maken, gezien het feit dat er geen twee taken tegelijkertijd kunnen worden uitgevoerd?
Deze lijkt op Activiteitselectie met behulp van Greedy Algorithm, maar er is een extra wending. Dat wil zeggen, in plaats van het aantal voltooide taken te maximaliseren, richten we ons op maximale winst. Het aantal uitgevoerde taken maakt hier niet uit.
Laten we een voorbeeld bekijken:
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | A | B | C | D | E | F |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (2,5) | (6,7) | (7,9) | (1,3) | (5,8) | (4,6) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 6 | 4 | 2 | 5 | 11 | 5 |
+-------------------------+---------+---------+---------+---------+---------+---------+
De banen worden aangeduid met een naam, hun start- en eindtijd en winst. Na een paar iteraties kunnen we erachter komen of we Job-A en Job-E uitvoeren , we kunnen de maximale winst van 17 krijgen. Hoe kunnen we dit nu vinden met behulp van een algoritme?
Het eerste wat we doen is de taken sorteren op hun eindtijd in niet-afnemende volgorde. Waarom doen we dit? Dit komt omdat als we een taak selecteren die minder tijd kost om te voltooien, we de meeste tijd overlaten om andere taken te kiezen. Wij hebben:
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
We hebben een extra tijdelijke array Acc_Prof van maat n (hier geeft n het totale aantal taken aan). Dit bevat de maximale geaccumuleerde winst van het uitvoeren van de taken. Snap je het niet? Wacht en kijk. We initialiseren de waarden van de array met de winst van elke taak. Dat betekent dat Acc_Prof [i] in eerste instantie de winst zal behalen van het uitvoeren van i-de taak.
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Laten we nu positie 2 aangeven met i , en positie 1 wordt aangegeven met j . Onze strategie zal zijn om j van 1 naar i-1 te herhalen en na elke iteratie zullen we i met 1 verhogen, totdat i n + 1 wordt .
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
We controleren of Job [i] en Job [j] elkaar overlappen, dat wil zeggen dat als de eindtijd van Job [j] groter is dan de starttijd van Job [i] , deze twee jobs niet samen kunnen worden uitgevoerd. Als ze elkaar echter niet overlappen, controleren we of Acc_Prof [j] + Profit [i]> Acc_Prof [i] . Als dit het geval is, zullen we Acc_Prof [i] = Acc_Prof [j] + Profit [i] updaten. Dat is:
if Job[j].finish_time <= Job[i].start_time
if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
Acc_Prof[i] = Acc_Prof[j] + Profit[i]
endif
endif
Hier vertegenwoordigt Acc_Prof [j] + Profit [i] de geaccumuleerde winst van het uitvoeren van deze twee taken toegther. Laten we het voor ons voorbeeld bekijken:
Hier overlapt Job [j] met Job [i] . Dus deze kunnen niet samen worden gedaan. Omdat onze j gelijk is aan i-1 , verhogen we de waarde van i tot i + 1 dat 3 is . En we maken j = 1 .
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Nu overlappen Job [j] en Job [i] elkaar niet. De totale hoeveelheid winst die we kunnen maken door deze twee banen te kiezen, is: Acc_Prof [j] + Profit [i] = 5 + 5 = 10, wat groter is dan Acc_Prof [i] . Dus werken we Acc_Prof [i] = 10 bij . We verhogen ook j met 1. We krijgen,
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Hier overlapt Job [j] met Job [i] en is j ook gelijk aan i-1 . Dus we verhogen i met 1 en maken j = 1 . We krijgen,
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Nu overlappen Job [j] en Job [i] elkaar niet, we krijgen de gecumuleerde winst 5 + 4 = 9 , die groter is dan Acc_Prof [i] . We werken Acc_Prof [i] = 9 bij en verhogen j met 1.
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 9 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Opnieuw overlappen Job [j] en Job [i] elkaar niet. De gecumuleerde winst is: 6 + 4 = 10 , wat groter is dan Acc_Prof [i] . We werken Acc_Prof [i] = 10 opnieuw bij . We verhogen j met 1. We krijgen:
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 10 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Als we doorgaan met dit proces, nadat we de hele tabel met i hebben herhaald, ziet onze tabel er uiteindelijk uit als:
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 14 | 17 | 8 |
+-------------------------+---------+---------+---------+---------+---------+---------+
* Een paar stappen zijn overgeslagen om het document korter te maken.
Als we de reeks Acc_Prof doorlopen , kunnen we de maximale winst 17 vinden ! De pseudo-code:
Procedure WeightedJobScheduling(Job)
sort Job according to finish time in non-decreasing order
for i -> 2 to n
for j -> 1 to i-1
if Job[j].finish_time <= Job[i].start_time
if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
Acc_Prof[i] = Acc_Prof[j] + Profit[i]
endif
endif
endfor
endfor
maxProfit = 0
for i -> 1 to n
if maxProfit < Acc_Prof[i]
maxProfit = Acc_Prof[i]
return maxProfit
De complexiteit van het vullen van de Acc_Prof- array is O (n 2 ). De array-doorloop neemt O (n) . Dus de totale complexiteit van dit algoritme is O (n 2 ).
Als we nu willen weten welke taken zijn uitgevoerd om de maximale winst te krijgen, moeten we de array in omgekeerde volgorde doorlopen en als de Acc_Prof overeenkomt met de maxProfit , zullen we de naam van de taak in een stapel plaatsen en de winst van die baan van maxProfit . We zullen dit doen tot onze maxProfit> 0 of we bereiken het beginpunt van de Acc_Prof- array. De pseudo-code ziet eruit als:
Procedure FindingPerformedJobs(Job, Acc_Prof, maxProfit):
S = stack()
for i -> n down to 0 and maxProfit > 0
if maxProfit is equal to Acc_Prof[i]
S.push(Job[i].name
maxProfit = maxProfit - Job[i].profit
endif
endfor
De complexiteit van deze procedure is: O (n) .
Een ding om te onthouden, als er meerdere taakplanningen zijn die ons maximale winst kunnen opleveren, kunnen we slechts één taakplanning vinden via deze procedure.