Programmation Dynamique

Un petit exemple: traverser un lac gelé

J'utilise un tableau qui, pour chaque borne (entre 0 et 100) et chaque état possible (nombre de chevaux vivants et quantité de nourriture), me dit si je peux arriver à la fin ou non.

Les éléments de ce tableau sont reliés par une récurrence. Actions possibles

Je remplis le tableau itérativement (ordre décroissant de nombre de kilomètres parcourus et ordre croissant de nombre de chevaux).

Le résultat souhaité est déterminé facilement du tableau final.

Facile à généraliser à calculer aussi (une) stratégie valable pour chaque situation d'où je peux sortir.

La méthode naïve

aurait été de calculer directement de la récurrence (peut-être par une fonction récursive) sans utiliser le tableau;

le temps de calcul aurait été déterminé par le nombre de façons de commencer le voyage

sans doute plusieures minutes de calcul

que la programmation dynamique a réduits à une fraction d'une seconde.

Le problème du voyageur de commerce

Il veut visiter toutes les n villes où il a des clients et rentrer chez lui
sans passer deux fois par la même ville
et dans le temps (ou coût ...) le plus petit possible.

Le temps pour visiter les derniers i villes dépend de quelles villes elles sont et d'où il se trouve après la (n-i)ième visite

forme générale de la récurrence:
V(E,i) = minj E-i(c(i,j)+V(E-i,j))

La programmation dynamique ne donne pas d'algorithme très performant mais aucun meilleur n'est connu qui garantit de donner toujours le parcours optimal.

Variante numéro 1
Economiser l'espace

Quand la récurrence donne la valeur de la colonne (ou tranche) i du tableau comme fonction de la colonne i+1 (ou i-1) on n'est pas obligé de garder tout le tableau; il suffit de garder deux colonnes à chaque moment.
(vrai pour la traversée du lac, le sac-à-dos, le voyageur)

Si, en outre, chaque élément d'une colonne ne dépend que des éléments de l'autre colonne qui sont en dessus (ou en dessous), il suffit de garder une colonne qui, à chaque moment, peut contenir un partie de l'ancienne colonne et une partie de la nouvelle!
(vrai pour la traversée, le sac-à-dos et peut-être le voyageur)

Un exemple (un peu) plus réaliste
probabilités et politique (de placement)

Placer des fonds dans des placements de haut, moyen ou bas risque de façon à maximiser les bénéfices (en moyenne) mais sous une contrainte de résultat garanti:

Calculer pour chaque montant possible et pour chaque an, le meilleur moyen possible (et la stratégie pour arriver à ce moyen) si on a ce montant au début de l'année

Pour chaque placement, décider s'il est permis (c'est-à-dire si dans le pire des cas on est garanti de finir avec les 1200 euros au moins);
si oui évaluer la moyenne des résultats finaux pour toutes les possibilités de la prochaine année;
et, bien sûr, choisir le placement qui donne le meilleur moyen et noter que ce placement est optimal dans cette situation.

Variante numéro 2
Eviter les calculs inutiles

Il se peut que quelques éléments du tableau ne sont utilisés dans le calcul final qui nous intéresse (c'est-à-dire ni directement ni indirectement) mais que la structure du problème est trop irrégulière pour savoir à l'avance lesquels;
(par exemple dans le cas de la traversée il est inutile de considérer des situations où on ne peux pas arriver)

En ce cas, la programmation dynamique comme décrite fait des calculs inutiles qui n'auraient pas été faits par la méthode récursive citée avant. Mais il est toujours vrai que cette méthode récursive fait BEAUCOUP plus de calculs parce qu'elle fait très souvent le même calcul plusieurs fois.

Il existe une méthode mixte qui ne fait que les calculs utiles et ne les fait qu'une fois: elle consiste à utiliser la structure récursive et un tableau; la première fois qu'un résultat est calculé il est inséré dans le tableau; les fois suivants, cette valeur est récupérée du tableau.

Nécessite une méthode de savoir quels éléments du tableau contiennent des résultats valables; ou une valeur impossible pour les non valables ou un tableau auxiliaire booléen.




File translated from TEX by TTH, version 3.05.
On 21 Nov 2005, 15:01.

symboles bricolés pour netscape par sed