Site WWW de Laurent Bloch
Slogan du site

ISSN 2271-3905
Cliquez ici si vous voulez visiter mon autre site, orienté vers des sujets moins techniques.

Pour recevoir (au plus une fois par semaine) les nouveautés de ce site, indiquez ici votre adresse électronique :

Programmation dynamique
Exemples simples
Article mis en ligne le 16 mai 2006
dernière modification le 11 mai 2021

par Laurent Bloch

"http://www.w3.org/TR/REC-html40/loose.dtd">

Programmation dynamique, autres exemples

Cet article est suivi d’un exemple d’application réelle.


Programmation dynamique, autres exemples

Laurent Bloch

Le 10 mai 2006




Principes


Mémorisation



Une idée séduisante est la suivante : prenons notre programme fib tel qu'il est :

(define (fib x) (if (< x 2) x (+ (fib (- x 1)) (fib (- x 2)))))


et associons-lui une table dans laquelle seront archivés les valeurs de F déjà calculées. La taille de la table est facile à prévoir : pour calculer Fn il faut une table de n cases.

À chaque calcul de Fi nous consultons la iieme case de la table, soit le calcul a déjà été effectué et nous y recueillons le résultat, soit nous le calculons et l'y inscrivons pour un usage ultérieur.

Cette méthode est élégante, efficace et indépendante de l'algorithme utilisé.

(module memofib (main get-n)) (define (get-n args) (print (memo-fib (string->number (cadr args))))) (define (make-table) (list '*TABLE*)) (define (cherche clef table) (let ((result (assoc clef (cdr table)))) (if result (cdr result) #f))) (define (insert! clef valeur table) (let ((result (assoc clef (cdr table)))) (if result (set-cdr! result valeur) (set-cdr! table (cons (cons clef valeur) (cdr table))))) 'ok)


(define (memoize f) (let ((table (make-table))) (lambda (x) (let ((result-deja-obtenu (cherche x table))) (or result-deja-obtenu (let ((result (f x))) (insert! x result table) result)))))) (define memo-fib (memoize (lambda (n) (if (< n 2) n (+ (memo-fib (- n 1)) (memo-fib (- n 2)))))))

Un exemple de programmation dynamique



La programmation dynamique résout des problèmes en combinant des solutions de sous-problèmes. (Thomas Cormen, Charles Leiserson, Ronald Rivest et Clifford Stein, Introduction à l'algorithmique)


L'idée de la programmation dynamique est proche de celle de mémorisation que nous venons d'évoquer, elle s'en distingue par ceci : la mémorisation archive les résultats au fur et à mesure de leur calcul tandis que la programmation dynamique effectue la construction de la table des valeurs selon un ordre a priori, supposé judicieux.

La programmation dynamique est par exemple souvent un bon choix lorsque l'on aura besoin, après les avoir calculées, des valeurs stockées dans tous les noeuds d'un arbre ou dans toutes les cases d'un tableau. Parfois aussi cette conservation des résultats intermédiaires est imposée par un problème tel que le calcul d'une valeur se fait en fonction de toutes les précédentes. L'art algorithmique consiste à chercher des solutions qui évitent ce type de contrainte mais c'est parfois impossible.

Nous allons donc chercher des procédés pour associer un algorithme qui calcule des valeurs successives avec une structure de données qui les archive.

Reprenons notre exemple de triangle de Pascal et examinons dans quel ordre sont calculés les résultats successifs1 en ne considérant que le premier calcul de chacun : d'abord C00, puis C10 et C11, puis C20, C21 et C22...

Notre programme se contentait d'imprimer les résultats au fur et à mesure de leur obtention, si nous voulons maintenant les conserver ceci suggère un calcul itératif qui remplirait un tableau qu'en Scheme nous implanterions comme un vecteur de vecteurs. Le programme est annexé à la fin de ce texte (cf. ).



Annexe : programme « triangle de Pascal »



;; Pour le triangle de Pascal : (define (pascal n) (let ((T (make-table n n))) (do ((i 0 (+ i 1))) ;; initialisation de la ((= i n)) ;; premire colonne 1 (table-set! T i 0 1)) (do ((i 1 (+ i 1))) ;; on commence 1 ((= i n)) ;; on s'arrte n-1 (do ((j 1 (+ j 1))) ((> j i)) (table-set! T i j (+ (table-ref T (- i 1) (- j 1)) (table-ref T (- i 1) j))))) T)) ;; un constructeur, pour crer des objets du type : (define (make-table n m) (let ((the-table (vector "*TABLE*" (make-vector n #f)))) (do ((i 0 (+ i 1))) ((= i n)) (vector-set! (vector-ref the-table 1) i (make-vector m 0))) the-table)) ;; un prdicat d'appartenance, pour vrifier qu'un ;; objet appartient bien au type : (define (table? obj) (and (vector? obj) (string=? (vector-ref obj 0) "*TABLE*") (vector? (vector-ref obj 1)))) ;; un mutateur, pour modifier un objet du type en ;; affectant une valeur un lment du tableau : (define (table-set! T i j val) (if (table? T) (vector-set! (vector-ref (vector-ref T 1) i) j val))) ;; un slecteur, pour accder un lment d'un ;; tableau du type : (define (table-ref T i j) (if (table? T) (vector-ref (vector-ref (vector-ref T 1) i) j))) ;; diverses procdures utilitaires dont la fonction se ;; comprend d'elle-mme : (define (table-nlines T) (if (table? T) (vector-length (vector-ref T 1)))) (define (table-ncols T) (if (table? T) (vector-length (vector-ref (vector-ref T 1) 0)))) (define (table-print T) (if (table? T) (let ((n (table-nlines T)) (m (table-ncols T))) (do ((i 0 (+ 1 i))) ((= i n)) (let ((this-line (vector-ref (vector-ref T 1) i))) (do ((j 0 (+ 1 j))) ((= j m)) (display (vector-ref this-line j)) (display " ")) (newline)))))) ;; Pour faire de cette collection de procdures un module ;; compilable par Bigloo, on ajoutera en tte : (module tables (export (make-table n m) (table? obj) (table-set! T i j val) (table-ref T i j) (table-nlines T) (table-ncols T) (table-print T))) ;; Nous aurons ainsi cr um modules tables, que nous pourrons ;; utiliser, par exemple, dans le module principal use-tables : (module use-tables (import tables) (main start)) (define (start args) (let ((i (string->integer (cadr args))) (j (string->integer (caddr args)))) (build-table i j))) (define (build-table i j) (let ((T (make-table i j))) (do ((k 0 (+ 1 k))) ((= i k)) (do ((l 0 (+ 1 l))) ((= j l)) (table-set! T k l (+ l k)))) (table-print T)))



1
dont nous savons qu'ils sont, pour la ligne de rang n en partant de 0, les coefficients du polynôme obtenu par élévation à la puissance n du binôme (a+b), soit, pour le pieme coefficient en partant de 0 de la nieme ligne, le nombre de combinaisons de p éléments parmi n, soit Cnp.

This document was translated from LATEX by HEVEA.