dynamic-programming
Sélection d'activité pondérée
Recherche…
Algorithme de planification des travaux pondérés
L'algorithme de planification des travaux pondérés peut également être appelé algorithme de sélection d'activité pondérée.
Le problème est que, compte tenu de certains emplois avec leur heure de début et de fin, et un bénéfice que vous faites lorsque vous avez terminé le travail, quel est le profit maximum que vous pouvez faire étant donné qu'aucun travail ne peut être exécuté en parallèle?
Celui-ci ressemble à la sélection d'activité à l'aide de l'algorithme gourmand, mais il y a une torsion supplémentaire. Autrement dit, au lieu de maximiser le nombre d’emplois terminés, nous mettons l’accent sur le profit maximum. Le nombre d'emplois effectués n'a pas d'importance ici.
Regardons un exemple:
+-------------------------+---------+---------+---------+---------+---------+---------+
| 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Les emplois sont désignés par un nom, leur heure de début et de fin et leur profit. Après quelques itérations, nous pouvons savoir si nous réalisons Job-A et Job-E , nous pouvons obtenir un profit maximum de 17. Maintenant, comment le découvrir en utilisant un algorithme?
La première chose à faire est de trier les travaux en fonction de leur temps d’arrivée dans un ordre non décroissant. Pourquoi faisons-nous cela? C'est parce que si nous choisissons un travail qui prend moins de temps pour finir, nous laissons le plus de temps possible pour choisir d'autres emplois. Nous avons:
+-------------------------+---------+---------+---------+---------+---------+---------+
| 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Nous aurons un tableau temporaire supplémentaire Acc_Prof de taille n (Ici, n désigne le nombre total de travaux). Cela contiendra le profit maximum accumulé de l'exécution des travaux. Ne comprends pas? Attendez et regardez. Nous allons initialiser les valeurs du tableau avec le profit de chaque travail. Cela signifie que , Acc_Prof [i] sera tout d' abord maintenir le bénéfice d'effectuer travail i-ème.
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Notons maintenant la position 2 avec i et la position 1 avec j . Notre stratégie sera d'itérer j de 1 à i-1 et après chaque itération, nous incrémenterons i de 1 jusqu'à ce que i devienne 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Nous vérifions si les tâches [i] et la tâche [j] se chevauchent, c’est-à-dire que si l’ heure de fin de la tâche [j] est supérieure à celle de la tâche [i] , ces deux tâches ne peuvent pas être effectuées ensemble. Cependant, s'ils ne se chevauchent pas, nous vérifierons si Acc_Prof [j] + Profit [i]> Acc_Prof [i] . Si tel est le cas, nous mettrons à jour Acc_Prof [i] = Acc_Prof [j] + Profit [i] . C'est:
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
Ici, Acc_Prof [j] + Profit [i] représente le bénéfice cumulé de la réalisation de ces deux tâches. Vérifions-le pour notre exemple:
Ici Job [j] chevauche Job [i] . Donc, ils ne peuvent pas être faits ensemble. Puisque notre j est égal à i-1 , nous incrémentons la valeur de i à i + 1 soit 3 . Et on fait 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Maintenant, Job [j] et Job [i] ne se chevauchent pas. Le montant total des bénéfices que nous pouvons réaliser en choisissant ces deux emplois est le suivant: Acc_Prof [j] + Profit [i] = 5 + 5 = 10 qui est supérieur à Acc_Prof [i] . Nous mettons donc à jour Acc_Prof [i] = 10 . Nous incrémentons aussi j de 1. Nous obtenons,
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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Ici, Job [j] chevauche Job [i] et j est également égal à i-1 . Nous incrémentons donc i de 1 et faisons j = 1 . On a,
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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Maintenant, Job [j] et Job [i] ne se chevauchent pas, nous obtenons le bénéfice cumulé 5 + 4 = 9 , qui est supérieur à Acc_Prof [i] . Nous mettons à jour Acc_Prof [i] = 9 et incrémentons j de 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Encore une fois, Job [j] et Job [i] ne se chevauchent pas. Le bénéfice accumulé est de: 6 + 4 = 10 , ce qui est supérieur à Acc_Prof [i] . Nous mettons à jour à nouveau Acc_Prof [i] = 10 . Nous incrémentons j de 1. Nous obtenons:
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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Si nous continuons ce processus, après avoir parcouru toute la table en utilisant i , notre table ressemblera à ceci:
+-------------------------+---------+---------+---------+---------+---------+---------+
| 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
* Quelques étapes ont été sautées pour raccourcir le document.
Si nous parcourons le tableau Acc_Prof , nous pouvons trouver le profit maximum à 17 ! Le 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
La complexité de remplissage du tableau Acc_Prof est O (n 2 ). La traversée du tableau prend O (n) . La complexité totale de cet algorithme est donc O (n 2 ).
Maintenant, si nous voulons savoir quels travaux ont été effectués pour obtenir le maximum de profit, nous devons parcourir le tableau dans l’ordre inverse et si Acc_Prof correspond au maxProfit , nous allons pousser le nom du travail dans une pile et soustraire Profit de ce travail de maxProfit . Nous le ferons jusqu'à notre maxProfit> 0 ou nous atteignons le point de départ du tableau Acc_Prof . Le pseudo-code ressemblera à:
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 complexité de cette procédure est la suivante: O (n) .
Une chose à retenir: si plusieurs horaires de travail peuvent nous permettre de réaliser des bénéfices maximum, nous ne pouvons trouver qu'un seul emploi par cette procédure.