Cours 7 et 8: Algorithmes Gloutons
Ana Bu?sic´
I Technique pour résoudre des problèmes d’optimisation I Solution optimale obtenue en effectuant une suite de choix :
I Pas de retour en arrière : à chaque étape de décision dans l’algorithme, le choix qui semble le meilleur à ce moment est effectué.
I Progression descendante : choix puis résolution d’un problème plus petit
I Propriété du choix glouton : Il existe toujours une solution optimale commen¸cant par un choix glouton.
I Propriété de sous-structure optimale : trouver une solution optimale contenant le premier choix glouton se réduit à trouver une solution optimale pour un sous-problème de même nature.
Introduction
Principe général
Exemple : Location d’un camion
Arbre Couvrant Minimum
Codage de Huffman
Matro¨?des
Définitions et propriétés
Algorithme GLOUTON
Exemple : Ordonnancements
I Un unique véhicule à louer et maximiser le nombre de clients satisfaits (autres fonctions possibles à optimiser)
IE ensemble de demandes; chaque demande ei est caractérisée par une date de début di et une date de fin fi.
I Les demandes ei et ej sont compatibles ssi
]di,fi[ ? ]dj,fj[= ?.
I On cherche un sous-ensemble maximal de E de demandes 2 à 2 compatibles.
Exemple
|
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
di |
1 |
2 |
4 |
1 |
5 |
8 |
9 |
13 |
11 |
|
fi |
8 |
5 |
7 |
3 |
9 |
11 |
10 |
16 |
14 |
Algorithme glouton : trier selon critère et satisfaire les demandes par ordre croissant.
Exemple
|
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
di |
1 |
2 |
4 |
1 |
5 |
8 |
9 |
13 |
11 |
|
fi |
8 |
5 |
7 |
3 |
9 |
11 |
10 |
16 |
14 |
Algorithme glouton : trier selon critère et satisfaire les demandes par ordre croissant.
Quel critère?
I durée?
I date de début?
I date de fin?
Exemple
|
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
di |
1 |
2 |
4 |
1 |
5 |
8 |
9 |
13 |
11 |
|
fi |
8 |
5 |
7 |
3 |
9 |
11 |
10 |
16 |
14 |
Algorithme glouton : trier selon critère et satisfaire les demandes par ordre croissant.
Quel critère?
I durée? NON I date de début? NON
I date de fin? OUI
Demandes :
|
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
di |
1 |
2 |
4 |
1 |
5 |
8 |
9 |
13 |
11 |
|
fi |
8 |
5 |
7 |
3 |
9 |
11 |
10 |
16 |
14 |
Demandes :
|
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
di |
1 |
2 |
4 |
1 |
5 |
8 |
9 |
13 |
11 |
|
fi |
8 |
5 |
7 |
3 |
9 |
11 |
10 |
16 |
14 |
Etape 1 : tri selon la date de fin
|
i |
4 |
2 |
3 |
1 |
5 |
7 |
6 |
9 |
8 |
|
di |
1 |
2 |
4 |
1 |
5 |
9 |
8 |
11 |
13 |
|
fi |
3 |
5 |
7 |
8 |
9 |
10 |
11 |
14 |
16 |
Demandes :
|
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
di |
1 |
2 |
4 |
1 |
5 |
8 |
9 |
13 |
11 |
|
fi |
8 |
5 |
7 |
3 |
9 |
11 |
10 |
16 |
14 |
Etape 1 : tri selon la date de fin
|
i |
4 |
2 |
3 |
1 |
5 |
7 |
6 |
9 |
8 |
|
di |
1 |
2 |
4 |
1 |
5 |
9 |
8 |
11 |
13 |
|
fi |
3 |
5 |
7 |
8 |
9 |
10 |
11 |
14 |
16 |
Etape 2 : satisfaire les demandes par ordre croissant
|
i |
4 |
2 |
3 |
1 |
5 |
7 |
6 |
9 |
8 |
|
di |
1 |
2 |
4 |
1 |
5 |
9 |
8 |
11 |
13 |
|
fi |
3 |
5 |
7 |
8 |
9 |
10 |
11 |
14 |
16 |
Solution : demandes 4,3,7,9.
E trié selon dates de fin : f1 ? f2 ? ... ? fn
E,d,f variables globales (Convention : f0 := 0.)
5
E trié selon dates de fin : f1 ? f2 ? ... ? fn E,d,f variables globales
5
E trié selon dates de fin : f1 ? f2 ? ... ? fn E,d,f variables globales
5
Appel R(0)
Complexité O(n log n) (tri des n dates de fin)
Théorème : Le résultat de l’algorithme est optimal.
1. Il existe une solution optimale qui commence par e1 : soit A une sol. opt., et soit ea1 le premier client; si ea1 6= e1, alors A ? ea1 + e1 est aussi une sol. opt.
Théorème : Le résultat de l’algorithme est optimal.
1. Il existe une solution optimale qui commence par e1 : soit A une sol. opt., et soit ea1 le premier client; si ea1 6= e1, alors A ? ea1 + e1 est aussi une sol. opt.
2. Le problème se ramène à trouver une solution optimale d’éléments de E compatibles avec e1. Donc si A est une solution optimale pour
E, alors A0 = A ? e1 est une solution optimale pour
E0 = {ei;di ? f1}. En effet si l’on pouvait trouver B0 une solution optimale pour E0 contenant plus de clients que A0, alors ajouter e1 à B0 offrirait une solution optimale pour E contenant plus de clients que A, ce qui contredirait l’hypothèse que A est optimale.
G = (S,A,w), graphe connexe non orienté
(n sommets et m arêtes) w : A ? R (valuation sur les arêtes)
Def. Un arbre couvrant minimum (ACM) est un sous-graphe connexe sans cycle T = (S,B) (B ? A) qui minimise
w(T) = Xw(u,v).
(u,v)?B
Calcul d’un ACM par stratégie gloutonne : la suite des minimums locaux
(ajout d’une arête minimale à chaque étape) produit un minimum global
3
(ajout d’une arête minimale à chaque étape) produit un minimum global
3
Calcul d’un ACM par stratégie gloutonne : la suite des minimums locaux
(ajout d’une arête minimale à chaque étape) produit un minimum global
3
Calcul d’un ACM par stratégie gloutonne : la suite des minimums locaux
(ajout d’une arête minimale à chaque étape) produit un minimum global
3
Calcul d’un ACM par stratégie gloutonne : la suite des minimums locaux
(ajout d’une arête minimale à chaque étape) produit un minimum global
3
Calcul d’un ACM par stratégie gloutonne : la suite des minimums locaux
(ajout d’une arête minimale à chaque étape) produit un minimum global
3
Calcul d’un ACM par stratégie gloutonne : la suite des minimums locaux
(ajout d’une arête minimale à chaque étape) produit un minimum global
3
Déf. une coupe de G = (S,A) est une partition (R,S ? R) de S. Une arête (u,v) traverse la coupe si l’une de ses extrémités est dans R et l’autre dans S ? R. Une coupe respecte un ensemble d’arêtes B si aucune arête de B ne traverse la coupe.
Proposition. Soit G = (S,A,w), et soit B un sous-ensemble de A inclus dans un ACM(G); soit (R,S ? R) une coupe de G qui respecte B et soit (u,v) une arête minimale traversant (R,S ? R). Alors B ? (u,v) est inclus dans un ACM(G).
Déf. une coupe de G = (S,A) est une partition (R,S ? R) de S. Une arête (u,v) traverse la coupe si l’une de ses extrémités est dans R et l’autre dans S ? R. Une coupe respecte un ensemble d’arêtes B si aucune arête de B ne traverse la coupe.
Proposition. Soit G = (S,A,w), et soit B un sous-ensemble de A inclus dans un ACM(G); soit (R,S ? R) une coupe de G qui respecte B et soit (u,v) une arête minimale traversant (R,S ? R). Alors B ? (u,v) est inclus dans un ACM(G).
Algorithme de Kruskal : B est un ensemble de sous-arbre de ACM(G); la coupe s’appuie sur les sommets de l’un de ces sous-arbres.
1
Algorithme de Prim : B est sous-arbre racine de ACM(G); la coupe s’appuie sur les sommets de B.
Algorithme de Kruskal : B est un ensemble de sous-arbre de ACM(G); la coupe s’appuie sur les sommets de l’un de ces sous-arbres.
Algorithme de Prim : B est sous-arbre racine de ACM(G); la coupe s’appuie sur les sommets de B.
Algorithme de Kruskal : B est un ensemble de sous-arbre de ACM(G); la coupe s’appuie sur les sommets de l’un de ces sous-arbres.
Algorithme de Prim : B est sous-arbre racine de ACM(G); la coupe s’appuie sur les sommets de B.
Algorithme de Kruskal : B est un ensemble de sous-arbre de ACM(G); la coupe s’appuie sur les sommets de l’un de ces sous-arbres.
Algorithme de Prim : B est sous-arbre racine de ACM(G); la coupe s’appuie sur les sommets de B.
Algorithme de Kruskal : B est un ensemble de sous-arbre de ACM(G); la coupe s’appuie sur les sommets de l’un de ces sous-arbres.
Algorithme de Prim : B est sous-arbre racine de ACM(G); la coupe s’appuie sur les sommets de B.
Algorithme de Kruskal : B est un ensemble de sous-arbre de ACM(G); la coupe s’appuie sur les sommets de l’un de ces sous-arbres.
Algorithme de Prim : B est sous-arbre racine de ACM(G); la coupe s’appuie sur les sommets de B.
Algorithme de Kruskal : B est un ensemble de sous-arbre de ACM(G); la coupe s’appuie sur les sommets de l’un de ces sous-arbres.
Algorithme de Prim : B est sous-arbre racine de ACM(G); la coupe s’appuie sur les sommets de B.
Algorithme de Kruskal : B est un ensemble de sous-arbre de ACM(G); la coupe s’appuie sur les sommets de l’un de ces sous-arbres.
Algorithme de Prim : B est sous-arbre racine de ACM(G); la coupe s’appuie sur les sommets de B.
Algorithme de Prim : B est sous-arbre racine de ACM(G); la coupe s’appuie sur les sommets de B.
Algorithme de Kruskal : B est un ensemble de sous-arbre de ACM(G); la coupe s’appuie sur les sommets de l’un de ces sous-arbres.
Algorithme de Prim : B est sous-arbre racine de ACM(G); la coupe s’appuie sur les sommets de B.
Algorithme de Kruskal : B est un ensemble de sous-arbre de ACM(G); la coupe s’appuie sur les sommets de l’un de ces sous-arbres.
Algorithme de Prim : B est sous-arbre racine de ACM(G); la coupe s’appuie sur les sommets de B.
Algorithme de Kruskal : B est un ensemble de sous-arbre de ACM(G); la coupe s’appuie sur les sommets de l’un de ces sous-arbres.
Algorithme de Prim : B est sous-arbre racine de ACM(G); la coupe s’appuie sur les sommets de B.
Algorithme de Kruskal : B est un ensemble de sous-arbre de ACM(G); la coupe s’appuie sur les sommets de l’un de ces sous-arbres.
Algorithme de Prim : B est sous-arbre racine de ACM(G); la coupe s’appuie sur les sommets de B.
Algorithme de Kruskal : B est un ensemble de sous-arbre de ACM(G); la coupe s’appuie sur les sommets de l’un de ces sous-arbres.
Algorithme de Prim : B est sous-arbre racine de ACM(G); la coupe s’appuie sur les sommets de B.
Problème : Compresser un fichier texte T (archivage, transfert).
Idée : 2 lectures du texte T
1. 1ère passe : calculer la fréquence de chaque caractère dans T
2. 2ème passe : encoder chaque caractère en binaire; les carctères les plus fréquents ont les codes les plus courts.
Fichier de 100000 caractères (6 caractères distincts)
|
Caractère |
a |
b |
c |
d |
e |
f |
|
Fréquence |
45% |
13% |
12% |
16% |
9% |
5% |
|
Code fixe |
000 |
001 |
010 |
011 |
100 |
101 |
|
Code variable |
0 |
101 |
100 |
111 |
1101 |
1100 |
Taille du fichier compressé :
2. Code variable : 1 * 45000 + 3 * 13000 + 3 * 12000 +3 * 16000 + 4 * 9000 + 4 * 5000 = 224000 bits
Fichier de 100000 caractères (6 caractères distincts)
|
Caractère |
a |
b |
c |
d |
e |
f |
|
Fréquence |
45% |
13% |
12% |
16% |
9% |
5% |
|
Code fixe |
000 |
001 |
010 |
011 |
100 |
101 |
|
Code variable |
0 |
101 |
100 |
111 |
1101 |
1100 |
Taille du fichier compressé :
1. Code fixe (sur 3 bits) : 3 * 100000 = 300000 bits
2. Code variable : 1 * 45000 + 3 * 13000 + 3 * 12000 +3 * 16000 +
4 * 9000 + 4 * 5000 = 224000 bits
Code préfixe : l’encodage d’un caractère n’est le préfixe d’aucun autre
? simple concaténation à l’encodage et pas d’ambigu¨?té au décodage.
Fichier de 100000 caractères (6 caractères distincts)
|
Caractère |
a |
b |
c |
d |
e |
f |
|
Fréquence |
45% |
13% |
12% |
16% |
9% |
5% |
|
Code fixe |
000 |
001 |
010 |
011 |
100 |
101 |
|
Code variable |
0 |
101 |
100 |
111 |
1101 |
1100 |
Taille du fichier compressé :
1. Code fixe (sur 3 bits) : 3 * 100000 = 300000 bits
2. Code variable : 1 * 45000 + 3 * 13000 + 3 * 12000 +3 * 16000 +
4 * 9000 + 4 * 5000 = 224000 bits
Code préfixe : l’encodage d’un caractère n’est le préfixe d’aucun autre
? simple concaténation à l’encodage et pas d’ambigu¨?té au décodage.
Ex. 001011101.
Code fixe : 001 011 101 ? bdf .
Code variable : 0 0 101 1101 ? aabe.
Un code préfixe peut toujours être représenté à l’aide d’un arbre binaire (arbre digital).
Si l’arbre n’est pas complet alors le code n’est pas optimal.
|
Caractère |
a |
b |
c |
d |
e |
f |
|
Fréquence |
45% |
13% |
12% |
16% |
9% |
5% |
|
Code fixe |
000 |
001 |
011 |
100 |
101 |
|
Caractère |
a |
b |
c |
d |
e |
f |
|
Fréquence |
45% |
13% |
12% |
16% |
9% |
5% |
|
Code variable |
0 |
101 |
100 |
111 |
1101 |
1100 |
Texte T sur l’alphabet A
If (c) dénote la fréquence du caractère c ? A dans T
Iprof (c) dénote la profondeur du caractère c dans l’arbre digital
(= taille du codage de c)
Le nombre de bits requis pour encoder le texte T
(i.e. la taille du fichier compressé) est
B(T) = Xf (c)prof (c).
c?A
Entrées : Fréquences (f1,...,fn) des lettres (ai) d’un texte T.
Sortie : Arbre digital donnant un code préfixe minimal pour T.
1. Créer, pour chaque lettre ai, un arbre (réduit à une feuille) qui porte comme poids la fréquence f (i).
2. Itérer le processus suivant :
I choisir 2 arbres G et D de poids minimum
I créer un nouvel arbre R, ayant pour sous-arbre gauche (resp. droit) G (resp. D) et lui affecter comme poids la somme des poids de G et D.
3. Arrêter lorsqu’il ne reste plus qu’un seul arbre :
c’est l’arbre de Huffman
|
f:5 |
e:9 |
c:12 |
b:13 |
d:16 |
a:45 |
|
|
|
|
|
|
1. La construction initiale et le tri : O(n log n)
2. A chaque itération :
I extraire 2 fois l’arbre de poids min et fabriquer un nouvel arbre à partir des 2 précédents : O(1)
I rajouter ce nouvel arbre à la liste triée : O(log n)
3. Il y a n ? 1 itérations.
La construction de l’arbre de Huffman est donc en O(n log n) comparaisons.
Optimalité : Le code préfixe complet de l’arbre de Huffman est minimal i.e. aucun arbre digital ne compresse mieux le texte T que Huffman(A,(fi)).
Soient x le caractère ayant la moins grande fréquence, et y le caractère ayant la seconde moins grande fréquence. Il existe un codage préfixe optimal tq. x et y ont le même père.
Optimalité : Le code préfixe complet de l’arbre de Huffman est minimal i.e. aucun arbre digital ne compresse mieux le texte T que Huffman(A,(fi)).
Soient x le caractère ayant la moins grande fréquence, et y le caractère ayant la seconde moins grande fréquence. Il existe un codage préfixe optimal tq. x et y ont le même père.
On considère l’alphabet A0 = A ? {x,y} + z, ou` z est une nouvelle lettre ayant une fréquence f (z) = f (x) + f (y).
Soit T0 l’arbre d’un codage optimal pour A’, alors l’arbre T obtenu à partir de T0 en rempla¸cant la feuille associée à z par un noeud interne ayant x et y comme feuilles représente un codage optimal pour A.
Définition. (E,I) est un matro¨?de si E est un ensemble de n éléments, I est une famille de parties de E, I ? P(E) vérifiant :
I l’hérédité : X ? I =? ?Y ? X, Y ? I.
I l’échange : (A,B ? I,|A| < |B|) =? ?x ? B ? A tel que A ? {x} ? I.
Si X ? I, on dit que X est un indépendant.
Définition. (E,I) est un matro¨?de si E est un ensemble de n éléments, I est une famille de parties de E, I ? P(E) vérifiant :
I l’hérédité : X ? I =? ?Y ? X, Y ? I.
I l’échange : (A,B ? I,|A| < |B|) =? ?x ? B ? A tel que A ? {x} ? I.
Si X ? I, on dit que X est un indépendant.
Exemples :
I Les matro¨?des vectoriels. E = {v1,...,vn} un ensemble de vecteurs d’un espace vectoriel et I la famille de tous les sous-ensembles de vecteurs de E linéairement indépendants. Alors M = (E,I) est un matro¨?de.
I l’hérédité : X ? I =? ?Y ? X, Y ? I.
I l’échange : (A,B ? I,|A| < |B|) =? ?x ? B ? A tel que A ? {x} ? I.
Si X ? I, on dit que X est un indépendant.
Exemples :
I Les matro¨?des vectoriels. E = {v1,...,vn} un ensemble de vecteurs d’un espace vectoriel et I la famille de tous les sous-ensembles de vecteurs de E linéairement indépendants. Alors M = (E,I) est un matro¨?de.
I Les matro¨?des graphiques (les forêts d’un graphe). Soit G = (S,E) un graphe non orienté et I la famille des forêts de G : F ? I si et seulement si F est acyclique. Alors M = (E,I) est un matro¨?de.
Etant donné un matro¨?de´ M = (E,I), on dit qu’un élément x ?/F est une extension de F ? I si F ? {x} ? I.
Si F est un sous-ensemble indépendant d’un matro¨?de M, on dit que F est maximal s’il ne possède aucune extension (i.e. il est maximal au sens de l’inclusion).
Etant donné un matro¨?de´ M = (E,I), on dit qu’un élément x ?/F est une extension de F ? I si F ? {x} ? I.
Si F est un sous-ensemble indépendant d’un matro¨?de M, on dit que F est maximal s’il ne possède aucune extension (i.e. il est maximal au sens de l’inclusion).
Thm. Tous les sous-ensembles indépendants maximaux d’un matro¨?de ont le même cardinal.
Etant donné un matro¨?de´ M = (E,I), on dit qu’un élément x ?/F est une extension de F ? I si F ? {x} ? I.
Si F est un sous-ensemble indépendant d’un matro¨?de M, on dit que F est maximal s’il ne possède aucune extension (i.e. il est maximal au sens de l’inclusion).
Thm. Tous les sous-ensembles indépendants maximaux d’un matro¨?de ont le même cardinal.
On dit qu’un matro¨?de M = (E,I) est pondéré si l’on dispose d’une fonction de pondération w de E dans R+ qui affecte un poids strictement positif w(x) à chaque élément x ? E.
Pour F ? E : w(F) = Pw (x).
x?F
Question : Trouver un indépendant de poids maximal (optimal).
GLOUTON
1 Trier les éléments de E par poids décroissant : w(e1) ? w(e2) ? ... ? w(en)
4
Lemme Supposons M = (E,I,w) (avec I 6= {?}) un matro¨?de pondéré; et E trié par ordre de poids décroissant. Soit x le premier élément de E tel que {x} soit indépendant, alors il existe un sous-ensemble optimal F de E qui contient {x}.
Lemme Supposons M = (E,I,w) (avec I 6= {?}) un matro¨?de pondéré; et E trié par ordre de poids décroissant. Soit x le premier élément de E tel que {x} soit indépendant, alors il existe un sous-ensemble optimal F de E qui contient {x}.
Preuve.
I Soit H un indépendant de poids optimal. Supposons que x ?/H. Aucun élément de H n’a un poids supérieur à w(x).
I Construire à partir de H un ensemble F indépendant de poids optimal et qui contient x.
Lemme Supposons M = (E,I,w) (avec I 6= {?}) un matro¨?de pondéré; et E trié par ordre de poids décroissant. Soit x le premier élément de E tel que {x} soit indépendant, alors il existe un sous-ensemble optimal F de E qui contient {x}.
Preuve.
I Soit H un indépendant de poids optimal. Supposons que x ?/H.
Aucun élément de H n’a un poids supérieur à w(x).
Preuve : y ? H implique que {y} est indépendant, puisque H ? I et I est héréditaire. Donc w(x) ? w(y) pour tout y ? H.
I Construire à partir de H un ensemble F indépendant de poids optimal et qui contient x.
Lemme Supposons M = (E,I,w) (avec I 6= {?}) un matro¨?de pondéré; et E trié par ordre de poids décroissant. Soit x le premier élément de E tel que {x} soit indépendant, alors il existe un sous-ensemble optimal F de E qui contient {x}.
Preuve.
Aucun élément de H n’a un poids supérieur à w(x).
Preuve : y ? H implique que {y} est indépendant, puisque H ? I et I est héréditaire. Donc w(x) ? w(y) pour tout y ? H.
I Construire à partir de H un ensemble F indépendant de poids optimal et qui contient x.
Commencer avec F = {x}. En se servant de la propriété d’échange, on trouve itérativement un nouvel élément de H pouvant être ajouté à F jusqu’à ce que |F| = |H|, en préservant l’indépendance de F.
Lemme Supposons M = (E,I,w) (avec I 6= {?}) un matro¨?de pondéré; et E trié par ordre de poids décroissant. Soit x le premier élément de E tel que {x} soit indépendant, alors il existe un sous-ensemble optimal F de E qui contient {x}.
Preuve.
I Soit H un indépendant de poids optimal. Supposons que x ?/H.
Aucun élément de H n’a un poids supérieur à w(x).
Preuve : y ? H implique que {y} est indépendant, puisque H ? I et I est héréditaire. Donc w(x) ? w(y) pour tout y ? H.
I Construire à partir de H un ensemble F indépendant de poids optimal et qui contient x.
Commencer avec F = {x}. En se servant de la propriété d’échange, on trouve itérativement un nouvel élément de H pouvant être ajouté à F jusqu’à ce que |F| = |H|, en préservant l’indépendance de F. Alors, F = H \ {y} ? x pour un certain y ? H, et donc w(F) = w(H) ? w(y) + w(x) ? w(H).F est optimal et x ? F.
Lemme. Soit x le premier élément de E choisi par GLOUTON
(c’est-à-dire le singleton indépendant de poids maximal) pour le matro¨?de pondéré M = (E,I,w). Trouver un sous-ensemble indépendant de poids maximal contenant x, revient à trouver un sous-ensemble indépendant de poids maximal du matro¨?de pondéré M0 = (E0,I0,w0), ou`
E0 = {y ? E \ {x} : {x,y} ? I} , I0 = {H ? E \ {x} : H ? {x} ? I}, et la fonction de pondération de M0 est celle de M, restreinte à E0.
Lemme. Soit x le premier élément de E choisi par GLOUTON
(c’est-à-dire le singleton indépendant de poids maximal) pour le matro¨?de pondéré M = (E,I,w). Trouver un sous-ensemble indépendant de poids maximal contenant x, revient à trouver un sous-ensemble indépendant de poids maximal du matro¨?de pondéré M0 = (E0,I0,w0), ou`
E0 = {y ? E \ {x} : {x,y} ? I} , I0 = {H ? E \ {x} : H ? {x} ? I}, et la fonction de pondération de M0 est celle de M, restreinte à E0. (On appelle M0 la contraction de M par l’élément x).
Preuve. Si F est un sous-ensemble indépendant de poids maximal de M contenant x, alors F0 = F \ {x} est un sous-ensemble indépendant de M0. Inversement, un sous-ensemble indépendant F0 de M0 engendre un sous-ensemble indépendant F = F0 ? {x} de M. Comme nous avons dans les deux cas w(F) = w(F0) + w(x), une solution de poids maximal pour M contenant x donne une solution de poids maximal sur M0, et réciproquement.
Théorème. L’algorithme GLOUTON donne une solution optimale. Preuve. Soit ek le premier élément indépendant de E, i.e. le premier indice i de l’algorithme tel que ei ? I.
I Il existe une solution optimale qui contient ek (choix glouton). I Puis, par récurrence on obtient que GLOUTON donne une solution optimale (sous-structure optimale) : on se restreint à une solution contenant ek, et on recommence avec E0 = E ? ek et I0 = {X ? E0;X ? {ek} ? I}.
Théorème. L’algorithme GLOUTON donne une solution optimale. Preuve. Soit ek le premier élément indépendant de E, i.e. le premier indice i de l’algorithme tel que ei ? I.
I Il existe une solution optimale qui contient ek (choix glouton). I Puis, par récurrence on obtient que GLOUTON donne une solution optimale (sous-structure optimale) : on se restreint à une solution contenant ek, et on recommence avec E0 = E ? ek et I0 = {X ? E0;X ? {ek} ? I}.
Théorème. L’algorithme GLOUTON donne une solution optimale. Preuve. Soit ek le premier élément indépendant de E, i.e. le premier indice i de l’algorithme tel que ei ? I.
I Il existe une solution optimale qui contient ek (choix glouton). I Puis, par récurrence on obtient que GLOUTON donne une solution optimale (sous-structure optimale) : on se restreint à une solution contenant ek, et on recommence avec E0 = E ? ek et I0 = {X ? E0;X ? {ek} ? I}.
I Il suffit de regarder E0 = {ek+1,...,en} car les éléments ej,j<k ne peuvent pas être extension d’un indépendant (sinon, par hérédité, aussi indépendants et choisis au lieu de ek).
Exemple des forêts d’un graphe : algorithme glouton de Kruskal pour construire un arbre de poids minimal. Trier toutes les arêtes par poids croissant, et sélectionner au fur et à mesure celles qui ne créent pas de cycle si les on a joute à l’ensemble courant.
1 Trier les éléments de E par poids décroissant : w(e1) ? w(e2) ? ... ? w(en)
4
1 Trier les éléments de E par poids décroissant : w(e1) ? w(e2) ? ... ? w(en)
4
Soit n = |E|, la phase de tri de GLOUTON prend un temps O(n log n).
Chaque exécution de la ligne 4 impose de vérifier si l’ensemble F ? {x} est ou non indépendant.
Si cette vérification prend un temps f (n) et les comparaisons se font en temps constants, l’algorithme GLOUTON prend un temps
O(n log n) + nf (n).
Problème :
I n tâches T1...Tn, toutes de durée 1, deadlines associées : d1, ..., dn avec pénalités w1,...,wn si deadline dépasseé.
I Un ordonnancement est une permutation des tâches : première tâche commence au temps 0 et termine au temps 1, deuxième tâche commence au temps 1 et termine au temps 2 ...
I Si une tâche Ti commence après sa deadline di alors on a la pénalité wi.
I But : trouver un ordonnancement qui minimise la pénalité totale des tâches en retard.
I tâche à l’heure : tâche finie avant la dead line
I tâche en retard : tâche finie après la dead line
Ordre canonique on peut se restreindre :
I aux ordonnancements ou` les tâches à l’heure précèdent les tâches en retard;
I aux ordonnancement ou` les tâches à l’heure sont classées par ordre de deadline croissant.
Remarque : minimiser la pénalité totale des tâches en retard = maximiser la pénalité des tâches à l’heure.
Définition. Un ensemble de tâches est dit indépendant ssi les tâches peuvent être exécutées en étant toutes à l’heure.
Lemme. A ensemble de tâches, Nt(A) = nombre de tâches de deadline ? t.
Les propositions suivantes sont équivalentes :
1. A est indépendant
2. Pour tout t = 1,2,...,n, Nt(A) ? t.
3. Ordre canonique ? pas de tâches en retard.
Exemple : 7 tâches
|
tâche |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
deadline |
4 |
2 |
4 |
3 |
1 |
4 |
6 |
|
pénalité |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
Trier les tâches par wi décroissants; puis appliquer l’algorithme glouton en prenant la tâche si elle tient sans pénalité (réorganiser selon l’ordre canonique à chaque nouvel ajout).
Exemple : 7 tâches
|
tâche |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
deadline |
4 |
2 |
4 |
3 |
1 |
4 |
6 |
|
pénalité |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
Trier les tâches par wi décroissants; puis appliquer l’algorithme glouton en prenant la tâche si elle tient sans pénalité (réorganiser selon l’ordre canonique à chaque nouvel ajout).
Sur l’exemple :
Exemple : 7 tâches
|
tâche |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
deadline |
4 |
2 |
4 |
3 |
