Greedy est un paradigme algorithmique qui construit une solution pièce par pièce, en choisissant toujours la pièce suivante qui offre l'avantage le plus évident et le plus immédiat. Les algorithmes gourmands sont utilisés pour les problèmes d'optimisation. Un problème d'optimisation peut être résolu à l'aide de Greedy si le problème a la propriété suivante : à chaque étape, nous pouvons faire un choix qui nous semble le meilleur pour le moment, et nous obtenons la solution optimale du problème complet .
Si un algorithme Greedy peut résoudre un problème, il devient généralement la meilleure méthode pour résoudre ce problème car les algorithmes Greedy sont en général plus efficaces que d'autres techniques comme la programmation dynamique. Mais les algorithmes Greedy ne peuvent pas toujours être appliqués. Par exemple, le problème fracional Knapsak peut être résolu en utilisant Greedy, mais 0-1 sac à dos ne peut pas être résolu en utilisant Greedy.
Les algorithmes gloutons sont parfois aussi utilisés pour obtenir une approximation des problèmes d'optimisation Hard. Par exemple, probléme du voyageur de commerce est un problème NP-difficile. Un choix gourmand pour ce problème consiste à choisir la ville non visitée la plus proche de la ville actuelle à chaque étape. Ces solutions ne produisent pas toujours la meilleure solution optimale mais peuvent être utilisées pour obtenir une solution approximativement optimale.
Considérons le probléme de sélection d'activité comme notre premier exemple d'algorithmes gourmands. Voici l'énoncé du problème.
On vous donne n activités avec leurs heures de début et de fin. Sélectionnez le nombre maximum d'activités pouvant être effectuées par une seule personne, en supposant qu'une personne ne peut travailler que sur une seule activité à la fois.
Exemple 1 : Considérons les 3 activités suivantes triées par par heure de fin. début[] = {10, 12, 20} ; finition[] = {20, 25, 30} ; Une personne peut exercer au plus deux activités. La ensemble maximal d'activités pouvant être exécutées is {0, 2} [ Ce sont des index dans start[] et terminer[] ] Exemple 2 : Considérez les 6 activités suivantes triés par heure de fin. début[] = {1, 3, 0, 5, 8, 5} ; finition[] = {2, 4, 6, 7, 9, 9} ; Une personne peut effectuer au plus quatre activités. La ensemble maximal d'activités pouvant être exécutées is {0, 1, 3, 4} [ Ce sont des index dans start[] et terminer[] ].
Le choix gourmand est de toujours choisir l'activité suivante dont l'heure de fin est la plus petite parmi les activités restantes et dont l'heure de début est supérieure ou égale à l'heure de fin de l'activité précédemment sélectionnée. Nous pouvons trier les activités en fonction de leur heure de fin afin de toujours considérer l'activité suivante comme une activité à heure de fin minimale.
1) Triez les activités en fonction de leur heure de fin
2) Sélectionnez la première activité du tableau trié et imprimez-la.
3) Procédez comme suit pour les activités restantes dans le tableau trié.
…….a) Si l'heure de début de cette activité est supérieure ou égale à l'heure de fin de l'activité précédemment sélectionnée, sélectionnez cette activité et imprimez-la.
Dans l'implémentation C suivante, on suppose que les activités sont déjà triées en fonction de leur heure de fin.
void printMaxActivities(int s[], int f[], int n){ int i, j; printf ("Following activities are selected n"); // The first activity always gets selected i = 0; printf("%d ", i); // Consider rest of the activities for (j = 1; j < n; j++) { // If this activity has start time greater than or // equal to the finish time of previously selected // activity, then select it if (s[j] >= f[i]) { printf ("%d ", j); i = j; } }}// driver program to test above functionint main(){ int s[] = {1, 3, 0, 5, 8, 5}; int f[] = {2, 4, 6, 7, 9, 9}; int n = sizeof(s)/sizeof(s[0]); printMaxActivities(s, f, n); return 0;}Comment fonctionne Greedy Choice pour les Activités triées par heure de fin ?
Supposons que l'ensemble d'activités donné soit S = {1, 2, 3, …n} et les activités sont triées par heure de fin. Le choix cupide est de toujours choisir l'activité 1. Comment se fait-il que l'activité 1 fournisse toujours l'une des solutions optimales. Nous pouvons le prouver en montrant que s'il existe une autre solution B avec la première activité autre que 1, alors il existe également une solution A de même taille avec l'activité 1 comme première activité. Soit k la première activité sélectionnée par B, alors il existe toujours A = {B – {k}} U {1}.
(Notez que les activités de B sont indépendantes et que k a le plus petit temps de finition parmi tous. Puisque k n'est pas 1, finition(k) >= finition(1)).
Comment mettre en œuvre lorsque des activités données ne sont pas triées ?
Nous créons une structure/classe pour les activités. Nous trions toutes les activités par heure de fin (voir tri en C++ STL ). Une fois que nous avons trié les activités, nous appliquons le même algorithme.
L'image ci-dessous est une illustration de l'approche ci-dessus :
Voici la mise en œuvre de l'approche ci-dessus :
struct Activitiy{ int start, finish;};// A utility function that is used for sorting// activities according to finish timebool activityCompare(Activitiy s1, Activitiy s2){ return (s1.finish < s2.finish);}// Returns count of the maximum set of activities that can// be done by a single person, one at a time.void printMaxActivities(Activitiy arr[], int n){ // Sort jobs according to finish time sort(arr, arr+n, activityCompare); cout << "Following activities are selected n"; // The first activity always gets selected int i = 0; cout << "(" << arr[i].start << ", " << arr[i].finish << "), "; // Consider rest of the activities for (int j = 1; j < n; j++) { // If this activity has start time greater than or // equal to the finish time of previously selected // activity, then select it if (arr[j].start >= arr[i].finish) { cout << "(" << arr[j].start << ", " << arr[j].finish << "), "; i = j; } }}// Driver programint main(){ Activitiy arr[] = {{5, 9}, {1, 2}, {3, 4}, {0, 6}, {5, 7}, {8, 9}}; int n = sizeof(arr)/sizeof(arr[0]); printMaxActivities(arr, n); return 0;}