dynamic-programming
Wybór ważonej aktywności
Szukaj…
Algorytm planowania ważonego zadania
Algorytm planowania zadań ważonych można również określić jako algorytm wyboru działań ważonych.
Problem polega na tym, że biorąc pod uwagę niektóre zadania z czasem rozpoczęcia i zakończenia oraz zyskiem, jaki osiągniesz po zakończeniu zadania, jaki jest maksymalny zysk, jaki możesz osiągnąć, biorąc pod uwagę, że nie można równolegle wykonać dwóch zadań?
Ten wygląda jak Selekcja aktywności za pomocą Chciwego Algorytmu, ale jest dodatkowy zwrot. Oznacza to, że zamiast maksymalizować liczbę zakończonych zleceń, koncentrujemy się na osiągnięciu maksymalnego zysku. Liczba wykonanych zadań nie ma tutaj znaczenia.
Spójrzmy na przykład:
+-------------------------+---------+---------+---------+---------+---------+---------+
| 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Zadania są oznaczone nazwą, czasem rozpoczęcia i zakończenia oraz zyskiem. Po kilku iteracjach możemy dowiedzieć się, czy wykonamy Job-A i Job-E , możemy uzyskać maksymalny zysk wynoszący 17. Teraz, jak to sprawdzić za pomocą algorytmu?
Pierwszą rzeczą, którą robimy, jest sortowanie zadań według czasu ich zakończenia w kolejności nie malejącej. Dlaczego to robimy? Dzieje się tak, ponieważ jeśli wybieramy zadanie, którego ukończenie zajmuje mniej czasu, pozostawiamy najwięcej czasu na wybranie innych zadań. Mamy:
+-------------------------+---------+---------+---------+---------+---------+---------+
| 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Będziemy mieć dodatkową tymczasową tablicę Acc_Prof o rozmiarze n (tutaj n oznacza całkowitą liczbę zadań). Będzie to zawierało maksymalny skumulowany zysk z wykonania zadań. Nie rozumiesz? Poczekaj i patrz. Zainicjujemy wartości tablicy z zyskiem każdego zadania. Oznacza to, że Acc_Prof [i] na początku zatrzyma zysk z wykonania i-tego zadania.
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Teraz oznaczmy pozycję 2 za pomocą i , a pozycję 1 oznaczymy za pomocą j . Naszą strategią będzie iteracja j od 1 do i-1, a po każdej iteracji będziemy zwiększać i o 1, aż i stanie się n + 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Sprawdzamy, czy Job [i] i Job [j] nakładają się, to znaczy, jeśli czas zakończenia Job [j] jest dłuższy niż czas rozpoczęcia Job [i] , to tych dwóch zadań nie można wykonać razem. Jeśli jednak się nie pokrywają, sprawdzimy, czy Acc_Prof [j] + Profit [i]> Acc_Prof [i] . W takim przypadku zaktualizujemy Acc_Prof [i] = Acc_Prof [j] + Profit [i] . To jest:
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
Tutaj Acc_Prof [j] + Zysk [i] reprezentuje skumulowany zysk z wykonania tych dwóch zadań razem. Sprawdźmy to w naszym przykładzie:
Tutaj Job [j] pokrywa się z Job [i] . Więc nie można tego zrobić razem. Ponieważ nasze j jest równe i-1 , zwiększamy wartość i do i + 1 , czyli 3 . I tworzymy 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Teraz Job [j] i Job [i] nie pokrywają się. Łączna kwota zysku, jaki możemy osiągnąć, wybierając te dwa zadania, to: Acc_Prof [j] + zysk [i] = 5 + 5 = 10, co jest większe niż Acc_Prof [i] . Dlatego aktualizujemy Acc_Prof [i] = 10 . Zwiększamy również j o 1. Otrzymujemy,
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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Tutaj Job [j] pokrywa się z Job [i], a j jest również równe i-1 . Zatem zwiększamy i o 1 i tworzymy j = 1 . Dostajemy
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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Teraz Job [j] i Job [i] nie pokrywają się, otrzymujemy skumulowany zysk 5 + 4 = 9 , który jest większy niż Acc_Prof [i] . Aktualizujemy Acc_Prof [i] = 9 i zwiększamy wartość j o 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Znów Job [j] i Job [i] nie pokrywają się. Skumulowany zysk wynosi: 6 + 4 = 10 , czyli więcej niż Acc_Prof [i] . Ponownie aktualizujemy Acc_Prof [i] = 10 . Zwiększamy j o 1. Otrzymujemy:
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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Jeśli będziemy kontynuować ten proces, po iteracji po całej tabeli za pomocą i , nasza tabela będzie w końcu wyglądać następująco:
+-------------------------+---------+---------+---------+---------+---------+---------+
| 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
* Kilka kroków zostało pominiętych, aby skrócić dokument.
Jeśli przejdziemy przez tablicę Acc_Prof , możemy ustalić maksymalny zysk wynoszący 17 ! Pseudo-kod:
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
Złożoność zapełniania tablicy Acc_Prof wynosi O (n 2 ). Przejście przez tablicę przyjmuje O (n) . Zatem całkowita złożoność tego algorytmu wynosi O (n 2 ).
Teraz, jeśli chcemy dowiedzieć się, które zadania zostały wykonane, aby uzyskać maksymalny zysk, musimy przejść przez tablicę w odwrotnej kolejności, a jeśli Acc_Prof pasuje do maxProfit , wypchniemy nazwę zadania do stosu i odejmujemy Zysk to zadanie od maxProfit . Będziemy to robić, dopóki nasz maxProfit> 0 lub dotrzemy do punktu początkowego tablicy Acc_Prof . Pseudo-kod będzie wyglądał następująco:
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
Złożoność tej procedury wynosi: O (n) .
Należy pamiętać, że jeśli istnieje wiele harmonogramów prac, które mogą zapewnić nam maksymalny zysk, za pomocą tej procedury możemy znaleźć tylko jeden harmonogram prac.