dynamic-programming
Selezione delle attività ponderate

Algoritmo di pianificazione del lavoro ponderato

Algoritmo di pianificazione dei lavori ponderati può anche essere indicato come algoritmo di selezione delle attività ponderate.

Il problema è che, dati determinati lavori con l'ora di inizio e l'ora di fine e un profitto che si ottiene quando si finisce il lavoro, qual è il profitto massimo che si può dare dato che non è possibile eseguire due lavori in parallelo?

Questo assomiglia ad Activity Selection usando Greedy Algorithm, ma c'è una svolta in più. Cioè, invece di massimizzare il numero di posti di lavoro finiti, ci concentriamo sulla realizzazione del massimo profitto. Il numero di lavori eseguiti non importa qui.

Diamo un'occhiata a un esempio:

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

I lavori sono indicati con un nome, il loro inizio e fine e il profitto. Dopo alcune iterazioni, possiamo scoprire se eseguiamo Job-A e Job-E , possiamo ottenere il massimo profitto di 17. Ora come scoprirlo usando un algoritmo?

La prima cosa che facciamo è ordinare i lavori per il loro tempo di completamento in ordine decrescente. Perché lo facciamo? È perché se selezioniamo un lavoro che richiede meno tempo per terminare, lasciamo il maggior tempo per scegliere altri lavori. Abbiamo:

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

Avremo un array temporaneo aggiuntivo Acc_Prof di dimensione n (Qui, n indica il numero totale di lavori). Ciò conterrà il profitto massimo accumulato nell'esecuzione dei lavori. Non capisco? Aspetta e guarda. Inizializzeremo i valori dell'array con il profitto di ogni lavoro. Ciò significa che Acc_Prof [i] in un primo momento deterrà il profitto derivante dall'eseguire l' i-esimo lavoro.

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

Ora denotiamo la posizione 2 con i , e la posizione 1 sarà denotata con j . La nostra strategia sarà quella di iterare j da 1 a i-1 e dopo ogni iterazione, noi incrementiamo i di 1, fino a quando i diventa 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    |
+-------------------------+---------+---------+---------+---------+---------+---------+

Controlliamo se Job [i] e Job [j] si sovrappongono, cioè se il tempo di fine di Job [j] è maggiore dell'ora di inizio di Job [i] , quindi questi due lavori non possono essere eseguiti insieme. Tuttavia, se non si sovrappongono, controlleremo se Acc_Prof [j] + Profitto [i]> Acc_Prof [i] . Se questo è il caso, aggiorneremo Acc_Prof [i] = Acc_Prof [j] + Profitto [i] . Questo è:

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

Qui Acc_Prof [j] + Profitto [i] rappresenta il profitto accumulato di questi due posti di lavoro. Controlliamolo per il nostro esempio:

Qui Job [j] si sovrappone a Job [i] . Quindi questi non possono essere fatti insieme. Poiché il nostro j è uguale a i-1 , incrementiamo il valore di i in i + 1 cioè 3 . E facciamo 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    |
+-------------------------+---------+---------+---------+---------+---------+---------+

Ora Job [j] e Job [i] non si sovrappongono. L'importo totale del profitto che possiamo ottenere selezionando questi due lavori è: Acc_Prof [j] + Profitto [i] = 5 + 5 = 10 che è maggiore di Acc_Prof [i] . Quindi aggiorniamo Acc_Prof [i] = 10 . Aumentiamo anche j di 1. Otteniamo,

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

Qui, Job [j] si sovrappone a Job [i] e j è anche uguale a i-1 . Quindi incrementiamo i di 1, e facciamo j = 1 . Noi abbiamo,

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

Ora, Job [j] e Job [i] non si sovrappongono, otteniamo il profitto accumulato 5 + 4 = 9 , che è maggiore di Acc_Prof [i] . Aggiorniamo Acc_Prof [i] = 9 e incrementiamo j di 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    |
+-------------------------+---------+---------+---------+---------+---------+---------+

Ancora Job [j] e Job [i] non si sovrappongono. Il profitto accumulato è: 6 + 4 = 10 , che è maggiore di Acc_Prof [i] . Aggiorniamo nuovamente Acc_Prof [i] = 10 . Aumentiamo j di 1. Otteniamo:

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

Se continuiamo questo processo, dopo aver ripetuto l'intera tabella usando i , la nostra tabella sarà finalmente la seguente:

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

_{* Sono stati saltati alcuni passaggi per abbreviare il documento.}

Se iteriamo attraverso l'array Acc_Prof , possiamo scoprire che il profitto massimo è 17 ! Lo pseudo-codice:

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

La complessità del popolamento dell'array Acc_Prof è O (n ² ). L'array traversal prende O (n) . Quindi la complessità totale di questo algoritmo è O (n ² ).

Ora, se vogliamo scoprire quali lavori sono stati eseguiti per ottenere il massimo profitto, dobbiamo attraversare la matrice in ordine inverso e se Acc_Prof corrisponde a maxProfit , invieremo il nome del lavoro in una pila e sottrai Profitto di quel lavoro da maxProfit . Lo faremo fino a maxProfit> 0 o raggiungiamo il punto iniziale dell'array Acc_Prof . Lo pseudo-codice sarà simile a:

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

La complessità di questa procedura è: O (n) .

Una cosa da ricordare, se ci sono più piani di lavoro che possono darci il massimo profitto, possiamo trovare solo un programma di lavoro tramite questa procedura.