Programmation dynamique : applications

1. Présenter Toutes les découpes possibles pour une planche de longueur 4 sous forme d'un arbre.
2. Déterminer le revenu de chaque découpe possible
3. En déduire la découpe optimale pour une planche de longueur 4

SOLUTION

1. Si l'on décide de faire une première découpe de longueur i dans la planche, quelle sera la longueur de la planche restante
2. Si l'on décide de faire une première découpe de longueur i dans la planche, quel sera le revenu optimal en fonction de p[i] et de coupe_recurs(p, n-i) ?
3. Si l'on appelle q le revenu optimal d'une précédente hypothèse. Comment choisir entre q et la réponse à la question 2 de façon optimale ?
4. Déduire des questions précédentes un algorithme récursif résolvant le problème, et coder cet algorithme.

SOLUTION

1. Dans l'arbre précédent, entourer les deux plus grands sous arbres identiques
2. Quelle est la taille de cet arbre ?
3. De façon générale, si la planche a pour longueur n, quelle sera la taille de cet arbre ?

SOLUTION

• La case r[i] du tableau rcontiendra les revenus maximum pour une planche de longueur i
• Le tableau r devra être transmis lors des appels récursifs
• Il sera nécessaire de construire deux fonctions, dont une ne fera que construire le tableau r rempli initialement de 0, et appeler ensuite la fonction récursive elle même.
def planche_memo()->list: pass def coupe_dyna_TB(n: int, p: list, r: list)->int: pass p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]

SOLUTION

n est la longueur de la planche
p est le tableau contenant les prix de chaque planche (p[i] est le prix de la planche de longueur i)
r est un tableau de longueur n+1 contenant initialement des 0

boucle i pour calculer le revenu optimal d'une planche de longueur i (i de 1 à n)
	initialiser q
	boucle j pour tester toutes les découpes pour la planche de longueur i (j de 1 à i : on réalise une découpe de longueur j<i)
		q reçoit le maximum entre : une découpe précédente et ce que rapporte la découpe de longueur j
	stocker le revenu d'une découpe i dans le tableau r
renvoyer le résultat
			

SOLUTION

1. Appliquer la méthode gloutonne pour une somme de 1€77cts
2. Appliquer la méthode gloutonne pour une somme de 11cts
3. Trouver une solution pour cette somme de 11cts

SOLUTION

1. Tester la fonction récursive sur une somme de 11cts avec le système de monnaie [100,50,10,5,2]
2. Tester la fonction récursive sur les sommes 177cts et 289 cts avec le système de monnaie [100,50,10,5,2]. Quel problème rencontrez vous ?

SOLUTION

Dans l'arbre des appels récursifs de l'exemple ( voir ci-dessus ) :

1. Identifier les branches de cet arbre qui n'aboutissent pas à une solution
2. Identifier les branches de cet arbre qui aboutissent à une solution
3. Identifier le nombre de pièces optimales dans cette situation

SOLUTION

1. Coder une fonction fonction en python rendu_dyna, qui prend en argument une somme à rendre et un tableau de systemede monnaie.
2. Cette fonction doit créer un tableau memo contenant des 0, et de longueur somme+1
3. Cette fonction doit ensuite renvoyer un appel à rendu_dyna_memo(somme, systeme, f)

Comme vous l'avez compris nous venons de créer le tableau de mémoïsation f.
Par suite, ce tableau contiendra, à un indice i, le nombre de pièces à rendre pour la somme i.
Il nous reste à coder la fonction rendu_dyna_memo(somme, systeme, f) en s'appuyant sur la fonction récursive pure précédente.

Reprenez le code de votre fonction récursive et modifiez là comme indiqué ci-dessous :

1. Avant de commencer le remplissage récursif du tableau f, la fonction va vérifier si f[somme] n'existe pas déjà dans le tableau.
2. Nous gardons ensuite le cas d'arrêt.
3. Au lieu de stocker l'appel récursif +1 dans la variable nb, il sera stocké dans la case du tableau f[somme]
4. La recherche de minimum se fait ensuite sur f[somme]
5. Et la fonction renvoie f[somme]

1. Tester la nouvelle fonction sur une somme de 11cts avec le système de monnaie [100,50,10,5,2]
2. Tester la nouvelle fonction sur les sommes 177cts et 289 cts avec le système de monnaie [100,50,10,5,2]. Rencontrez vous le même problème que précédemment ?

Si vous avez suivi cette démarche pas à pas, vous voyez maintenant l'amélioration algorithmique qu'il existe entre une fonction récursive "simple" et une fonction récursive avec mémoïsation (programmation dynamique de haut en bas).

Question subsidiaire : pouvez-vous améliorer votre code pour qu'il renvoie aussi la liste des pièces à rendre pour la solution optimale ?

SOLUTION

• Créer un tableau de tableaux de la même taille que la matrice de départ, que vous nommerez phi. Chaque case de ce tableau de tableaux contiendra le plus court chemin pour aller jusqu'à la case (i,j) dans la matrice de départ.
• Créer une fonction plus_court_chemin prenant en paramètre le tableau phi, la matrice de départ et deux entiers i et j. Cette fonction renverra le plus court chemin dans la matrice de départ jusqu'à la case (i,j).
• Utiliser la fonction plus_court_chemin pour remplir le tableau de tableaux phi
• Afficher la dernière case du tableau phi.

SOLUTION

1. Que doit renvoyer la fonction si le pixel de coordonnées (x,y) est noir ?
2. Que doit renvoyer la fonction si x=0 ou si y=0 ?
3. Quels sont les coordonnées des pixels "en bas à droite" des trois carrés présentés ci-dessus
4. En déduire (ou appeler le professeur) la relation de récursivité permettant de trouver plusGrdCarreBlanc(x,y,img) grâce à trois appels récursifs et à une fonction de recherche de minimum.
5. Coder et tester la fonction plusGrdCarreBlanc(x,y,img)
6. Parcourir le tableau de tableaux pour chercher le plus grand carré blanc

test = [[1, 0, 0, 1, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
        [1, 0, 0, 0, 0, 0, 0, 0, 1, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
        [0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 1]]						
			

from random import randint

def creerIMG(n):
    img=[[0 for i in range (n)] for j in range(n)]
    for i in range(n):
        x=randint(0,n-1)
        y=randint(0,n-1)
        img[x][y]=1
    return img						
			

SOLUTION

• Dans ces fonctions, le tableau memo contiendra dans la case [x][y] le plus grand carré blanc en partant du pixel en bas à droite.
• Le tableau memo
devra être transmis lors des appels récursifs
• Il sera nécessaire de construire deux fonctions, dont une ne fera que construire le tableau de tableaux memo rempli initialement de None, et appeler ensuite la fonction récursive elle même.
• Une fois la fonction testé sur des cases choisies, parcourir le tableau de tableaux pour chercher le plus grand carré blanc

SOLUTION

Analysons ces cas possibles :

1. Insertion ou ajout d'une lettre : dans ce cas, la sous-chaîne j a une lettre en plus que la sous-chaîne i, et la distance est augmentée de 1 par rapport à la distance calculée à l'appel précédent, c'est à dire la distance entre deux chaînes de longueur :i et j-1 :

   

   → la relation de récurrence est alors : d(i, j) = 1 + d(i, j-1)
2. Suppression d'une lettre : dans ce cas, la sous-chaîne j a au contraire une lettre en moins que la sous-chaîne i :

   

   Établir la relation de récurrence qui lie alors d(i, j) à la valeur de d calculée à l'appel précédent.
3. Remplacement d'une lettre ou pas de modification : dans ces deux cas, les deux sous-chaînes ont la même taille, mais :
   • la distance augmente de 1 dans le cas du remplacement de la lettre à l'indice i de ch1 par la lettre à l'indice j de ch2 :

     

   • la distance n'augmente pas si ces deux lettres sont identiques :

     

   Établir alors la relation de récurrence qui donne d(i, j) dans ces deux situations.
4. le cas général sera le minimum entre les 3 valeurs calculées; quels sont alors les deux cas de base de la récursion ?

SOLUTION

Compléter la fonction dist_lev_rec récursive ci-dessous qui prend en paramètre deux indices i et j, et qui renvoie la distance de Levenshtein entre deux chaînes ch1 ( paramètre i ) et ch2 ( paramètre j ).

Pour simplifier la signature de la fonction ( il faudrait sinon aussi les passer en paramètres...), les chaînes ch1 et ch2 sont stockées dans deux variables définies dans le programme principal, et donc accessibles en lecture seule depuis la fonction.

Vérifier la correction de la fonction avec les exemples suivants, et d'autres !

• d('CHAT', 'CHUTE') = 2
• d('CHIEN', 'CHAT') = 3 ( 2 substitutions + 1 ajout )
• d('CHIEN', 'NICHE') = 4 ( 2 suppressions + 1 insertion + 1 ajout )
• d('CHAT', 'ANTICONSTITUTIONNELLEMENT') = 23 ( compte laissé à la charge du lecteur 😇)

SOLUTION

Écrire une fonction dist_lev_TB qui utilise la mémoïsation pour améliorer la complexité de l'algorithme :

Tester cette nouvelle version, notamment avec l'exemple des deux phrases ci-dessus !

SOLUTION

Pour chaque case (i, j), on calcule le coût minimal des insertions, suppressions et substitutions en "provenance" des cases voisines.

1. D'après l'étude précédente, et en vous aidant de la relation de récurrence établie précédemment, établir la relation générale qui permet de calculer la distance d(i, j) en fonction des valeurs des cases voisines.
2. en fin de remplissage du tableau, où se trouve la valeur de la distance minimale entre les deux chaînes ch1 et ch2 ?

SOLUTION

Implémenter, puis tester cette dernière approche.

On fera particulièrement attention à la manière d'adresser un caractère dans les chaînes ch1 et ch2...

SOLUTION