Chapitre 8 : Programmation dynamique

Documents
55 pages
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

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


Sujets

Informations

Publié par
Nombre de visites sur la page 188
Langue Français
Signaler un problème
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