Chapitre 8 : Programmation dynamique

pages

Français

Documents

Lire un extrait

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

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

Français

Ebook

Lire un extrait

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

Publié par

pefav

Nombre de lectures

188

Langue

Français

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

Voir

Publié par

pefav

Nombre de lectures

188

Langue

Français

cours de cours

Chapitre

GraphesetRechercheOp´erationnelle– ESIAL

Programmation

J.-F. Scheid

2011–2012

dynamique

Plan du chapitre

I. II. III.

IV.

Introductionetprinciped’optimalite´deBellman Programmationdynamiquepourlaprogrammationline´aireen nombres entiers Probl`emesdecheminementdansungraphevalu´e 1Plus court cheminssape´→futur 2Plus court cheminfutur→apsse´ 3Remarques sur quelques algorithmes (Bellman, Dijkstra)

Probl`emeduvoyageurdecommerce

oudrr´espour954)nioshcmebpeddeseuruenglox(auimpt

Programmation dynamique:

I.Introductionetprinciped’optimalit´edeBellman

).nimuo.xameressanttpasint´amitnoydP.orrgmave´epplominaedquamll1∼(npee´eBra

C’estuneme´thodedeconstructiond’algorithmetre`sutilise´een optimisation combinatoire (→recherche de solution optimale dans ensembleﬁnide solutionsmndaratsrgi`se).

ti(elpciSP)Edimeum´e’´enonimratimenu’dtidedohte´ags’Iliaosnncenotsurtiblesdesolutionsmdettossee-sumesnnr:oieetountjererconavoislesssanitnoosulnisereatecttjereOns.ontiulosselsetuotsapequin’es-ensembla`nuossuitneentnsalearppntmeelsiilpxeticiurteset

hcednimetposuamilox(uengmauroux.eBllam(n1∼59)4opurr´esoudredespbnoitammauqimanydlove´eedarep´epprogrP

Ils’agitd’uneme´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-ensemblequin’estpasint´eressant.

I.Introductionetprinciped’optimalit´edeBellman

Programmation dynamique: C’estunem´ethodedeconstructiond’algorithmetr`esutilis´eeen optimisation combinatoire (→recherche de solution optimale dans un ensembleﬁnide solutionsndsiame`rtargs).

)n.mi

I. Introduction et principe d’optimalite de Bellman ´

Programmation dynamique: C’estuneme´thodedeconstructiond’algorithmetre`sutilise´een optimisation combinatoire (→recherche de solution optimale dans un ensembleﬁnide solutionsdnaaimr`stgres).

Ils’agitd’uneme´thoded’taoi´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-ensemblequin’estpasinte´ressant.