Algorithmes gloutons [gl] Algorithmique
L’algorithme glouton ne donne pas l’optimum si notre but est de maximiser la dur ee totale de location du v ehicule M^eme si on classe les demandes de location par dur ees d ecroissantes, un algorithme glouton ne donnera pas une solution optimale : le tableau ci-dessus pr esente un contre-exemple
Algorithmes gloutons - Education
D’autres systèmes ne sont pas canoniques L’algorithme glouton ne répond alors pas de manière optimale Par exemple, avec le système {1,3,6,12,24,30}, l’algorithme glouton répond en proposant le rendu 49 = 30+12+6+1, soit 4 pièces alors que la solution optimale est 49 = 2×24+1, soit 3 pièces La réponse à cette difficulté
ALG TD Algorithmes Gloutons - IRISA
4 Un algorithme glouton qui s electionne les programmes par ordre d ecroissant de cout^ maximise-t-il l’espace utilis e ? Si oui, le prouver, si non, donner un contre-exemple Exercice 3 (Algorithme de Prim) En th eorie des graphes, on peut utiliser l’algorithme de Prim a n de calculer un arbre couvrant minimal
Bienvenue sur Département Informatique et Interactions
premier choix glouton solution optimale 6 sous-structure optimale solution optimale du sous-problème induit par le premier choix 7 s e M e : e s s: M = f 1; 2; 5 g
Conception dalgorithmes et applications (LI325) Cours 7 et 8
I Propri et e du choix glouton :Il existe toujours une solution optimale commen˘cant par un choix glouton I Propri et e de sous-structure optimale :trouver une solution optimale contenant le premier choix glouton se r eduit a trouver une solution optimale pour un sous-probl eme de m^eme nature
Approche de sélection d’attributs pour la classification
glouton, c'est-à-dire ne permettant pas les retours en arrière Dans cet article, nous avons proposé une approche de sélection d’attributs pour pallier cette limite de l’algorithme RFE-SVM Notre approche consiste à combiner l'algorithme RFE-SVM avec des opérateurs de recherche locale,
Optimisation pour lapprentissage profond
Ludovic Trottier Adam •Algorithme 1 Échantillonage: (???? , )~ Ƹ ???? , 1≤????≤ 2 Gradient: ෝ= 1 σ =1 ???????? ???? ;????, 3 1er moment: ←????1 +1−????1 ෝ
COURS ALGORITHMIQUE ET PROGRAMMATION INFORMATIQUE
• Algorithme : mot dérivé du nom du mathématicien al_Khwarizmi qui a vécu au 9ème siécle, était membre d’un académie des sciences à Bagdad • Un algorithme prend des données en entrée , exprime un traitement particulier et fournit des données en sortie • Programme : série d’instructions pouvant s’exécuter
[PDF] corrige bac pro gestion administration 2016
[PDF] corrigé tonea factory
[PDF] epreuve e2 gestion administrative des relations avec le personnel 2017
[PDF] epreuve e2 gestion administrative des relations avec le personnel 2015
[PDF] der krieg otto dix histoire des arts
[PDF] otto dix der krieg gravures
[PDF] gestion admission bac pro
[PDF] der krieg otto dix description
[PDF] gestion admission post bac 2017
[PDF] gestion admission post bac identifiant
[PDF] otto dix der krieg analyse du tableau
[PDF] la monnaie évaluation ce2
[PDF] apb gestion oullins
[PDF] gestion admission post bac enseignant
Algorithmes gloutons
Stéphane Grandcolas
stephane.grandcolas@univ-amu.frProblèmes d'optimisation.[Solutions]
permutations, sous-ensembles, configurations particulières,...problème de décision: existe-t-il une solution?
[Solutions optimales]les solutions qui maximisent (resp. minimisent) une fonction donnéeproblème d'optimisation: trouver une solution optimale.
Algorithmes gloutons - Stéphane Grandcolas - p.1Problèmes d'optimisation.[Exemples]
arbres couvrants de poids minimal,plus longue sous séquence commune,plus court trajet passant par une ensemble de villes donné,permutation d'une séquence de colis la mieux équilibrée,...
Algorithmes gloutons - Stéphane Grandcolas - p.2 Problèmes d'optimisation.[Approche générale]un premier choix,des sous-problèmes correspondants aux différents choix,une solution optimale est déduite des solutions optimales des
sous-problèmes. [Une solution est une suite de choix] Algorithmes gloutons - Stéphane Grandcolas - p.3 Exemple : placement des convives.Placernconvives en minimisant le nombre de voisins en conflits. placer_les_convives(E,P)1siE=∅alors
2siPest meilleur queMalors
3M:=P,
4sinon
5pour chaquec?Efaireon envisage successivement de placer
6placer_les_convives(E- {c},P?c),chaque convive deEà la position courante
On va énumérer lesn!permutations desnconvives Algorithmes gloutons - Stéphane Grandcolas - p.4Exemple : placement des convives.Approche glouton :on envisage un seul choix à chaque étape, celui
qui semble le meilleur à cet instant(par exemple le convive qui devrait être le plus difficile à placer). placer_les_convives(E)1S:=??,
2tant queE?=∅faire
3U:={c?Etel quecn'est pas en conflit avec le dernier convive deS},
4siU=∅alors
5U:=E,
6 choisir le convivec?Uqui est le plus en conflit avec des convives deE,
7E:=E- {c},
8S:=S?c,
9renvoyerS
Pas de garantie de l'optimalité mais coût réduit. Algorithmes gloutons - Stéphane Grandcolas - p.5 Algorithmes gloutons.recherche exhaustive :on explore systématiquement tous les choix possibles, programmation dynamique :mémorisation des solutions de sous-problèmes qui apparaissent plusieurs fois (si il y en a), algorithmes gloutons :sélection d'un choix particulier et traitement du sous-problème correspondant (et non pas de tous les sous-problèmes) :heuristique de choix Algorithmes gloutons - Stéphane Grandcolas - p.6 Algorithmes gloutons.Un algorithme glouton construit une solution pas à passans revenir sur ses décisions,en effectuant à chaque étape le choix qui semble le meilleur,en espérant obtenir un résultat optimum global
Exemple rendu de monnaie :avec le moins possible de pièces. Algorithme glouton :répéter le choix de la pièce de plus grande valeur qui ne dépasse pas la somme restante tant que celle-ci n'est pas nulle Algorithmes gloutons - Stéphane Grandcolas - p.7Algorithmes gloutons.
énumération de
toutes les configurations possibles solution optimale ?Algorithmes gloutons - Stéphane Grandcolas - p.8Algorithmes gloutons.
solution optimale choix gloutons Choix glouton : solution non optimale (heuristique glouton) ?Algorithmes gloutons - Stéphane Grandcolas - p.8Algorithmes gloutons.
solution optimaleChoix glouton optimal
Algorithmes gloutons - Stéphane Grandcolas - p.8Algorithmes gloutons.Approche glouton
suivant les problèmes pas de garantie d'optimalité (heuristique glouton)peu couteuse (comparée à une énumération exhaustive)choixintuitif Une très bonne approche lorsqu'elle produit des solutions optimales Une bonne approche pour des problèmes difficiles (i.e. les autres approches sont très couteuses) où on ne cherche pas absolument l'optimalité Algorithmes gloutons - Stéphane Grandcolas - p.9 Exemple : empaquetage.un ensemble d'objetsE={1,...,n}de poidsp1,...,pn des boites de capacitésCProblème: placer les objets dans les boites
en respectant leurs capacitésen utilisant le moins possible de boites Méthode :par choix successifs d'un objet et d'une boite Choix glouton :placer le premier objet dans la première boîte où c'est possible Algorithmes gloutons - Stéphane Grandcolas - p.10Exemple : empaquetage.Exemple.
7 6 3 4 8 5 9 2
capacité 11poids ?Algorithmes gloutons - Stéphane Grandcolas - p.11Exemple : empaquetage.Exemple.
7 6 3 4 8 5 9 2
capacité 11poids ?Algorithmes gloutons - Stéphane Grandcolas - p.11Exemple : empaquetage.Exemple.
7 6 3 4 8 5 9 2
capacité 11poids 7 ?Algorithmes gloutons - Stéphane Grandcolas - p.11Exemple : empaquetage.Exemple.
7 6 3 4 8 5 9 2
capacité 11poids 7 6 ?Algorithmes gloutons - Stéphane Grandcolas - p.11Exemple : empaquetage.Exemple.
7 6 3 4 8 5 9 2
capacité 11poids 7 63?Algorithmes gloutons - Stéphane Grandcolas - p.11
Exemple : empaquetage.Exemple.
7 6 3 4 8 5 9 2
capacité 11poids 7 634 ?Algorithmes gloutons - Stéphane Grandcolas - p.11
Exemple : empaquetage.Exemple.
7 6 3 4 8 5 9 2
capacité 11poids 7 634 8 ?Algorithmes gloutons - Stéphane Grandcolas - p.11
Exemple : empaquetage.Exemple.
7 6 3 4 8 5 9 2
capacité 11poids 7 634 8 5 ?Algorithmes gloutons - Stéphane Grandcolas - p.11
Exemple : empaquetage.Exemple.
7 6 3 4 8 5 9 2
capacité 11poids 7 634 8 5 9 ?Algorithmes gloutons - Stéphane Grandcolas - p.11
Exemple : empaquetage.Exemple.
7 6 3 4 8 5 9 2
capacité 11poids 7 634
8 5 92
Algorithmes gloutons - Stéphane Grandcolas - p.11Exemple : empaquetage.
procédureEmpaqueter(n,p,C)Cla capacité des boites,
out :le nombre de boites utilisées, c[ ]représente les capacités résiduelles des boites1m= 0,
2c[1] =C,
3 pouri= 1ànfaire
4b= 1,
6b=b+ 1,
7 sib=m+ 1alors
8m=m+ 1,
9c[b] =C,
10c[b] =c[b]-p[i],
11 renvoyerm
Algorithmes gloutons - Stéphane Grandcolas - p.12 Exemple : empaquetage.Un bon choix glouton : prendre l'objet de plus grand poids capacité 11poids9 8 7 69 8 7 6 5 4 3 2
?Algorithmes gloutons - Stéphane Grandcolas - p.13 Exemple : empaquetage.Un bon choix glouton : prendre l'objet de plus grand poids capacité 11poids9 8 7 69 8 7 6 5 4 3 2
5 ?Algorithmes gloutons - Stéphane Grandcolas - p.13 Exemple : empaquetage.Un bon choix glouton : prendre l'objet de plus grand poids capacité 11poids9 8 7 69 8 7 6 5 4 3 2
54?Algorithmes gloutons - Stéphane Grandcolas - p.13 Exemple : empaquetage.Un bon choix glouton : prendre l'objet de plus grand poids capacité 11poids
9 8 7 69 8 7 6 5 4 3 2
543?Algorithmes gloutons - Stéphane Grandcolas - p.13 Exemple : empaquetage.Un bon choix glouton : prendre l'objet de plus grand poids capacité 11poids
9 8 7 69 8 7 6 5 4 3 2
5432Algorithmes gloutons - Stéphane Grandcolas - p.13 Exemple : empaquetage.Le choix du paquet de plus grand poids n'est pourtant pas optimal poids capacité 126 5 5 3 3 2 6 5 533
2 6 5 52
33
Algorithmes gloutons - Stéphane Grandcolas - p.14
Algorithmes gloutons : optimalité.Un algorithme glouton produit des solutions optimales si les deux
propriétés suivantes sont vérifiées : [propriété du choix glouton]il existe toujours une solution optimale qui contient un premier choix glouton En général on montre que toute solution optimale contient oudébute par un choix glouton. [propriété de sous-structure optimale]toute solution optimalecontient une sous-structure optimaleSoitSune solution optimale du problèmePcontenant le choixC, et
S ?=S?{C}. Alors,S?est une solution optimale du sous-problèmePCrésultant du choixC dans le problèmeP. Algorithmes gloutons - Stéphane Grandcolas - p.15Algorithmes gloutons : choix optimal.
premier choix glouton solution optimale Algorithmes gloutons - Stéphane Grandcolas - p.16Algorithmes gloutons : choix optimal.
sous-structure optimale solution optimale du sous-problème induit par le premier choix Algorithmes gloutons - Stéphane Grandcolas - p.17 Exemple : rendu de monnaie.s: somme à atteindreM: valeurs des pièces de monnaie
Objectif :constituer la sommesavec le moins possible de piècesExemple :M={1,2,5}ets= 10
Solution optimale:5 + 5(2 pièces)
Algorithmes gloutons - Stéphane Grandcolas - p.18 Exemple : rendu de monnaie.Algorithme glouton: choisir des pièces tant que la somme n'est pas atteinte Heuristique de choix: la pièce de valeur la plus grande (inférieure à la somme restant à compléter) Algorithmes gloutons - Stéphane Grandcolas - p.19 Rendu de monnaie.[propriété du choix glouton] Remarque :toute solution optimale contient deux pièces de 2 et aucune de 1 ou au plus une pièce de 1 et au plus une pièce de 20/0 0/1 1/0 1/1 2/0
Sis≥5toute solution optimale contient au moins une pièce de 5 : c'est le choix glouton. Sisvaut 1, 2, 3 ou 4, l'algorithme fait un bon premier choix (la valeur 2 ou la valeur 1) Toute solution optimale contient donc un choix glouton Algorithmes gloutons - Stéphane Grandcolas - p.20 Rendu de monnaie.[propriété de sous-structure optimale]SoitSune solution optimale pour la sommes,
soitC ?Sun choix glouton (la plus grosse pièce deS). AlorsS?=S- {C}est une solution optimale pours-valeur(C).Preuve.Par l'absurde : soitS??meilleure queS?pour
s-valeur(C), alorsS??? {C}est meilleure queS?? {C}pours. Contredit l'hypothèse queS?? {C}=Sest optimale. Algorithmes gloutons - Stéphane Grandcolas - p.21Rendu de monnaie : preuve de l'optimalité.Pn: caractérise les problèmes dont les solutions optimales comportent
au plusnpiècesPreuve par récurrence surn:
base :le choix glouton produit des solutions optimales pour les problèmesP1(la solution se réduit à la plus grande pièce de valeur inférieure ou ègale às)hypothèse :l'algorithme glouton produit des solutions optimales pour les problèmesPn induction :l'algorithme glouton produit des solutions optimales pour les problèmesPn+1 Algorithmes gloutons - Stéphane Grandcolas - p.22 Rendu de monnaie : preuve de l'optimalité.preuve :soitSune solution optimale de taillen+ 1(sommes),Scontient donc un premier choix gloutonC ?S(propriété du choix
glouton). AlorsS?{C}est une solution optimale de taillenpours-valeur(C) (propriété de sous-structure optimale). Hypothèse de récurrence : l'algorithme glouton produit unesolution optimaleS?pour la sommes-valeur(C). S ?? {C}constitue donc une solution optimale pourscorrespondant au choix glouton. Algorithmes gloutons - Stéphane Grandcolas - p.23quotesdbs_dbs43.pdfusesText_43