Un autre algorithme de programmation dynamique pour le problème de sac-à-dos
Dans cette partie, nous allons décrire une autre construction possible de la programmation dynamique en prenant toujours comme exemple le problème de sac-à-dos.
Cette construction se base sur la création itérative d'un espace d'états représentant les solutions partielles générées à chaque niveau de la récurrence.
Exemple : Instance du problème
Pour illustrer la technique en question, on s'appuie sur la même instance du problème dont les paramètres sont le suivants :
Pour rappel, notre problème peut être formulé comme suit :
Maximiser 11x₁+8x₂+5x₃
tel que :
7x₁+6x₂+4x₃≤10
xi∈{0,1} ∀ 1≤i≤3
Méthode : Principe
Le principe de la deuxième approche consiste à construire à chaque itération i=0,1,2,...,N un ensemble Ei contenant des états [u,v] associés à des solutions partielles faisant intervenir les i premiers objets en sachant que :
- u est l'utilité totale associée à l'état,
- v est le volume utilisé associé à l'état.
Les relations de récurrence, nécessaires pour calculer les états à chaque itération, se basent sur le principe suivant.
Fondamental : Règle d'évolution
Soit [u,v] un état de l'ensemble E(i-1) généré à l'itération i-1 (i=1,2,...,N). A partir de cet état, deux états peuvent être créés dans l'ensemble E(i) à l'itération suivante selon les conditions suivantes :
[u + wi, v + vi] si v + vi ≤Vmax (ceci implique que l'objet i a été pris dans le sac)
[u, v] (cela implique que l'objet i n'a pas été pris dans le sac).
Méthode : Algorithme
E(0)={[0,0]}
Pour i=1,2,3,...,N
Initialiser E(i)={}.
Créer pour chaque [u,v] de E(i-1) deux états [u + wi, v + vi] si v + vi ≤Vmax et [u,v] et les insérer dans E(i).
Supprimer E(i-1).
Pour chaque valeur v, garder au maximum un état [u,v] dans E(i) avec u maximal.
Retourner max [u,v] dans E(n) {u}
Calcul et résultats
Le détail du calcul est résumé dans le tableau suivant :
i | E(i) |
0 | {[0,0]} |
1 | {[0,0] ; [11,7]} |
2 | {[0,0] ; [8,6] ; [11,7]} |
3 | {[0,0] ; [5,4] ; [8,6] ; [13,10] ;[11,7]} |
Le valeur maximale est obtenue pour l'état [13,10] dans E(3), ce qui confirme que l'utilité optimale est égale à 13.
Fondamental :
La complexité de l'algorithme de programmation dynamique est de O(N.Vmax). En effet, on peut remarquer que le nombre d'états générés à chaque itération est borné par (Vmax+1). De plus, nous avons (N+1) itérations à réaliser. Ceci conduit également à une complexité de O(N.Vmax).
Simulation : Visualiser l'espace d'états
L'ensemble d'états à chaque itération est calculé et représenté dans l'animation suivante. Afin d'assurer une meilleure compréhension de l'algorithme proposé, nous recommandons au lecteur de visualiser le fichier PPS suivant. La grille représente l'espace d'états et les coordonnées des points s'affichant à chaque itération représentent les valeurs des états associés. Il est important de noter que la grille est dimensionnée pour que tout état réalisable puisse être représenté (Vmax est la borne supérieure pour la variable v et (w1+w2+w3) est une borne supérieure pour la variable u).
Cette animation facilitera donc de saisir étape par étape l'exécution progressive de l'algorithme.
