Chapitre 8 : Programmation dynamique

Publié par

Graphes et Recherche Operationnelle – ESIAL 2A Chapitre 8 : Programmation dynamique J.-F. Scheid 2011–2012 1

  • resoudre des pb de chemins optimaux

  • principe d'optimalite de bellman

  • methode de construction d'algorithme tres

  • recherche de solution optimale


Publié le : mardi 19 juin 2012
Lecture(s) : 176
Tags :
Source : iecn.u-nancy.fr
Nombre de pages : 55
Voir plus Voir moins
Chapitre
GraphesetRechercheOp´erationnelle– ESIAL
8
:
Programmation
J.-F. Scheid
2011–2012
dynamique
2A
1
Plan du chapitre
I. II. III.
IV.
Introductionetprincipedoptimalite´deBellman Programmationdynamiquepourlaprogrammationline´aireen nombres entiers Probl`emesdecheminementdansungraphevalu´e 1Plus court cheminssape´futur 2Plus court cheminfuturapsse´ 3Remarques sur quelques algorithmes (Bellman, Dijkstra)
Probl`emeduvoyageurdecommerce
2
oudrr´espour954)nioshcmebpeddeseuruenglox(auimpt
Programmation dynamique:
I.Introductionetprincipedoptimalit´edeBellman
3
).nimuo.xameressanttpasint´amitnoydP.orrgmave´epplominaedquamll1(npee´eBra
un
Cestuneme´thodedeconstructiondalgorithmetre`sutilise´een optimisation combinatoire (recherche de solution optimale dans ensemblefinide solutionsmndaratsrgi`se).
ti(elpciSP)Edimeum´e´enonimratimenudtidedohte´agsIliaosnncenotsurtiblesdesolutionsmdettossee-sumesnnr:oieetountjererconavoislesssanitnoosulnisereatecttjereOns.ontiulosselsetuotsapequines-ensembla`nuossuitneentnsalearppntmeelsiilpxeticiurteset
hcednimetposuamilox(uengmauroux.eBllam(n159)4opurr´esoudredespbnoitammauqimanydlove´eedarep´epprogrP
Ilsagitduneme´thoded´erationimplicite´nemu(idem PSE) : on retient ou rejette des sous-ensembles de solutions mais on ne construit pas toutes les solutions. On rejette certaines solutions sans lesavoircontruitesexplicitementsiellesappartiennenta`un sous-ensemblequinestpasint´eressant.
I.Introductionetprincipedoptimalit´edeBellman
Programmation dynamique: Cestunem´ethodedeconstructiondalgorithmetr`esutilis´eeen optimisation combinatoire (recherche de solution optimale dans un ensemblefinide solutionsndsiame`rtargs).
3
)n.mi
I. Introduction et principe d’optimalite de Bellman ´
Programmation dynamique: Cestuneme´thodedeconstructiondalgorithmetre`sutilise´een optimisation combinatoire (recherche de solution optimale dans un ensemblefinide solutionsdnaaimr`stgres).
Ilsagitduneme´thodedtaoi´mreilicinpmte´enu(idem PSE) : on retient ou rejette des sous-ensembles de solutions mais on ne construit pas toutes les solutions. On rejette certaines solutions sans lesavoircontruitesexplicitementsiellesappartiennent`aun sous-ensemblequinestpasinte´ressant.
Programmationdynamiquede´veloppe´eparBellman(1954) pour re´soudredespbdecheminsoptimaux(longueurmax.oumin.)
3
eqs´ntuefadeon¸cilppe´uqcniraepiCepurlaespoerchrechehimdeceitamsnpooueflliesfdeitrnrselumrovisruce´.ux
D´emonstrationparlabsurde.
Principedoptimalit´edeBellman
4
Uncheminoptimalestforme´desous-cheminsoptimaux: Si (C) est cheminoptimalallant deAa`Bet siCppaitra(ane`tC) alors les sous-chemins de (C) allant deAa`Cet deC`aBsontoptimaux.
un
Principedoptimalite´deBellman Uncheminoptimalestforme´desous-cheminsoptimaux: Si (C) est un cheminoptimalallant deA`aBet siC(a`tarppentiaC) alors les sous-chemins de (C) allant deAa`Cet deC`aBsontoptimaux.
De´monstrationparlabsurde.
Ceprincipeappliqu´edefac¸onell´seuqeeitnfournit desformules recursives ´ pour la recherche de chemins optimaux.
4
x0
xe´
allant
de
quelconque
dans
` a
y
exemple
cherchele chemin graphevalu´e.
5
Un
plus
court
On un
le
zea`.yasllnadtescheminedetousllaminimrueugnolatlesy)z,L(`u)o(1y,))L+z((F)zni(zy)=mveF(ursir´ecy(Fetonnugnolal)iminrmeuouetedalhcmelssellnanias0`aytdexmule.ForO.
Un exemple. On cherchele chemin le plus court allant dex0x`a´eyquelconque dans phe val ´ un gra ue.
On noteF(y) la longueurminimalede tous les chemins allant dex0a`y.
Formulere´cursive
F(y) = min (F(z) +L(z,y)) z
(1)
ouL(z,y) est la longueurminimalede tous les chemins allant dez`ay. `
5
Demonstrationdelaformuler´ecursive(1) ´
.
Soit un pointzexnsdacnO.isnorgelehpanhemieuncd`erminimal(Cz) ´ allant dex0`ayet passant parzepicnirpelraP.lmel,anpodamit´tilBede le sous-chemin allant dex0a`zest minimal et a pour longueurF(z). De mˆeme,lesous-cheminallantdez`ayest minimal et a pour longueur L(z,y).
Donc la longueur du chemin (Cz) estF(z) +L(z,y). On conclut en prenant le minimum surzF(y) = minz(F(z) +L(z,y))
6
Laprogrammationdynamiqueapplique´eaunproble`medonne, ` ´ consiste a trouver unenr´eatioivecursmrluoforpue`lb.emd `
Enproce´dantensuite`aund´ecoupagee´tapepar´etape,onobtient formule de recurrence. ´
une
7
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.