[PDF] Algorithmes gloutons II- Définition et principe:

View - Download Algorithmes gloutons

Previous PDF

Next PDF

1

I- Introductions ssssm

La résolution d'un problème algorithmique peut parfois se faire à l'aide de techniques générales ,

des " paradigmes», qui sont selon le philosophe des sciences Thomas Samuel Kuhn des

découvertes scientifiques universellement reconnues qui, pour un temps, fournissent à un groupe de

chercheurs des problèmes types et des solutions. Ces techniques ont pour avantage d'être applicables à un grand nombre de situations. Parmi ces méthodes on peut citer par exemple le fameux principe "diviser pour régner" :

1.Diviser : on divise les données initiales en plusieurs sous-parties.

2.Régner : on résout récursivement chacun des sous-problèmes associés (ou on les résout

directement si leur taille est assez petite)

3.Combiner : on combine les différents résultats obtenus pour obtenir une solution au

problème initial.

A.LOUGHANI

Algorithmes gloutons

Issu du latin impérial glut(t)onem, " glouton », dérivé de glut(t)us, " gosier » : Qui mange avec

avidité et excès, voracement. Un enfant glouton, une faim gloutonne, cet homme est un glouton, une jeunesse gloutonne de plaisirs...etc

N. m. Mammifère carnivore de la famille des Mustélidés, un glouton vit essentiellement dans les

régions arctiques. 2

1.Une forme récursive "Top down" dite de mémoïsation :

On utilise directement la formule de récurrence. Lors d'un appel récursif, avant d'effectuer un calcul on regarde dans le tableau ars»(»lndrsi,icr si ce travail n'a pas déjà été effectué.

2.Une forme itérative "Bottom Up" :

On résout d'abord les sous problèmes de la plus "petite taille", puis ceux de la taille "d'au dessus", etc. Au fur et à mesure on stocke les résultats obtenus dans le tableau ars»(»lndrsi,icr.

On continue jusqu'à la taille voulue.

Les algorithmes gloutons, que l'on rencontre principalement pour résoudre des problèmes d'optimisation, constituent l'une de ces techniques générales de résolution.

II- Définition et principe:

Lors de la résolution d'un problème d'optimisation, la construction d'une solution se fait souvent de

manière séquentielle, l'algorithme faisant à chaque étape un certain nombre de choix. Le principe

glouton consiste à faire le choix qui semble le meilleur sur le moment (choix local), sans se préoccuper des conséquences dans l'avenir, et sans revenir en arrière. Un algorithme glouton est donc un algorithme qui ne se remet jamais en question et qui se dirige le

plus rapidement possible vers une solution. Aveuglé par son appétit démesuré, le glouton n'est pas

sûr d'arriver à une solution optimale, mais il fournit un résultat rapidement. Même si la solution

n'est pas optimale, il n'est pas rare que l'on s'en contente, on rentre alors dans le monde des algorithmes d'approximation.

Pour que la méthode gloutonne ait une chance de fonctionner, il faut que le choix local aboutisse à

un problème similaire plus petit. La méthode gloutonne ressemble ainsi à la programmation

dynamique. Mais la différence essentielle est que l'on fait d'abord un choix local et on résout

ensuite un problème plus petit (progression descendante). En programmation dynamique, au

contraire, on commence par résoudre des sous-problèmes, dont on combine ensuite les résultats

(progression ascendante).

III- Le problème du rendu de monnaies ssssm

àTsSlén nlusatsgdl:eb»rs ssssm

On considère un système de pièces de monnaie. La question est la suivante : quel est le nombre minimal de pièces à utiliser pour rendre une él»»rsaluu(r ? De plus, quelle est la répartition des pièces correspondante ?

La valeur de la solution optimale sera ce nombre minimal de pièces, et la solution en elle-même la

liste des pièces nous permettant de rendre la somme. Formalisons un peu ce problème avec quelques notations mathématiques : Le système de pièces de monnaie peut être modélisé par un n-uplet d'entiers naturels

A.LOUGHANIOu encore la méthodeiGH '' la programmation dynamique''. Pour ce faire, et donc éviter de

recalculeriplusieurs fois les solutions des mêmes sous-problèmes, on va mémoriser ces solutions

dans une sorte de mémoire cache. Celle-ci sera un tableau ou liste, selon le langage

d'implémentation utilisé, et possédera une ou deux dimensions suivant les cas. Sa mise en pratique

peut prendre deux formes : 3 S=(c1,c2,...,cn), où ci représente la valeur de la pièce ;

IOn suppose que c1=1 et que c1

IUne somme à rendre est un X ;

IUne répartition de pièces est un (x1,x2,...,xn), où x1 représente le

nombre de pièces c1, x2 le nombre de pièces c2, ...etc. Le nombre total de pièces d'une telle

répartition est donc - i 1 i n xi .

On peut reformuler la question comme suit :

pour tout entier naturel X, on cherche un n-uplet d'entiers naturels (x1,x2,...,xn) qui i 1 i n xi - i 1 i n xi.ci = X s ssssm b-L'égalité - i 1 i n xi.ci = X signifie juste que l'on rend la bonne somme. c- - i 1 i n xi = x1 + x2 +...+ xn . s sss vérifiant - i 1 i 9 xi = 6.

Pour i≥4 on a nécessairement xi = 0 car les pièces correspondantes ont une valeur plus grande que

la somme à rendre. La contrainte devient donc x1+2x2+5x3=6 et il y a cinq triplés qui la vérifient :

I(6,0,0)

I(4,1,0)

I(2,2,0)

I(1,0,1)

I(0,3,0)

A.LOUGHANI

a-L'hypothèse c1=1 garantit qu'un rendu toujours possible puisque les sommes à rendre sont entières. Dans la zone euro, le système actuellement en circulation est S=(1,2,5,10,20,50,100,200,500),

100 centimes = 1€, 200 centimes = 2€, 500 centimes billet de 5€ .

Avec les notations précédentes, on a ainsi c1 = 1, c2 = 2, c3 = 5,..., c9 = 500. Et bien sûr n = 9.

Pour rendre par exemple une somme de X = 6 euros, on doit considérer les n-uplets (x1,x2,...,x9)

Le triplet qui minimise x1 +x2 +x3 est alors la solution, il s'agit en l'occurrence de (1,0,1). Il faut ainsi

deux pièces pour rendre une somme de 6 euros, une pièce de 1 et un de 5. 4 Pour terminer cette sous-partie, demandons-nous ce qu'un humain ferait dans une telle situation. Il

commencerait sans doute par rendre la plus grande pièce "possible", puis ferait de même avec le

reste jusqu'à ce que la somme soit rendue. C'est d'ailleurs ce que font des millions de commerçants

quotidiennement.

D'un point de vue algorithmique cela donne :

1.Choisir la plus grande pièce du système de monnaie inférieure ou égale à la somme à rendre.

2.Déduire cette pièce de la somme.

3.Si la somme n'est pas nulle recommencer à l'étape 1.

Ce point de vue est un algorithme glouton.

Cette méthode est séduisante, car simple, mais malheureusement pas toujours optimale.Voici un contre-exemple :

Par contre, pour rendre cette même somme avec le système (1,3,4) il n'y a pas optimalité. En effet

on rendra d'abord une pièce de 4, puis une pièce de 1 et enfin une autre pièce de 1, c'est-à-dire trois

pièces. Or on pouvait rendre de façon plus performante deux pièces de 3.

Dans le système de pièces européen, on peut montrer que l'algorithme glouton donne toujours

tursélet nluslg n»,erT

3TsSértalIilarsr silarsSx clus ssssm

,IsêusgértalIilarAslusgrt s(idndrs ssssm

Où :

pieces : les types de pièces possibles, une liste d'entiers classées dans le sens décroissant.

Somme : la somme à rendre, un entier.

Choisies : une liste indiquant le nombre de pièces choisies pour chacune des pièces. b- Code pythons ssssm

A.LOUGHANI

n ← longueur de la liste pieces pour i allant de 0 à n-1

Tant que somme >= pieces[i]

somme ← somme - pieces[i] choisies[i] ← choisies[i] + 1 renvoyer choisies

Si l'on doit rendre la somme de 6 avec le système (1,2,5), la méthode précédente fournit un résultat

optimal à savoir un de 5 puis une pièce de 1, i.e. deux pièces. On suppose que l'on dispose d'un nombre de pièces illimité et que l'on8€ à rendre , c-à-d 800 centimes, dans le système européen de monnaie : F

Udtes noudutrdi tolt Tlootl utb

-otfdnutrDihtelireltb

PnvvD Di tBnlto_DitClncooltelireltJtnicus tr_nit 2 uq:ltfchucftrlt:DiidcltatluatBnltrdi tiDuelthdc lt

cotiltel ultBnltrl tvcqhl trltLtnicus at4tnicus tlutItnicus 'tVitul ulto_dopDecuT:ltdClhtb

UdtesvDi ltrdi tUlt Tlootl utb

U_dopDecuT:ltiDn tveDvD ltrltelireltniltvcqhltrltLtnicus tlutrlnytvcqhl trltItnicus't'dc tDitCDcut èclitBn_Ditdnedcutvntelireltrlnytvcqhl trlt4tnicus tBnctl utnitelirntvon tDvuc:dotU ,'UVxàH,ï-rlftelirnV:Diidclé D::lavclhl gtb ttttttit@toliévclhl g tttttthTDc cl t@tRGSWi fDetctcitedipléigtb tttttttttttXTcolt D::ltQ@tvclhl RcS ttttttttttttttttt D::lt@t D::ltTtvclhl RcS ttttttttttttttttthTDc cl RcSt@thTDc cl RcStEtI ttttttteluneithTDc cl vclhl t@tRFGGa)GGaIGGaFGa)GaIGaFa)aIS

D::lt@tOGG

veciué__Ul tvcqhl thTDc cl t Diutb__g veciuéelirnV:Diidclé D::lavclhl gg

Ul tvcqhl thTDc cl t Diutb

RIaIaIaGaGaGaGaGaGS

(clhl t@tRLa4aIS

D::lt@tJ

veciué__Ul tvcqhl thTDc cl t Diutb__g veciuéelirnV:Diidclé D::lavclhl gg

Ul tvcqhl thTDc cl t Diutb

RIatGat)S

J

-otfdnutuDnwDne t _d neletBnltolthD:vultl utèDitlutBnltoltelirntdnthocliutl utlydhuatrDihtodt D::lt

fcidolt1telirelath"1"rt1todtfcitrlto_dopDecuT:ltl utt D::l@G' (DnethlodtDitvlnutfdceltnitul utlitfcitrltèDnholtfDetrdi to_dopDecuT:ltveshsrliutb Vitvlnutul ulethlutdopDecuT:ltvDnetnilt D::lt1telireltrlt4IHtt1tvdeucetrl tvcqhl tIGHtaFHttlut)Htlut

CDcetodtesvDi ltrdi tolt Tloo'

UltveDèoq:ltrnt dht1trD tl uto_nitrl t)ItveDèoq:l tï("hD:volu trltYchTdertFdevatlyvD s trdi tnit

deucholtrltIIZ)'tUdtfDe:noducDitrntveDèoq:ltl utfDeut c:volat:dc t dtes DonucDitl utvon thD:volyl't

YchTdert'diiciptFdevt

ïstolt4t[diCcletII4F

1t\D uDi

,:sechdci xicCle custHdCder 'duTs:duchcliacifDe:duchclitluveDfl lnetr_nicCle cus ]udiutrDiistvon clne tDèwlu tvD srdiuthTdhnitnitvDcr tlutniltCdolnetlutsudiutrDiistnitvDcr t

:dyc:n:tvDnetolt dhatBnlo tDèwlu tfdnu"cot:luueltrdi tolt dhtrlt:dicqelt1t:dyc:c letodtCdolnetuDudol

di trsvd letoltvDcr t:dyc:dotdnuDec stvDnetolt dht>t ,'UVxàH,ï-rlftelirnV:Diidclé D::lavclhl gtb ttttttit@toliévclhl g tttttthTDc cl t@tRGSWi fDetctcitedipléigtb tttttttttttXTcolt D::ltQ@tvclhl RcS ttttttttttttttttt D::lt@t D::ltTtvclhl RcS ttttttttttttttttthTDc cl RcSt@thTDc cl RcStEtI tttttttd leut D::lt@@tG ttttttteluneithTDc cl Z tVithD::lihltvdetnitsiDihstrl trDiisl 't?di tiDuelthd atiDn tdCDi tnit dht1trD tBnctvlnut

hDiulicetnitvDcr t:dyc:dotlutĄDèwlu tdntvon 't(DnethTdBnltDèwlutatiDn tdCDi tnitvDcr tlutnilt

Cdolnet

(detlyl:volat ctDitdtBndueltDèwlu ttlutnit dht1trD tr_nitvDcr t:dyc:dotrlt4Gt;ptdoDe ttDittdtĄ@tLtlut

@t4Gato_circhltaliucletcatCdecltrltIt1tL'tVites n:lthlodtrdi toltudèoldnt ncCdiutb

Vèwlu I)4L

ДᬃᰝЄЄЄI4I)OIG

=i nculatDitrsfcicuttol tCdecdèol tBnctelves liuliutlitBnloBnlt Deultol tdhucDi tDntol

rshc cDi tBnctd:qileDiut1tueDnCletnilt DonucDi'tVitvelirtdoDe ttodtCdecdèoltd Dhcslt1tnitDèwlut

ulooltBnlt @tIt ctoLDèwlutctl ut:c trdi tolt dhatlut@tGt ctoLDèwlutctiLl utvd t:c trdi tolt dh'

?di tiDueltlyl:volatnilt DonucDitesdoc dèoltl utrlt:luueltuDn tol tDèwlu trdi tolt dht1trD t dnf

oltvel:cleatiDn tdCDi trDihtbt @tGatt@tIatt@tIatlutḄt@tI' ,'UVxàH,ï- O (nc tcotfdnutrsfcicetol thDiuedciul trntveDèoq:l't-hcatcoti_2tlitdtBnLniltbtodt D::ltrl tvDcr trl uDn tol tDèwlu trdi tolt dhtrDcutEueltcifseclneltDntspdoltdntvDcr t:dyc:dotrnt dht1trD '

3lodt Lshecutchctbt

'tEt')tEt'4tE'Lt^t lutvDnetĄDèwlu tb txciIci '^t (DnetCsecfcletBnltodthDiuedciultl utel vlhusltrdi tiDueltlyl:volatcot nffcutrlthdohnolethluul D::ltbtGt_tI4tEtIt_tI)tEtIt_tOtEtIt_IGt@t4GathltBnctl utèclitcifseclnetDntspdot1t4GatrDihtod hDiuedciultl utel vlhusl'tïDn tvdeoDi tdoDe trlt DonucDitesdoc dèol't'dc thltiLl utvd ishl dcel:liutodt:lcoolnelt DonucDi'

=ifciatcotfdnutlyvec:letodtfDihucDitBnctuedrncutiDueltDèwlhucfttBnctl utrlt:dyc:c letodtCdolnetuDudoltrl

Dèwlu trdi tolt dhth"1"rtodt D::lt'tEt')tEt'4tE'LttrDcutEueltodtvon tpedirltvD cèol't(DnetĄ

Dèwlu athlodt Lshecutb

:dytxciIci ?di tiDueltlyl:volatodtCdolnetuDudolthDiulinltrdi tolt dhtl utspdolt1tIG't3luult DonucDitiLl u

vd todt:lcoolnelathdetcotlyc ultniltdnuelt DonucDitrltCdolnetvon tpedirltBnltIG't=itlffluatcot nffcutrlt

velirelt lnol:liutol tDèwlu tItlut)tBnctrDiileDiutniltCdolnetuDudoltrltII't-otiLlyc ultvd trlt :lcoolnelt DonucDitBnlthluultrleicqelatiDn trceDi tdoDe tBnlthluult DonucDitl utDvuc:dol' Vitrc vD ltr_niltoc ultrltCdolne trl tDèwlu tlutrltolne tvDcr trntu2vltb VitiDultoltvDcr trnt dht(tlutoltvDcr t:dyc:dotvDcr V:dy'

VitvlnutrDihtsheceltoltv lnrD"hDrltb

è"t3Drlt(2uTDit ttttb

,CdiutrltodihletodtfDihucDitel:voceV dhtatDituecltr_dèDertodtoc ultrl tDèwlu t loDitol tCdolne t

rsheDc diul tvnc tDitel:vocutolt dh't

UdtfDihucDitel:voceV dhtl utb

,'UVxàH,ï-.ecletodtoc ultDèwlu tvdetDereltheDc diut loDitodtCdolnetrlthTdBnltDèwlu (tPtG itPtiD:èeltr_Dèwlu

Dèwlu VhTDc c t@tRGSWi

vDnetctdoodiutrltGt1ti"I ttt ct(tEtDèwlu RcSRIStC@tvDcr V:dytdoDe tttttDèwluVhTDc c RcSt@tI ttttt(tPt(tEtDèwluRcSRIS

YliCD2letDèwluVhTDc c

I (eliDi tnithd ates n:stvdetoltudèoldntrltCdolne thc"rl Dn tb

Vèwlu I)4L

élit;pgIG'FtG')L

t

Vit nvvD ltvDcr V:dyt@tFatr_nitdnuelth`ustDitdtDèwlu t@tRR)aISaRFaG'FSaRIaG')SaR4aLSSt'tVitueclttodt

oc ultDèwlutlutDitodihltodtfDihucDitel:voceV dhéDèwlu avDcr V:dygtb ?di tolt TlooatDitCDcutodtoc ultuecsltr_dèDertli ncultol tDèwlu thTDc c tb

VitelucliutrDihtb

,'UVxàH,ï-rlftttel:voceV dhéDèwlu avDcr avDcr V:dygtb tttttttt(t@tG ttttttttit@toliéDèwlu g ttttttttDèwlu VhTDc c t@tRGSWi ttttttttfDetctcitedipléigtb tttttttttttttcft(tEtDèwlu RcSRIStC@tvDcr V:dytb tttttttttttttttttDèwlu VhTDc c RcSt@tI ttttttttttttttttt(t@t(tEtDèwlu RcSRIS tttttttteluneitDèwlu VhTDc c

Dèwlu t@tRR)aISaRFaG'FSaRIaG')SaR4aLSS

Dèwlu t@toc uéelCle lré DeulréDèwlu ggg veciuéDèwlu g vDcr V:dyt@tF'G veciué__Ul tDèwlu thTDc c t Diutb__g veciuéel:voceV dhéDèwlu avDcr V:dygg

RRFaG'FSaR4aLSaR)aISaRIaG')SS

Ul tDèwlu thTDc c t Diutb

RIaIaGaIS

IG

PnvcifD'hD:

3shcolt3dinaïP-tIelt.Y,N,-=Yt=ït,x.VïV'-=tatïDnCldntveDped::latloocv l

(cleelt\lpcdiat\lpcdi'fell'fe

PhTDDo:DnC'fe

,'UVxàH,ï-quotesdbs_dbs43.pdfusesText_43

[PDF] corrige bac pro gestion administration 2016

[PDF] epreuve e2 gestion administrative des relations avec le personnel 2017

[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

[PDF] gestion scei

[PDF] gestion admission post bac mot de passe perdu

[PDF] trace écrite la monnaie ce2