TD - Programmation dynamique
Optimisation et Recherche Operationnelle
M1 Info - semestre d’automne 2020-2021
Université Claude Bernard Lyon 1
Christophe Crespelle Eric Duchêne Aline Parreau
[Link]@[Link] [Link]@[Link] [Link]@[Link]
Exercice 1. Sur l’autoroute du profit
Vous implentez une chaine de restaurants sur les aires de repos d’une section d’autoroute.
Les aires sont numerotees de 1 a n dans l’ordre dans lequel on les rencontre sur l’autoroute.
Pour chaque aire i, on connait :
— sa position xi , exprimee en km depuis le debut de la section autoroutiere 0 < x1 <
x2 < · · · < xn , et
— le revenu espere ri > 0 en placant un de vos restaurants dans cette aire, qui depend
de la frequentation de l’aire.
Les xi et les ri sont donnes dans deux tableaux separes indexes par i. La societe qui
gere l’autoroute, l’AFN (Autoroutes de France et de Navarre), impose une contrainte sur
l’implentation des restaurants : deux restaurants de la meme chaine (y compris la votre)
doivent etre espaces d’au moins 50km. On veut faire un algorithme qui retourne un
placement de vos restaurants qui ait un revenu escompte maximum, note OP T , compte
tenu de la contrainte imposee par l’AFN.
a. On note p(i) le numero de l’aire la plus proche de i qui est situee avant i (xp(i) < xi )
et a au moins 50 km de l’aire i. Donnez un algorithme de complexite O(n) qui calcule
p(i) pour tout i ∈ J1, nK. On prendra pour convention p(i) = 0 lorsqu’il n’existe pas
d’aire a au moins 50km de i avant i.
Solution.
Algorithme 1 : Algorithme pour le calcul de p(i), 1 ≤ i ≤ n.
1 p ← 0;
2 pour i de 1 a n faire
3 tant que x[i] − x[p + 1] ≥ 50 faire
4 p ← p + 1;
5 p[i] ← p;
Au cours de l’algorithme la valeur pretendante a etre p[i] est stockee dans p. Cette
valeur est initialisee a 0 (ligne 1) qui est la valeur par convention lorsqu’aucun site
ne se trouve a au moins 50km avant le site i courant. Ensuite, la boucle "pour" sur
i (ligne 2) considere chacun des sites un par un. Pour chacun d’eux, la boucle "tant
que" de la ligne 3 cherche le plus grand p (en l’incrementant a la ligne 4) tel que le
site numero p se trouve au moins 50km avant le site i (condition d’arret de la boucle
"tant que", ligne 3). Lorsque cette valeur de p est atteinte elle est affectee a p[i] a la
ligne 5.
La complexite de l’algorithme est bien O(n) car la boucle "pour" de la ligne 2 s’exe-
cute exactement n fois et le nombre total d’iterations de la boucle interne "tant que"
(ligne 3) au cours de l’algorithme n’excede pas n, car p augmente de 1 a chaque ite-
ration de la boucle. Pour etre rigoureux, remarquez aussi que le nombre de fois ou
le test de la condition de la boucle "tant que" est negatif, qui ne compte pas dans
les iterations de la boucle, est aussi exactement n : une fois pour chaque valeur de
i. Toutes les autres instructions sont elementaires et prennent un temps constant. La
complexite totale de l’algorithme est donc O(n).
b. Si on decide de placer un restaurant sur l’aire i, sur quelles aires j avant i, c.a.d.
j < i, peut-on eventuellement placer un autre restaurant ?
Solution. Precisemment sur les aires numero j avec j ≤ p(i) car ce sont les aires se
trouvant avant i et a au moins 50km de i. C’est la raison pour laquelle p(i) a ete defini
ainsi.
On s’interesse maintenant au sous-probleme Restau(j) dans lequel on ne place des res-
taurants que sur les aires i ∈ J1, jK, pour un j ∈ J1, nK fixe, et on note OP T (j) le revenu
maximum qu’on peut atteindre dans ce sous probleme (on etend cette notation en posant
par convention OP T (0) = 0).
c. Soit Sj∗ une solution de revenu maximum au sous-probleme Restau(j) telle que
j 6∈ Sj∗ . Exprimez le revenu r(Sj∗ ) de cette solution en fonction des OP T (j 0 ) pour
j 0 < j.
Solution. Puisque j n’est pas dans la solution optimale Sj∗ au probleme Restau(j),
alors cette solution n’utilise que des sites j 0 ≤ j −1 (remarquez que lorsque j 6∈ Sj∗ alors
necessairement j > 1). Ainsi, Sj∗ est aussi une solution au probleme Restau(j − 1). Et
comme Sj∗ est la solution optimale de Restau(j) alors c’est aussi la solution optimale
de Restau(j − 1) : r(Sj∗ ) = OP T (j − 1).
d. Meme question lorsque j ∈ Sj∗ .
Solution. Lorsque j ∈ Sj∗ , les autres sites j 0 impliques dans Sj∗ , c’est a dire j 0 ∈ Sj∗ et
j 0 6= j, verifient necessairement j 0 ≤ p(j), car Sj∗ satisfait les contraintes de distancia-
tion imposees par l’AFN. Ainsi, comme Sj∗ est la solution optimale a Restau(j), les
sites j 0 ∈ Sj∗ avec j 0 6= j forment une solution optimale a Restau(p(j)). On a donc
r(Sj∗ ) = rj + OP T (p(j)).
e. Donnez une formule de recurrence qui exprime OP T (j) en fonction des OP T (j 0 ), j 0 <
j.
Solution. Comme toute solution optimale a restau(j) contient ou ne contient pas
j, d’apres les deux questions precedentes, on a OP T (j) = max{OP T (j − 1), rj +
OP T (p(j))}.
f. Donnez un algorithme de complexite O(n) pour calculer OP T , le revenu escompte
maximum, et un placement de vos restaurants correspondant.
Solution.
Pour calculer OP T , l’algorithme 2 suit une approche de programmation dynamique
dans laquelle on calcule OP T [j] pour tout 0 ≤ j ≤ n, en posant comme convenu
OP T [0] = 0 et en utilisant le tableau p calcule a la question a. A la fin de l’algorithme,
on obtient alors la valeur de OP T comme OP T = OP T [n].
Le calcul des OP T [j], 1 ≤ j ≤ n, se fait dans la boucle "pour" de la ligne 2 en utilisant
la formule de recurrence de la question e (disjonction de cas des lignes 3 a 8). Afin
d’obtenir non seulement la valeur de OP T mais egalement une solution qui realise
cette valeur, on utilise un tableau prem qui pour chaque valeur de j ≥ 1 donne le site
de plus grand indice utilise dans la solution de valeur optimale OP T [j] au probleme
intermediaire restau(j). Grace au tableau prem, a la fin de l’algorithme (ligne 10 a 14),
on peut construire une solution optimale en remarquant que si le site xi est utilise dans
la solution optimale que l’on construit, alors le prochain site xj , avec j < i, utilise dans
cette solution est celui d’indice j = prem[p[i]], car lorsque xi participe a la solution
optimale a restau(i) (ligne 8), cette derniere est construite en prenant le site xi et
une solution optimale a restau(p[i]) (ligne 7). Dans l’algorithme, les listes sont notees
entre parentheses et le . designe la concatenation de deux listes. Dans la liste S que
l’on construit, les sites apparaissent dans l’ordre decroissant de leurs indices.
Algorithme 2 : Algorithme pour le calcul de OP T et d’une solution S realisant un
revenu escompte de OP T .
1 OP T [0] ← 0;
2 pour j de 1 a n faire
3 si OP T [j − 1] ≥ r[j] + OP T [p[j]] alors
4 OP T [j] ← OP T [j − 1];
5 prem[j] ← prem[j − 1];
6 sinon
7 OP T [j] ← r[j] + OP T [p[j]];
8 prem[j] ← j;
9 OP T ← OP T [n];
10 k ← prem[n];
11 S ← (k);
12 tant que p[k] > 0 faire
13 k ← prem[p[k]];
14 S ← S.(k);
15 retourner (OP T, S);
Il est aise de verifier que la complexite de l’algorithme 2 est O(n). Toute les instructions
sont elementaires et prennent un temps constant, y compris la concatenation de deux
listes ligne 14 avec une structure de donnee adequate (dans laquelle les listes sont
representees avec un pointeur sur leur premier et sur leur dernier element). La boucle
"pour" de la ligne 2 s’execute exactement n fois et la boucle "tant que" de la ligne 12
au plus n fois, car comme p[k] < k pour tout k, p[k] decroit strictement (ligne 13) a
chaque iteration de la boucle.
Exercice 2. Un sac de valeur
Dans le probleme du sac a dos, on donne une collection d’objets numerotes de 1 a n et
chaque objet a une valeur vi ∈ R+ et un poids wi ∈ R+ , pour i ∈ J1, nK. Le probleme
est a valeurs entieres si de plus les valeurs vi sont des entiers,
P c.a.d. ∀i ∈ J1, nK, vi ∈ N.
Pour une collection d’objets S ⊆ J1, nK, on note v(S) = vi la valeur de la collection S
P i∈S
et w(S) = wi son poids (avec par convention v(∅) = 0 et w(∅) = 0). On donne aussi
i∈S
un poids limite W ≥ 0 pour le sac a dos et on demande la valeur maximum OP T d’une
collection d’objets S telle que w(S) ≤ W . En clair, on veut maximiser la valeur de ce que
l’on prend en ayant une limite ferme sur le poids total. Ce probleme est un grand classique
de l’optimisation combinatoire, utilise pour modeliser de nombreux problemes pratiques.
Il est NP-difficile et on se propose de faire un algorithme pseudopolynomial pour le
resoudre de maniere exacte, en utilisant l’approche de la programmation dynamique. Cet
algorithme a une complexite theorique exponentielle mais est tres efficace en pratique
lorsque les valeurs entieres restent relativement petites (c’est a dire du meme ordre de
grandeur que le nombre d’objets).
On considere le sous-probleme P oidsSac(i, V ) suivant : quel est le poids limite minimum
Pi
d’un sac qui peut recevoir une collection d’objets de valeur au moins V , avec V ≤ vj ,
j=1
qui sont choisis uniquement parmi les objets d’indice j ≤ i ? Ce poids minimum est note
OP T (i, V ). Soit O une solution qui atteint le poids minimum OP T (i, V ).
a. Que vaut OP T (i, V ) si i ∈ O et i est l’unique objet de O ?
Solution. OP T (i, V ) = w(O) = wi .
b. Que vaut OP T (i, V ) si i ∈ O et i n’est pas l’unique objet de O ?
Solution. OP T (i, V ) = w(O) = wi + OP T (i − 1, V − vi ).
c. Montrer que dans le cas ou i ∈ O, on a toujours OP T (i, V ) = wi + OP T (i −
1, max{0, V − vi }).
Solution. Si i est le seul objet de O, alors vi ≥ V et la formule donne OP T (i, V ) =
wi + OP T (i − 1, max{0, V − vi }) = wi + OP T (i − 1, 0) = wi , ce qui est correct d’apres
la question a. Si i n’est pas le seul objet de O, alors vi < V et la formule donne
OP T (i, V ) = wi + OP T (i − 1, max{0, V − vi }) = wi + OP T (i − 1, V − vi ), ce qui est
correct d’apres la question b.
d. Que vaut OP T (i, V ) si i 6∈ O ?
Solution. Si i 6∈ O alors il existe une solution optimale a P oidsSac(i, V ) qui n’utilise
que les objets j < i. Cette solution est donc aussi une solution optimale a P oidsSac(i−
1, V ). Dans ce cas, on a donc OP T (i, V ) = OP T (i − 1, V ).
i−1
P
e. Donnez une formule de recurrence pour OP T (i, V ) dans le cas ou V > vj ?
j=1
i−1
P
Solution. Lorsque V > vj , necessairement i appartient a toute solution opti-
j=1
male a P oidsSac(i, V ). D’apres la question c, on a donc OP T (i, V ) = wi + OP T (i −
1, max{0, V − vi }).
i−1
P
f. Donnez une formule de recurrence pour OP T (i, V ) dans le cas ou V ≤ vj ?
j=1
Solution. Dans ce cas, il est possible qu’il existe une solution optimale qui ne contienne
pas i. La valeur de OP T (i, V ) est donc le min entre l’optimum des solutions qui ne
contiennent pas i, c’est a dire OP T (i−1, V ), et l’optimum des solutions qui contiennent
i, qui vaut wi + OP T (i − 1, max{0, V − vi }) comme on l’a deja montre a la question c.
i−1
P
On obtient donc, dans le cas ou V ≤ vj , OP T (i, V ) = min{OP T (i − 1, V ), wi +
j=1
OP T (i − 1, max{0, V − vi })}.
g. En utilisant les formules des deux questions precedentes, ecrivez un algorithme qui
calcule OP T (i, V ) pour toutes les valeurs possibles et pertinentes de i et V et qui
retourne OP T , la valeur de la solution optimale au probleme du sac a dos a valeurs
entieres.
Solution.
L’algorithme 3 fait un simple parcours de tous les couples (i, V ) valides, c’est a dire
Pi
avec V ≤ vj , et affecte pour chacun d’eux la valeur de OP T (i, V ) dans une table,
j=1
en suivant les formules de recurrence trouvees aux questions e et f (disjonction de cas
des lignes 4 a 7). L’initialisation de la recurrence se fait par les valeurs de OP T (i, 0)
qui sont 0 pour tous les i (ligne 2). Le calcul de OP T se fait a la fin en parcourant
Pn
la derniere ligne de la table, OP T (n, V ) pour 1 ≤ V ≤ vj , et en y selectionnant la
j=1
valeur maximale de V telle que OP T (n, V ) ≤ W . Notez que sur cette derniere ligne,
le probleme P oidsSac(n, V ) n’est pas contraint sur le choix des objets i ∈ J1, nK qui
peuvent etre utilises dans la solution. Il est donc identique au probleme initial du sac
a dos.
Algorithme 3 : Algorithme pour le calcul de OP T (i, V ) et de la valeur OP T de la
solution optimum au probleme du sac a dos a valeurs entieres.
1 pour i de 1 a n faire
2 OP T [i, 0] ← 0;
i
P
3 pour V de 1 a vj faire
j=1
i−1
P
4 si V > vj alors
j=1
5 OP T (i, V ) ← wi + OP T (i − 1, max{0, V − vi });
6 sinon
7 OP T (i, V ) ← min{OP T (i − 1, V ), wi + OP T (i − 1, max{0, V − vi })};
8 OP T ← 0;
n
P
9 pour V de 1 a vi faire
i=1
10 si OP T (n, V ) ≤ W alors
11 OP T ← V ;
12 retourner OP T ;
On note v ∗ = max {vi }.
1≤i≤n
h. Donnez la complexite de votre algorithme en fonction de n et v ∗ .
i
P
Solution. Remarquez que le calcul de la somme vj pour tous les i ∈ J1, nK peut etre
j=1
fait preliminairement et prend seulement un temps O(n). Le calcul de la formule de
recurrence (lignes 4 a 7) se fait en temps constant grace a la table OP T (., .). En plus
de la boucle "pour" principale (ligne 1) qui s’execute n fois et de la boucle "pour" de
n
vj = O(nv ∗ ), le temps d’execution de l’algorithme depend
P
la ligne 9 qui s’execute
j=1
du nombre d’execution de la boucle "pour" interne (ligne 3) qui s’execute exactement
n Pi
vj = O(n2 v ∗ ). Au total on obtient donc une complexite de O(n + nv ∗ + n2 v ∗ ) =
P
i=1 j=1
2 ∗
O(n v ).
On note aussi w∗ = max {wi }.
1≤i≤n
i. Exprimez la taille t, en nombre de bits, de l’entree de l’algorithme en fonction de
n, v ∗ et w∗ .
Solution. Comme chaque valeur vi est code en binaire sur log vi bits et chaque poids
Pn
wi est code sur log wi bits, cela prend au total un espace t = (log vi + log wi ) =
i=1
O(n(log v ∗ + log w∗ )).
j. La valeur de v ∗ est-elle polynomiale en fonction de t ?
Solution. Comme t depend logarithmiquement de v ∗ , on ne peut borner v ∗ qu’ex-
ponentiellement en fonction de t. C’est pour ca que la complexite de l’algorithme 3
telle que nous l’avons exprimee depend en fait exponentiellement de la taille t de l’en-
tree, malgre son aspect a premiere vue polynomial : O(n2 v ∗ ). Remarquez que si dans
l’entree les nombres etaient codes en unaire (a ne pas faire !), alors cette complexite
serait bien polynomiale en la taille de l’entree car on aurait alors t = O(n(v ∗ + w∗ )), et
surtout t ≥ v ∗ et t ≥ n (ainsi O(n2 v ∗ ) = O(t3 )). Dans ce cas, on dit que la complexite
de l’algorithme est pseudo-polynomiale. C’est a dire polynomiale avec un codage de
l’entree en unaire (qui est mauvais), et exponentielle avec un codage naturel en binaire
(qui est le bon codage a utiliser).