Licence informatique L3 Annee

Description

Niveau: Supérieur, Licence, Bac+3
Licence informatique - L3 Annee 2011/2012 Conception d'algorithmes et applications (LI325) COURS 6 Resume. Dans cette sixieme seance, nous continuons l'exploration des algorithmes de type Programmation Dynamique. Nous traiterons grace a ce principe un probleme de la theorie des graphes (recherche des plus courts chemins dans un graphe oriente sans circuit negatif) et un probleme d'ordonnancement (le probleme du sac a dos). 1. Programmation Dynamique en Algorithmique des Graphes 1.1. Plus courts chemins dans un graphe oriente value sans circuit negatif. On considere un graphe G = (X,A) ou X de cardinal n est l'ensemble de ses sommets et A l'ensemble de ses arcs. On se donne une application v de A dans Z, v(a) est appelee abusivement la longueur de l'arc a. Par extension, la longueur d'un chemin est egale a la somme des longueurs des arcs qui le composent. Le probleme consiste a determiner pour chaque couple de sommets (x, x?), la longueur d'un plus court chemin, s'il existe, qui joint x a x?. On notera cette valeur d(x, x?) avec comme convention que d(x, x?) = ∞ s'il n'existe pas de chemin entre x et x?). On peut de plus supposer qu'entre deux sommets il y a au plus un arc.

• solution optimal


• appel au principe de la programmation dynamique


• definition recursive des dk


• principe de la programmation dynamique


• court chemin


• optimalite de la solution imax

Informations

• Publié par: thieg
• Nombre de lectures: 31
• Langue: Français

Extrait

Licence informatique - L3

Anne´e2011/2012

Conception d’algorithmes et applications (LI325) COURS 6

R ´ esume ´ .’lxelprotnniousnalgorithationdesedsempyteetscanD`exisitecnae´semocsuon,e ProgrammationDynamique.Noustraiteronsgrˆace`aceprincipeunproble`medelathe´oriedes graphes(recherchedespluscourtscheminsdansungrapheorient´esanscircuitn´egatif)etun proble`med’ordonnancement(leprobl`emedusac`ados).

1.Programmation Dynamique en Algorithmique des Graphes 1.1.nssa´eluva´entieroehpargnusnadsnrtschemiPluscouit.fe´agiunticcr`erensidOnco un grapheG= (X, A`u)oXde cardinalnest l’ensemble de ses sommets etAl’ensemble de ses arcs. On se donne une applicationvdeAdansZ,v(altam)eenepats´lepbaeevisulongueurde l’arcadrueugnolal,noisga´estnemihenc’uxtenPare.elimmdeseolela`alosesarcsqungueursd 0 composent.Leprobl`emeconsiste`ade´terminerpourchaquecoupledesommets(x, x), la longueur 0 0 d’un plus court chemin, s’il existe, qui jointxa`x. On notera cette valeurd(x, x) avec comme 0 0 convention qued(x, x) =∞s’il n’existe pas de chemin entrexetx). On peut de plus supposer qu’entre deux sommets il y a au plus un arc. En effet, s’il en existe plusieurs, il suffit de ne retenir quelepluscourt(c’est-a`-direceluidelongueurminimale).Onprendragardedenepasselaisser perturberpardesnotationsetuneterminologiede´place´es.Eneffet,iln’yariendem´etriquedans ceprobl`eme.Cetteterminologieesthe´rite´eduproble`meo`uleslongueurssonttoutespositives. Dans ce cas,dse’C.emretudeuqiatemh´atsmenuseaancedistrslatalodesiatcntsibnenue g´eod´esique.

1.1.1.Sous-Structure optimale.sluspIltaescnocetnaeltnanreapropri´et´esuivsie´ederamqreulr 0 0 courts chemins reliantxa`x: SiCest un chemin de longueur minimale joignantxa`xqui passe parzntiaalimelernd’unchet´enatiouguemrniimdnlenoilrslo,aacnocaltiafnetsexa`zet d’un 0 chemin de longueur minimale reliantz`axltiate´’rne,sacecaa¸plemdeunl’nteccsehimsnicen.S parunchemindelongueurinfe´rieure,oncontrediraitlaminimalit´edeC. On utilise ici le fait qu’il n’yapasdecircuitdontlasommedesvaleursdesarcssoitne´gative(sinonladistanceentredeux 0 sommetsxetxitraseidfucricnu’tage´nti−∞sauttourucirourdenninaute´ednfitiisfaentiuc 0 et donc tout chemin reliantx`axee´nntemniunimal)pourrna(intoˆ´entcreesceoamsprli´meet chemindelongueurminimaleenluirajoutantuneinfinit´edetoursautourducircuit). Dans la suite, on noterax 1 , ..., x n les sommets deGet pour toutk >0 et tout cheminC, on noteraP k (Ceti´su´eap)lprroet:vina Tous les sommets deCirneusnqc,eaduitristemctitnee´fnueirrnt,o´eitemr´xtneosteenigironoseu a`k.

On peut remarquer qu’un cheminCeifi´vreP 1 (C) si et seulement s’il se compose d’un unique arc. D’autre part, la conditionP n+1 (C) est satisfaite par tous les cheminsCdu graphe. Notons d k (x i , x j ) la longueur du plus court cheminCfiie´vreqiuP k (C) et qui a pour originex i et pour extr´emite´x j . Par convention, cette valeur est∞li’setsixe’n.ecttpeorrp´itee´pasdecheminayant

1.1.2.´rnoruceevisruopUsonetilu.ncessiateddsclluelacOn va montrer qu’il y a une construction re´cursivepourlesd k (x i , x j ). Tout d’abord, on remarque que s’il y un arcareliantx i `ax j , on a d 1 (x i , x j ) =v(a) et sinond 1 (x i , x j ) =∞. D’autre part on a le lemme suivant : 1