Programmation dynamique - Bienvenue à l'IRIF · 2015-10-31 · Programmation dynamique UFR d’Informatique 2015--2016 F. Laroussinie Programmation dynamique Diviser-pour-régner:

Programmation dynamique

UFR d’Informatique

2015--2016

F. Laroussinie

Programmation dynamiqueDiviser-pour-régner:

1) on décompose un problème en sous-problèmes pertinents (dont la taille est une fraction de celle de départ), 2) on résout les sous-problèmes, 3) on construit une solution pour le problème initial…

Approche “top-down”

Programmation dynamique 1) on résout des sous-problèmes et on stocke leurs solutions, 2) on voit quels sous-problèmes sont pertinents et 3) on les utilise pour construire une solution pour le problème initial…

Approche “bottom-up”

3 idées !

Exemple : la suite de FibonacciF0=0 F1=1 Fn+2 = Fn+1 + Fn

Def fibonaif(n) : if n==0 : return 0 elif n==1 : return 1 else: return fibonaif(n-1)+fibonaif(n-2)

“top-down”


Def fibocache(n) : if n==0 : return 0 elif n==1 : return 1 T = [None] * (n+1) T[0]=0 T[1]=1 return fibocacheAux(T,n)

Def fibocacheAux(T,n) : if T[n]==None :

T[n]=fibocacheAux(T,n-1)+fibocacheAux(T,n-2) return T[n]

toujours “top-down” (et beaucoup mieux !)


Def fibo(n) : T = [0]*(n+1) T[1]=1 for i = 2 … n : T[i] = T[i-1]+T[i-2] return T[n]

“bottom-up”

(2 idées sur les 3…)


Def fiboopt(n) : if n==0 : return 0 elif n==1 : return 1 a , b = 0 , 1 for i = 2 … n-1 : a , b = b , a+b return a+b

(évite le stockage des valeurs inutiles pour la suite)

Exemple : la plus grande sous-séquence croissante

Le problème: Input:Output: une plus longue sous-séquence croissante

sous-séquence = suite d’indices 1≤i1< i2< … < ik ≤ n

… croissante : si ai1 < ai2 < … < aik

Exemple: 5 2 8 6 3 6 9 7 x x x x

Au travail !


Le problème: Input:Output: une plus longue sous-séquence croissante

indice: Soit L[j] la longueur d’une sous-séquence croissante maximale terminant en j.

L[j] = 1 + max ({0} U { L[i] | i<j ^ ai < aj })

Longueur de la solution = max({L[i] | 1≤i≤n})

Exemple: 5 2 8 6 3 6 9 7


L[j]: 1 1 2 2 2 3 4 4

L[1]=1 5 2 8 6 3 6 9 7 L[2]=1 5 2 8 6 3 6 9 7 L[3]=2 5 2 8 6 3 6 9 7 L[4]=2 5 2 8 6 3 6 9 7 L[5]=2 5 2 8 6 3 6 9 7 L[6]=3 5 2 8 6 3 6 9 7 L[7]=4 5 2 8 6 3 6 9 7 L[8]=4 5 2 8 6 3 6 9 7

Les plus grandes sous-séquences croissantes

sont de taille 4.

Algorithme: 1) calcul des L[j] avec:

- mémorisation du L[-] max (et du jmax) - pour chaque L[j], on stocke dans Pred[j] un indice i tel que L[j]=1+L[i].

2) On retrouve les L[jmax] éléments d’une sous-séquence croissante maximale avec Pred[-]:

jmax, Pred[jmax], Pred[Pred[jmax]], …


L[j] = 1 + max ({0} U { L[i] | i<j ^ ai < aj })Complexité en O(n2)


Calcul de L[j]

MaJ de max et jmax

Construction d’une solution

def plssc(T) : |T|=n maxsofar , imax = 0 , 0 L, Pred = [0,…0], [0,…,0] taille → n for j = 0 … n-1 : aux = 0 iaux = None for i in 0 … j-1 : if (T[i] < T[j] and L[i]>aux) : aux = L[i] iaux = i L[j] =1 + aux Pred[j] = iaux if (L[j] > maxsofar) : maxsofar = L[j] jmax = j #Construction de la ss-seq trouvee: iaux = jmax res = [0…0] taille → maxsofar

i = maxsofar-1 while (iaux != None) : res[i] = iaux iaux = Pred[iaux]

i = i-1 return maxsofar, res


Calcul de L[j]

MaJ de max et jmax

Construction d’une solution

def plssc(T) : maxsofar , imax = 0 , 0 L, Pred = [0]*len(T), [0]*len(T) for j in range(len(T)) : aux = 0 iaux = None for i in range(j) : if (T[i] < T[j] and L[i]>aux) : aux = L[i] iaux = i L[j] = 1 + aux Pred[j] = iaux if (L[j] > maxsofar) : maxsofar = L[j] jmax = j #Construction de la ss-seq trouvee: iaux = jmax res = [0] * maxsofar

i = maxsofar-1 while (iaux != None) : res[i] = iaux iaux = Pred[iaux] i=i-1 return maxsofar, res

Python

Les problèmes de sac à dos


Taille du problème: les 2n+1 valeurs données

Le problème: Input: un poids maximal W ∈ N, un ensemble de n objets ayant chacun un poids Output: la valeur maximale pouvant être stockée dans le sac (sans dépasser sa capacité !).

On distingue des variantes… (et des cas particuliers): - avec répétitions : on peut prendre plusieurs fois le même objet. - sans répétition: chaque objet est pris au plus une fois. - …


Taille du problème: les 2n+1 valeurs données

Le problème: Input: un poids maximal W ∈ N, un ensemble de n objets ayant chacun un poids Output: la valeur maximale pouvant être stockée dans le sac (sans dépasser sa capacité !).

- Cas avec répétitions: “Integer knapsack” - Cas sans répétition: “Knapsack” - Cas “borné” - …

Les problèmes de décision associés sont NP-complets… (Voir le “Garey & Johnson”, page 247).

Problèmes connus et

difficiles !

sac à dos avec répétitionsLe problème: Input: un poids maximal W ∈ N, un ensemble de n sortes d’objets ayant un poids Output: la valeur maximale pouvant être stockée dans le sac (sans dépasser sa capacité !).

Exemple:O: 1 2 3 4 5

wi 2 1 5 6 7

vi 6 1 18 22 24W=12Essais: - O5+O3 -> poids 12, valeur 42 - 2 x O3 + O1 -> poids 12, valeur 42 - 2x O4 -> poids 12, valeur 44, - …

sac à dos avec répétitionsInput: Output: la valeur maximale pouvant être stockée dans le sac.

Au travail !soit K[w] la valeur maximale pouvant être stockée dans un sac de capacité w∈{0,1,2,…,W}

- solution au problème: K[W] - K[0]=0

Comment calculer K[w] ?

sac à dos avec répétitions

Calcul de K[w]… Si une solution optimale pour réaliser K[w] contient au moins un objet i, alors… 1) sans cette occurrence de l’objet i, le contenu du sac

est optimal pour le poids w-wi, et 2) sa valeur est alors K[w-wi] !

K[w] = max ({0} U {K[w-wi]+vi | wi ≤ w})

sac à dos avec répétitionsDefinition:

K[w] = max ({0} U {K[w-wi]+vi | wi ≤ w})

Propriété: K[w] est la valeur maximale pouvant être stockée dans un sac de capacité w∈{0,1,2,…,W}

sac à dos avec répétitionsDefinition: K[w] = max ({0} U {K[w-wi]+vi | wi ≤ w})Propriété: K[w] est la valeur maximale d’un sac de capacité w∈{0,1,2,…,W}Preuve:par induction sur w.

Si K[w]=0 : Alors il n’existe pas d’objet de poids ≤w, donc la valeur maximale d’un sac de capacité w est 0.

Si K[w]>0 : Prenons un sac S optimal pour w. Supposons que ce sac contienne les objets I={i1, i2,…, ik}. Soit i un de ces i. La valeur de S est donc: vi + Σ vj Et le poids de S sans l’ojet i, est Σ wj et sa valeur est Σ vj

On a bien K[w-wi] = Σ vj car sinon S ne serait pas optimal !

j∈ I\{i}

j∈ I\{i}

j∈ I\{i}

j∈ I\{i}

≤ w-wi


def SaDrepet(W,T) : K = [None, … None] // taille → W+1 K[0] = 0 for w = 1 … W : M = 0 for (wi,vi) in T : if wi <= w : M = max(M,K[w-wi]+vi) K[w]=M

return K[W],K


def SaDrepet(W,T) : K = [None] * (W+1) K[0] = 0 for w in range(1,W+1) : M = 0 for (wi,vi) in T : if wi <= w : M = max(M,K[w-wi]+vi) K[w]=M return K[W],K

Python


O: 1 2 3 4 5wi 2 1 5 6 7

vi 6 1 18 22 24

0 1 6 7 12 18 22 24 28 30 36 40 44

0 1 2 3 4 5 6 7 8 9 10 11 12

K[-]

Exemple


return K[W],K

sac à dos avec répétitions complexité

Complexité en Θ(W.n)


return K[W],K

Instance:- une liste T d’objets

de taille n, - un entier W.

sac à dos avec répétitions complexité

On suppose que les 2n+1 valeurs sont codées en binaire. La taille d’une instance du problème du sac à dos est donc:

t = ∑ log(wi+1) + ∑ log(vi+1) + log(W+1)i i

Une complexité en Θ(W.n) est donc en Θ(2t).

wi,vi,W>0

sac à dos avec répétitionsConstruire une solution à partir de K[-]:

Complexité en O(W.n)

une solution S[-] est un tableau d’entiers tq:

∑S[i].vi = K[W] et ∑S[i].wi ≤ W

def SolSaDrepet(W,K,T) : n = |T| S = [0, … ,0] taille → n v = K[W] w = W while v>0 : for j = 0 … n-1 : (wj,vj) = T[j] if (wj <= w) and (v-vj == K[w-wj]) : S[j] += 1 v -= vj w -= wj return S

sac à dos avec répétitionsConstruire une solution à partir de K[-]:

def SolSaDrepet(W,K,T) : n = len(T) S = [0]*n v = K[W] w = W while v>0 : for j in range(n) : (wj,vj) = T[j] if (wj <= w) and (v-vj == K[w-wj]) : S[j] += 1 v -= vj w -= wj return S

Python

sac à dos sans répétition


L’idée utilisée précédemment ne marche pas car les problèmes ne sont plus indépendants: le contenu du sac optimal pour le poids w sans l’objet i n’est pas forcément optimal pour le poids w-wi !

Exemple: W=10 et O: 1 2 3wi 5 5 6vi 20 2 3

K[10] = 22 (objet 1 + objet 2) K[5] = 20 (objet 1)

Calculer K[w] ?

Chaque objet est pris au plus une fois. Le problème: n objets, une capacité W…

Donc (objet 1+objet 2)\ objet 1 n’est pas optimal pour 10-w1 !

valeur=2 !

sac à dos sans répétitionIl faut affiner les calculs pour tenir compte des éléments potentiellement présents dans le sac (et qui ne peuvent pas être pris une seconde fois !).

Soit K[j,w] la valeur maximale que l’on peut stocker dans un sac de capacité w avec des objets 1,…,j.

K[j,w] = max (K[j-1,w], K[j-1,w-wj]+vj)K[0,w] = 0 et K[j,0]=0

Solution = K[n,W] : tous les objets sont autorisés et le poids max est W !

sac à dos sans répétitionAlgorithme de calcul des K[j,w]:

K[0,w]=0 ∀ w=0,…,W K[j,0]=0 ∀ j=0,…,n Pour j=1,…,n : Pour w = 1,…,W : Si w≤wj : K[j,w]=K[j-1,w] Sinon: K[j,w] = max(K[j-1,w],K[j-1,w-wj]+vj) Retourner K[n,W]

Complexité en O(W.n) Mémoire en O(W.n)

(NB: on peut aussi calculer par colonnes…)

sac à dos sans répétitionO: 1 2 3 4 5wi 1 2 5 6 7

vi 1 6 18 22 24

Exemple:

W=12

Ou :

def SaDsansrepet2(W,T) :

n = len(T)

Tab = [ ]

K = [0 for i in range(W+1)]

Tab.append(K[:])

for (wj,vj) in T :

for w in range(wj,W+1) :

K[w] = max(Tab[-1][w],Tab[-1][w-wj]+vj)

Tab.append(K[:])

return K[W],Tab

Remarque sur le programme Python : on recopie systematiquement les lignes precedentespour recuperer les valeurs des cas ou w < wj . . .

Exemple : On prend W = 12 et (toujours) le tableau suivant :

w 1 2 5 6 7

v 1 6 18 22 24

Et on construit le tableau K suivant :

j\w 0 1 2 3 4 5 6 7 8 9 10 11 12

0 0 0 0 0 0 0 0 0 0 0 0 0 01 0 1 1 1 1 1 1 1 1 1 1 1 12 0 1 6 7 7 7 7 7 7 7 7 7 73 0 1 6 7 7 18 19 24 25 25 25 25 254 0 1 6 7 7 18 22 24 28 29 29 40 415 0 1 6 7 7 18 22 24 28 30 31 40 42

Dans le tableau, on a illustre le calcul de deux valeurs (le 18 de la ligne n = 3, et le 30 de laderniere ligne) en mettant en gras les valeurs utilisees pour leurs calculs.

On retrouve les solutions avec :

def SolSaDsansrepet(W,Tab,T) :

n = len(T)

S = [False for i in range(n)]

v = Tab[n][W]

w = W

for j in reversed(range(n)) :

(wj,vj) = T[j]

if (wj <= w) and (v-vj == Tab[j][w-wj]) :

S[j] = True

v -= vj

w -= wj

return S

19

+v5 (=24) Solution=42 !


def SaDsansrepet(W,T) : n = len(T) Tab = [ ] K = [0] * (W+1) Tab.append(K[:]) for j in range(n) : (wj,vj) = T[j] for w in range(wj,W+1) : K[w] = max(Tab[-1][w],Tab[-1][w-wj]+vj) Tab.append(K[:]) return K[W],Tab

Python

ajout d’une copie de K à Tab

sac à dos sans répétitionRetrouver la solution (ie la composition du sac !) à partir de K[-,-] ?

def SolSaDsansrepet(W,Tab,T) : n = len(T) S = [False] * n v = Tab[n][W] w = W for j in reversed(range(n)) : (wj,vj) = T[j] if (wj <= w) and (v-vj == Tab[j][w-wj]) : S[j] = True v = v-vj w = w-wj

return S


idée: Améliorer l’algorithme… en économisant de la mémoire…

sac à dos sans répétition0 1 w-wj w W

0

1

j-1

j K[j,w]

n

+vj

K[j,w] ne dépend que de la ligne K[j-1,-] !

� Construction du tableau: Pour w=W à 1:

K[w] = max(K[w],vj+K[w-wj])


K=[0,0,…,0] (taille W) Pour j=1,…,n : Pour w = W,…,1 : Si wj≤w :

K[w] = max(K[w] , K[w-wj]+vj) Retourner K[W]

Complexité en O(W.n) Mémoire: O(W)

sac à dos sans répétitiondef SaDsansrepet3(W,T) : n = len(T) K = [0] * (W+1) for j in range(n) : wj = T[j][0] vj = T[j][1] for w in range(W,wj-1,-1) : K[w] = max(K[w],K[w-wj]+vj)

return K[W]

Complexité en O(W.n) Mémoire: O(W)

Python

sac à dos avec répétitionle retour !

On peut aussi passer par un K[j,w]…

K[j,w] = max (K[j-1,w], K[j,w-wj]+vj)K[0,w] = 0 et K[j,0]=0

sac à dos avec répétition0 1 w-wj w W

0

1

j-1

j K[j,w]

n

+vj

� Construction du tableau: Pour w=1 à W:

K[w] = max(K[w],vj+K[w-wj])

les problèmes de sac à dosQuelques cas particuliers:

- sac à dos sans répétition et tel que vi=wi ∀i.

- sac à dos (avec ou sans répétition) avec vi=1 ∀i.

- sac à dos (avec ou sans répétition) avec des objets fractionnables.

- …

Difficile… ~“subset-sum problem”

Facile… maximiser le nb d’objets

Facile…

voir la partie “algorithmes gloutons”

Programmation dynamiqueUn algorithme de programmation dynamique n’est pas toujours possible.

Il faut que le problème à résoudre vérifie une propriété de “sous-structure optimale”:

Il faut qu’une solution optimale pour un problème contienne aussi des solutions optimales pour ses sous-problèmes.

Exemple: le sac à dos sans répétition avec K[j,w] ! (et K[j-1,w] et K[j-1,w-wi] ).

Rendre la monnaie

Autre problème…

Rendre la monnaie Input: Output: une manière de réaliser S avec les pièces de manière à avoir un nombre minimal de pièces.

Exemple: on veut constituer la somme 534€ à partir de billets(*) de 50€, de 20€, de 10€, de 5€ et de pièces de 2€ et 1€.

(*) oui, ça marche aussi avec les billets… !

➤ 10 x 50€ + 1x20€ + 1x10€ + 2x2€

Exemple: Constituer 8€ avec des pièces de 1€, de 4€ et de 6€.

Rendre la monnaie

➤ 2x4€ : 2 pièces.NB: et pas 6€ + 2x1€ … 3 pièces !

Exemple: le système monétaire de la Livre Sterling avant1971: 1 £ = 20 shilling 1 shilling = 12 pences + pièces de 1/4 de shilling (”3 pence”) + pièces de 1/3 de shilling (“4 pence” ou “groat”) + pièces de 1/2 shilling

Comment faire 8 pence ? ➤ 2x1 “groat”.

Rendre la monnaie

Comment faire ?

Input: Output: une manière de réaliser S avec les pièces de manière à avoir un nombre minimal de pièces.

☞ hypothèse importante : on dispose d’autant de pièces que nécessaire pour chaque sorte de pièces…

Rendre la monnaie Soit T[i,s] le nombre minimal de pièces de valeurs p1,…,pi pour constituer la somme s.

T[i,0]= T[0,s]=

0 ∀i ∞ ∀s

T[i,s] = min (T[i-1,s] , 1+T[i,s-pi]) si s≥pi T[i-1,s] sinon {

sans autre pi avec un autre pi

Rendre la monnaie Exemple: Constituer 8 avec des pièces de 1, de 4 et de 6.

i\s 0 1 2 3 4 5 6 7 8

0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

1 0 1 2 3 4 5 6 7 8

2 0 1 2 3 1 2 3 4 2

3 0 1 2 3 1 2 1 2 2

3x1 1x41x6+1x1

p1=1p2=4p3=6

Rendre la monnaie

Algorithme:

T[1…n,1…S] : tableau d’entiers Pour i=1…n :

Pour s=1…S : Si i=1 ^ s<pi Alors : T[i,s] = ∞ Si i=1 ^ s≥pi Alors : T[i,s] = 1 + T[1,s-p1] Si i>1 ^s<pi Alors : T[i,s] = T[i-1,s] Sinon : T[i,s] = min ( T[i-1,s] , 1+T[i,s-pi] )

Complexité: O(n.S)

Rendre la monnaie

Reconstituer un ensemble solution ?

Idée: ◆si T[i,s]=T[i-1,s] alors pi n’est pas (ou plus) utile ici et la solution est la même que pour T[i-1,s]; ◆si T[i,s]=1+T[i,s-pi] alors il faut ajouter une pièce pi à la solution de T[i,s-pi].

(et si T[i-1,s]=1+T[i,s-pi] alors les deux choix sont optimaux !)

Complexité: O(n+T[n,S])

Calcul des plus courts chemins dans un graphe

Autre problème…

Algorithmes dans les graphesBeaucoup de problèmes différents !

Dans cet exposé: 2 problèmes… et 4 algorithmes ! Trouver un chemin optimal

Comment aller de Chevaleret a Porte de Bagnolet ?

Funiculaire deMontmartre

Orlyvaltarificationspéciale

Stade de FranceSt-Denis

St-Denis–Porte de Paris

Basiliquede St-Denis

Portede St-Ouen

LamarckCaulaincourt

JulesJoffrinGuy

Môquet

Portede Clichy

ChâteletLes Halles

Stalingrad

MarcadetPoissonniers

Hôtel de Ville

Arts etMétiers

Château Rouge

StrasbourgSt-Denis

St-Mandé

Hoche

MarxDormoy

La CourneuveAubervilliers

Le Bourget

Jaurès

Placedes Fêtes

Belleville Jourdain Télégraphe

Ourcq Portede Pantin

JacquesBonsergent Saint-Fargeau

PelleportPorte

de Bagnolet

Danube

BotzarisButtes

Chaumont

République

Parmentier

SèvresBabylone

RichelieuDrouot

Palais RoyalMusée du

Louvre

RéaumurSébastopol

Raspail

Pyramides

MontparnasseBienvenüe

Mabillon

ClunyLa Sorbonne

MalakoffRue Étienne Dolet

Chaussée d’AntinLa Fayette

BonneNouvelle

GrandsBoulevards

Bourse Sentier

BarbèsRochechouart

LaChapelle

Pigalle

PoissonnièreLiège

Notre-Damede-Lorette

St-Georges

Abbesses

Anvers

La Fourche

Placede Clichy

Pereire–Levallois Blanche

Villiers

OpéraAuber

HavreCaumartin

Trinitéd’Estienne

d'Orves

FranklinD. Roosevelt

Neuilly–Porte Maillot

Avenue Foch

Bir-Hakeim

Invalides

Pasteur

Pontde l’Alma

JavelAndréCitroën

Javel

Michel-AngeMolitor

La Muette

Michel-AngeAuteuil

Boulainvilliers Champ de MarsTour Eiffel

ChampsÉlysées

ClemenceauTrocadéro

AvenueHenri

Martin

Avenue duPdt Kennedy

Commerce

Félix Faure

Ruede la Pompe Iéna

Ranelagh

Jasmin

Exelmans

ChardonLagache

Églised’Auteuil

Duroc

La MottePicquetGrenelle

Assemblée Nationale

Varenne

St-MichelNotre-DameSolférino

Musée d’Orsay

Concorde Les Halles

Jussieu

Odéon

Étienne Marcel

Vavin

St-Germaindes-Prés

St-Sulpice

St-PlacidePlace Monge

Pont NeufTuileries

Notre-Damedes-Champs

Luxembourg

Port-Royal

LouvreRivoli

St-Michel

Bastille

Daumesnil

Reuilly–Diderot

PèreLachaise

Oberkampf

Quai dela Rapée

SaintMarcel Bercy

Fillesdu Calvaire

Chemin Vert

St-SébastienFroissart

Ruedes Boulets

Charonne

SèvresLecourbe

Cambronne

PontMarie

SullyMorland

PhilippeAuguste

AlexandreDumas

Avron

Voltaire

Quatre Septembre

St-Ambroise

RueSt-Maur

Pte deVincennes

Maraîchers Portede Montreuil

Robespierre

Croix de Chavaux

Buzenval

Pyrénées

Laumière

Châteaud’Eau

Porte Dorée

Porte de Charenton

Ivrysur-Seine

Portede Choisy

Ported’Italie Porte d’Ivry

Olympiades

Créteil–UniversitéCréteil–L’Échat

Maisons-AlfortLes Juilliottes

Maisons-Alfort–Stade

DenfertRochereau

MaisonBlanche

CensierDaubenton

Tolbiac

Le KremlinBicêtre Villejuif

Léo LagrangeVillejuifPaul Vaillant-Couturier

GlacièreCorvisart

NationaleChevaleret

CitéUniversitaire

Gentilly

Antony

MalakoffPlateau de Vanves

MoutonDuvernet

Gaîté

EdgarQuinet

Bd Victor

Issy

Portede St-Cloud

Pantin

Magenta

Vitrysur-Seine

Saint-Ouen

Ledru-Rollin

Ménilmontant

Couronnes

ColonelFabien

Montgallet

Michel Bizot

Charenton–Écoles

Liberté

FaidherbeChaligny

École Vétérinairede Maisons-Alfort

St-Paul

MaubertMutualité

CardinalLemoine

Temple

ChâteauLandon

Bolivar

Église de Pantin

Bobigny–PantinR. Queneau

RiquetCrimée

Corentin CariouPorte de la Villette

Aubervilliers–PantinQuatre Chemins

Fortd’Aubervilliers

LesGobelins Campo

FormioQuai

de la GareCour

St-Émilion

Pierre et Marie Curie

Dugommier

Bel-AirPicpus

St-Jacques

Dupleix

Passy

Alésia

Pernety

Plaisance

Pte de Vanves

Convention

Vaugirard

Porte de Versailles

Corentin Celton

Volontaires

Falguière

Lourmel

Boucicaut

Ségur

Ruedu Bac

Rennes

SaintFrançoisXavier

Vaneau

ÉcoleMilitaire

La Tour Maubourg

AvenueÉmile Zola

CharlesMichelsMirabeau

Ported’Auteuil

BoulogneJean Jaurès

Billancourt

MarcelSembat

Cité

AlmaMarceau

Boissière

KléberGeorge V

Argentine

Victor Hugo

Les SablonsPorte Maillot

Pont de Neuilly

Esplanadede La Défense

St-Philippedu-Roule

MiromesnilSt-Augustin

Courcelles

Ternes

Monceau

RomeMalesherbesWagram

Porte de Champerret

Anatole FranceLouise Michel

Europe

Le PeletierCadet

Pereire

Brochant

Mairiede Clichy

Garibaldi

Mairiede St-Ouen

CarrefourPleyel

Simplon

Bérault

RichardLenoir

Goncourt

BréguetSabin

Rambuteau

La PlaineStade de France

Madeleine

Gabriel Péri

BibliothèqueFr. Mitterrand

Les Agnettes

Portede Clignancourt

Garede l’Est

Garede Lyon

St-Denis–Université

Portede la Chapelle

La Courneuve8 Mai 1945

BobignyPablo Picasso

PréSt-Gervais

Mairiedes Lilas

Mairiede Montreuil

Gallieni

LouisBlanc

Portedes Lilas

Gambetta

Gare du Nord

Charlesde Gaulle

Étoile

Pont de LevalloisBécon

PorteDauphine

La Défense

BoulognePont de St-Cloud

Châtelet

Gared’Austerlitz

Nation

Châteaude Vincennes

Créteil–Préfecture

Mairie d’Ivry

Placed’Italie

VillejuifLouis Aragon

Mairie d’Issy

Châtillon–Montrouge

Pontde Sèvres

IssyVal de Seine

Gare St-Lazare

GareMontparnasse

HaussmannSt-Lazare

Ported’Orléans

Balard

Pontdu Garigliano

St-Lazare

Asnières–GennevilliersLes Courtilles CDG

Grande Arche

Orly

Paris

www.ratp.fr

MR

Prop

riété

de

la R

ATP

- Age

nce

Cart

ogra

phiq

ue -

PMI 0

4-20

08- B

O D

esig

n: b

dcco

nsei

l - R

epro

duct

ion

inte

rdite

Comment sortir ?

novembre 29, 2010_1.pdf - Page 3

Les graphes

G = (S ,A)S est un ensemble fini de sommets.On va considerer des graphes orientes ou non-orientes :

q0 q1 q2

q3 q4 q5

q6

Plus courts cheminsDe quoi parle-ton ? Un graphe orienté valué G=(S,A,w) avec w:A➝R : La longueur d’un chemin est la somme du poids de ses transitions. : Un plus court chemin (PCC) entre s et u est un chemin s ➝* u de longueur minimale. Obj: trouver des PCC et/ou les longueurs des PCC.

Problèmes autour des PCC:1) trouver les PCC depuis une origine unique s. 2) trouver les PCC pour toutes les paires de sommets

de G.

q1

q2c

Plus courts chemins dans un graphe

2

5

-3

1

34

2-13

2

q2q1 q3

q4 q5 q6

Entre q1 et q3 ?

Entre q1 et q2 ?

1

Entre q1 et q5 ?

2

-4

Algorithme de Floyd-Warshallobj: trouver les PCC pour toutes les paires de sommets de G.

Données: G=(S,A,w) avec w:A➝R sans cycle négatif sous forme matricielle.

Résultat: Une matrice (!ij) où le coefficient !ij est la longueur d’un PCC entre xi et xj.

Représentation matricielle de G=(S,A,w)

Le probleme

Objectif : calculer les PCC entre tous les sommets. . .

On suppose que G = (S ,A,w) est donne sous forme matricielle :(MG ,w)

• S = {x1, . . . xn}

• w : A → R

• MG = (αij)1≤i ,j≤n : αij decrit l’arc entre xi et xj .

αijdef=

⎧

⎪

⎨

⎪

⎩

0 si i = j

w(xi , xj ) si i = j et (xi , xj) ∈ A

∞ si i = j et (xi , xj) ∈ A

Dans la suite, on notera δij la distance δ(xi , xj ) d’un PCC entre xiet xj .

S={x1,…xn}

Représentation matricielle de G=(S,A,w)Exemple

q0 q1 q2

q3 q4 q5

q6

2

7

4

4

4 3

31 8

5

⎛

⎜

⎜

⎜

⎜

⎜

⎜

⎜

⎜

⎝

0 2 ∞ 4 ∞ ∞ ∞∞ 0 ∞ 3 7 ∞ ∞∞ ∞ 0 ∞ ∞ 8 ∞∞ ∞ ∞ 0 4 ∞ 4∞ ∞ 1 ∞ 0 5 3∞ ∞ ∞ ∞ ∞ 0 ∞∞ ∞ ∞ ∞ ∞ ∞ 0

⎞

⎟

⎟

⎟

⎟

⎟

⎟

⎟

⎟

⎠

Algorithme de Floyd-WarshallQuestion: Comment calculer la matrice (!ij) ?

On va calculer une famille de matrices D(k) pour 0≤k≤n Le coefficient d(k)ij sera égal à la distance d’un PCC entre xi et xj ne passant que par des états dans {x1,…xk}.

d(k)ij = min(d(k-1)ij , d(k-1)ik + d(k-1)kj) k>0d(0)ij ="ij

� algorithme de programmation dynamique

Comment ?

Algorithme de Floyd-WarshallLa preuve de correction se fait par induction sur k.

Hyp: G sans cycle négatif !

Prop: Si G a un cycle négatif, il existe un coefficient de la diagonale de D(n) qui est <0…

d(k)ij = min(d(k-1)ij , d(k-1)ik + d(k-1)kj) k>0

Algorithme simplifie

Procedure PCC-Floyd(G )//On initialise D avec M:

pour i = 1 . . . n faire

pour j = 1 . . . n fairedij := αij

si αij = ∞ alors πij := i

pour k = 1 . . . n faire

pour i = 1 . . . n faire

pour j = 1 . . . n faire

si dij > dik + dkj alorsdij := dik + dkjπij := πkj

return D,Π

Algorithme de Floyd-Warshall

Complexité en O(n3)

� Comme pour le sac à dos, on peut utiliser une seule matrice d (au lieu de n).

Documents

Programmation dynamique - Bienvenue à l'IRIF · 2015-10-31 · Programmation dynamique UFR d’Informatique 2015--2016 F. Laroussinie Programmation dynamique Diviser-pour-régner: