dynamic-programming
Gewichtete Aktivitätsauswahl

Gewichteter Job Scheduling-Algorithmus

Der gewichtete Job Scheduling-Algorithmus kann auch als gewichteter Aktivitätsauswahlalgorithmus bezeichnet werden.

Das Problem ist, wenn bestimmte Jobs mit ihrer Start- und Endzeit und einem Gewinn, den Sie nach Beendigung des Jobs erzielen, erzielt werden. Was ist der maximale Gewinn, den Sie erzielen können, wenn keine zwei Jobs gleichzeitig ausgeführt werden können?

Dieses sieht aus wie die Aktivitätsauswahl mit Greedy-Algorithmus, aber es gibt eine zusätzliche Wendung. Das heißt, anstatt die Anzahl der erledigten Jobs zu maximieren, konzentrieren wir uns auf den maximalen Gewinn. Die Anzahl der ausgeführten Jobs spielt hier keine Rolle.

Schauen wir uns ein Beispiel an:

+-------------------------+---------+---------+---------+---------+---------+---------+
|          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    |
+-------------------------+---------+---------+---------+---------+---------+---------+

Die Jobs werden mit einem Namen, ihrer Start- und Endzeit und ihrem Gewinn gekennzeichnet. Nach einigen Iterationen können wir herausfinden, ob wir Job-A und Job-E ausführen, und wir können den maximalen Gewinn von 17 erzielen. Nun, wie kann man das mit einem Algorithmus herausfinden?

Als erstes sortieren wir die Jobs nach ihrer Endzeit in nicht abnehmender Reihenfolge. Warum machen wir das? Wenn wir einen Job auswählen, dessen Ausführung weniger Zeit in Anspruch nimmt, haben wir die meiste Zeit für die Auswahl anderer Jobs. Wir haben:

+-------------------------+---------+---------+---------+---------+---------+---------+
|          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    |
+-------------------------+---------+---------+---------+---------+---------+---------+

Wir haben ein zusätzliches temporäres Array Acc_Prof der Größe n (Hier bezeichnet n die Gesamtzahl der Jobs). Dieser enthält den maximalen kumulierten Gewinn der Ausführung der Jobs. Verstehe es nicht Warten Sie und schauen Sie zu. Wir initialisieren die Werte des Arrays mit dem Gewinn der einzelnen Jobs. Das bedeutet, dass Acc_Prof [i] zunächst den Gewinn der Ausführung eines i-ten Jobs hält.

+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

Bezeichnen wir nun Position 2 mit i und Position 1 wird mit j bezeichnet . Unsere Strategie besteht darin, j von 1 nach i-1 zu iterieren und nach jeder Iteration i um 1 zu erhöhen, bis i zu n + 1 wird .

                               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    |
+-------------------------+---------+---------+---------+---------+---------+---------+

Wir prüfen , ob Job [i] und Job [j] überlappen, das heißt, wenn die Zeit von Job [j] größer als Job [i] ‚s Startzeit, dann diesen beiden Arbeitsplätze nicht zusammen getan werden kann. Wenn sie sich jedoch nicht überschneiden, prüfen wir, ob Acc_Prof [j] + Profit [i]> Acc_Prof [i] ist . Wenn dies der Fall ist, werden wir Acc_Prof [i] = Acc_Prof [j] + Profit [i] aktualisieren. Das ist:

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 steht Acc_Prof [j] + Profit [i] für den kumulierten Gewinn, wenn diese beiden Jobs zusammen ausgeführt werden. Schauen wir uns unser Beispiel an:

Hier überschneidet sich Job [j] mit Job [i] . Diese können also nicht zusammen gemacht werden. Da unser j gleich i-1 ist , erhöhen wir den Wert von i auf i + 1 , dh 3 . Und wir machen 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    |
+-------------------------+---------+---------+---------+---------+---------+---------+

Nun überschneiden sich Job [j] und Job [i] nicht. Der Gesamtgewinn, den wir durch die Auswahl dieser beiden Jobs erzielen können, ist: Acc_Prof [j] + Profit [i] = 5 + 5 = 10, was größer als Acc_Prof [i] ist . Also aktualisieren wir Acc_Prof [i] = 10 . Wir erhöhen auch j um 1. Wir bekommen,

                                         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 überschneidet sich Job [j] mit Job [i] und j ist auch gleich i-1 . Also erhöhen wir i um 1 und machen j = 1 . Wir bekommen,

                               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    |
+-------------------------+---------+---------+---------+---------+---------+---------+

Nun überschneiden sich Job [j] und Job [i] nicht, wir erhalten den kumulierten Gewinn 5 + 4 = 9 , der größer als Acc_Prof [i] ist . Wir aktualisieren Acc_Prof [i] = 9 und erhöhen j um 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    |
+-------------------------+---------+---------+---------+---------+---------+---------+

Wieder überlappen sich Job [j] und Job [i] nicht. Der kumulierte Gewinn beträgt: 6 + 4 = 10 , was größer als Acc_Prof [i] ist . Wir aktualisieren erneut Acc_Prof [i] = 10 . Wir erhöhen j um 1. Wir erhalten:

                                                   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    |
+-------------------------+---------+---------+---------+---------+---------+---------+

Wenn wir diesen Prozess fortsetzen, nachdem wir die gesamte Tabelle mit i durchlaufen haben, sieht unsere Tabelle schließlich folgendermaßen aus:

+-------------------------+---------+---------+---------+---------+---------+---------+
|          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    |
+-------------------------+---------+---------+---------+---------+---------+---------+

_{* Einige Schritte wurden übersprungen, um das Dokument zu verkürzen.}

Wenn wir das Array Acc_Prof durchlaufen , können wir herausfinden, dass der maximale Gewinn 17 beträgt! Der 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

Die Belegung des Acc_Prof- Arrays ist komplex ( O ² ). Die Array-Durchquerung nimmt O (n) an . Die Gesamtkomplexität dieses Algorithmus beträgt also O (n ² ).

Wenn wir nun herausfinden möchten, welche Jobs ausgeführt wurden, um den maximalen Profit zu erzielen, müssen wir das Array in umgekehrter Reihenfolge durchlaufen. Wenn Acc_Prof mit dem maxProfit übereinstimmt , verschieben wir den Namen des Jobs in einen Stack und ziehen Profit ab dieser Job von maxProfit . Wir werden dies tun, bis maxProfit> 0 ist oder wir den Anfangspunkt des Acc_Prof- Arrays erreichen. Der Pseudo-Code sieht folgendermaßen aus:

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

Die Komplexität dieses Verfahrens ist: O (n) .

Eine Sache, die wir berücksichtigen sollten: Wenn es mehrere Jobzeitpläne gibt, mit denen wir maximalen Profit erzielen können, können wir mit diesem Verfahren nur einen Jobzeitplan finden.