Algorithmique et Programmation Projet Algorithme“Measure and Conquer”pour Maximum Independent Set

Publié par

Algorithmique et Programmation Projet : Algorithme“Measure and Conquer”pour Maximum-Independent-Set Ecole normale superieure Departement d'informatique 2011-2012 1 Contexte On s'interesse au probleme des gardiens de musee. Un musee est schematiquement forme de couloirs, ou des peintures sont accrochees. Les couloirs doivent etre surveilles par des gardiens. Quand un gardien est positionne au croisement de plusieurs couloirs, il surveille tous les couloirs attenants. Les gardiens du musee en question, tout comme la direction, ont a coeur que la surveillance ait effectivement lieu. Pour assurer le coup, la direction a utilise un algorithme glouton pour assigner les gardiens a des croisements. Cependant, il semble aux gardiens qu'ils sont legerement en sur-effectif, et que certains d'entre eux pourraient faire la sieste ou sortir pendant que les autres assurent la surveillance. C'est une nouvelle illustration du fait qu'un travailleur efficace est un faineant malin. Ils cherchent donc a determiner le nombre strictement minimal de gardiens necessaires a la surveillance du musee, afin de profiter davantage de la vie. Formellement, les couloirs du musee sont les aretes d'un graphe, et le probleme consiste a placer des gardiens sur les sommets de ce graphe de telle sorte que chaque arete soit attenante a un gardien (au moins). On cherche a placer le moins de gardien possible.

  • clique

  • taille

  • return max

  • maximum independent

  • gardien

  • i˜ ?


Publié le : mardi 19 juin 2012
Lecture(s) : 69
Tags :
Source : di.ens.fr
Nombre de pages : 3
Voir plus Voir moins
Algorithmique et Programmation Projet : Algorithme“Measure and Conquer”pour Maximum-Independent-Set
Ecolenormalesupe´rieure De´partementdinformatique td-algo@di.ens.fr 2011-2012
1 Contexte Onsinte´resseauprobl`emedesagdrs´eedemuiensu.lUcnomrsoi,tame´hcstseee´sude´ermfontmeueiq o`udespeinturessontaccroch´ees.Lescouloirsdoiventeˆtresurveill´espardesgardiens.Quandungardien estpositionne´aucroisementdeplusieurscouloirs,ilsurveilletouslescouloirsattenants.Lesgardiensdu muse´eenquestion,toutcommeladirection,ontacoeurquelasurveillanceaiteectivementlieu.Pour assurerlecoup,ladirectionautilise´unalgorithmegloutonpourassignerlesgardiens`adescroisements. Cependant,ilsembleauxgardiensquilssontle´ge`rementensur-eectif,etquecertainsdentreeux pourraient faire la sieste ou sortir pendant que les autres assurent la surveillance. C’est une nouvelle illustrationdufaitquuntravailleurecaceestunfaine´antmalin.Ilscherchentdonca`d´eterminerle nombrestrictementminimaldegardiensne´cessaires`alasurveillancedumuse´e,andeproterdavantage de la vie. Formellement,lescouloirsdumus´eesontlesareˆtesdungraphe,etleproble`meconsistea`placerdes gardienssurlessommetsdecegraphedetellesortequechaqueareˆtesoitattenante`aungardien(au moins).Oncherchea`placerlemoinsdegardienpossible.Onneconnaıˆtpasdalgorithmepolynomialpour r´esoudreceprobl`eme(quiestenfaitleMinimum Vertex Covert.lempcoP-eNuaapssga`lmeeets).Leprob
2 Terminologie Dans un graphe arbitraire, uneCliquesouitontreus´elibmesedelmmosqstenuneetsdsue-xa`d-ue.x Tr`esclairement,dansungraphe,latailledelaplusgrandecliquedugrapheestbiend´enie.Leprobl`eme Maximum-cliquequliecuneruvroatlamixamelliatederaphe.edansungts`enoisc Demˆeme,unIndependent Setest un ensemble de sommets qui ne sontpase´eserileux(ntreneaucu pairenestrelie´e).Cestdonclecontraireduneclique,etilyaunecorrespondanceentrelescliquesdun 2 grapheetlesindependentsetsdugraphecompl´ementaire(o`uE=VE). Aussi, les algorithmes de cliquesmaximumetdemaximumindependentsetsontessentiellementlameˆmechose,a`conditionde compl´ementerlegraphe. Enfin, unVertex Coveresarˆetesdugrapheu.qItlinuoehsctteuoetlsemnsedblomestsmeseenut pasdiciledevoirquelecompl´ementairedunindependentsetestunvertexcover.Parcons´equent,un Minimum Vertex Coverˆtuepetboerteridnuuna`aptrMaximum Independent Setenemt.piceuqor,´rte Ilestamusantdenoterqueleproble`medetrouverunMinimum Edge Coverpllepeusttiredia--`ste,c ensembledarˆetesquitouchetouslessommets,estluisolubleentempspolynomial(vialecalculdun couplage maximal). ´ On note Γ(xcajdstnemmosastel)`saexerangedphdsuanattnodnnno´n.eE-ensembl´eunsousW deV, lesous-graphe induit parWe´edofmrpaehelrgstemetsssomWesdsearˆeettdeEqui relient des sommets deW. Le´egrded’un sommet est son nombre de voisins.
3 Algorithme“Measure and Conquer” LalgorithmequiportelenomMeasureandConquerae´t´ed´ecriten2006parFormin,Grandoni etKratsch[1].Cestunalgorithmediviserpourre´gner,maisavecuntasdastuces.Cesauteursd´e-  0.2888n montrentquelalgorithmesex´ecuteentempsO2 dansle pire des cas, ce qui est plus rapide que l’algorithme de Bron-Kerbosch dans le pire des cas (cependant le“measure and conquer”n’est a priori
1
pas plus rapideen pratiqueis)L.i´deeedbaseestqueestqueIest un independent set, et que sivest un sommet arbitraire, alors de deux choses l’une : i) OubienvI. Dans ce cas, les voisins deverteˆsaptnevuependansv. Il s’ensuit queI− {v}est un independent set deG− {v} −Γ(v) ii) Oubienv /I. Dans ce cas,Iest un independent set deG− {v}. Onend´eduitunalgorithmequasimenttrivial: 1:functionMaxIndependentSet(G) 2:ifG=then return3:ChoisirvGmal)maxigr´edede(tnemelbare´fe´rp 4:I1MaxIndependentSet(G− {v}) 5:I2MaxIndependentSet(G− {v} −Γ(v)) 6:returnmax{I1, I2} 7:end function
3.1Ame´liorationsindispensables ´ Composantes connexes.Evidement, si le grapheGn’est pas connexe, on peut trouver un MIS de touteslescomposantesconnexeslesunesapre`slesautres,etrenvoyerleurunion.
Sommetsdomine´s.Un sommetvdomineun sommetusi{v} ∪Γ(v)⊆ {u} ∪Γ(u) (ceci implique quilssontadjacents).Nousarmonsquonpeutretirerlessommetsdomin´essansfairediminuerlataille duplusgrandindependentsetpre´sentdanslegraphe.Eneet,siIest un MIS (Maximum Independent Set) deGet quevdomineudansG, alors de deux choses l’une : ibien) OuuI. Dans ce cas, les voisins deurteˆnadenevusaptpenesI. Cela implique que les voisins 0 devne sont pas dansI,tneuqe´snocrPa.I=I− {u} ∪ {v}est un MIS deG− {u}maeˆedm,le taille queI. iibien) Ouu /Itnemedit´ev,eIest un MIS deG− {u}. Onpeutdonc,`achaqueappelr´ecursif,´eliminerlessommetsdomin´es,cequinepeutquacce´l´ererles appelsr´ecursifs.
Sommets pliables.Un sommetvestpliablesi Γ(v) ne contient pas d’anti-triangle(un anti-triangle est triplet de sommetsx, y, ztel que{x, y} ∈/ E,{x, z} ∈/ Eet{y, z} ∈/ E). L’action depliervproduit un e nouveau grapheGdn´eanteparrapport`atiedalafc¸nousviG: i) pourtoute pairex, yΓ(v), on ajoute un nouveau sommetxfy`aGsi{x, y}/E. ii) pourchaque sommetxfyojae´tutnetrsleaielesarˆe,onajoutxfyosmmt`edcsaahucdnseeΓ(x)Γ(y). iiiraeneteˆojanuetuquhaaiepliretcanojtuteasosmmered)o´es. ivretire) onvet Γ(v). e e Linte´rˆetdessommetspliables,cestquesiontrouveunMISIdansG(qu’on suppose obtenu en pliant le sommetvdansGd´enntmeunreuiedsnadSIM),anoepolsriceltuafG: e i) siIcontient un sommetxfyproduit par le pliage (et il ne peut y en avoir qu’un seul car ils sont tous e reli´esentreeux),alorsI=I− {xfy} ∪ {x, y}est un MIS deG. e ii) sinonI=I∪ {v}est un MIS deG. Onpeutsereporter`a[1]pourunepreuvedecesassertions.Laconclusion,cestquonpeutdonc´eliminer syste´matiquementlessommetspliables,cequiaboutita`unediminutiondelatailledessous-proble`mes.
Sommets Miroirs.Unmiroird’un sommetvest un sommetustan`adiuxdecedev(c.a.d. un voisin d’un voisin) tel que Γ(v)Γ(uclique(´eventuelelemtnived.)nOonteenutse)M(v) l’ensemble des miroirs devedidecd´onsit,anlraptnemellemrofaser`reseni´tsasnneIp.evt´egnpeu,oesseedrmelactne sint´eresser`asesmiroirs.NousarmonseneetquelalgorithmesuivantcalculeunMISdeG: 1:functionMaxIndependentSet(G) 2:ifG=then return3:ChoisirvG´rp(ge´rmexamila)ef´erablementded 4:I1MaxIndependentSet(G− {v} −M(v)) 5:I2MaxIndependentSet(G− {v} −Γ(v)) 6:returnmax{I1, I2} 7:end function
2
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.