ITC2 – TD 2-4

Dans cette page, voyez la méthode de programmation dynamique en informatique du tronc commun deuxième année (ITC2) en prépa scientifique appliquée à la partition équilibrée d’entiers positifs. Méthodes ascendante itérative et descendante récursive mémoïsée illustrées en live dans la vidéo ci-dessous :

Visualiser et exécuter le code de la vidéo

Sujet PFD du TP :

proxy.php?id=pdf-itc2-2-4

Programmer ce TP directement ici sur Basthon :

↑ Ce Basthon reste en cache du navigateur ↑

Visualiser le Basthon correction
Visualiser les liens Dropbox vers les différents documents de ce TD

Liens :

Codes non exécutables indépendants de Basthon et Dropbox (peuvent ne pas être à jour)

Code de la vidéo :

## Algorithme par force brute

def explore(E):
    Res = [[]]
    for e in E:
        res = []
        for l in Res:
            ll = l + [e]
            res.append(ll)
        Res += res
    return Res

E = [75,69,43,90,110,58,62,72,86,25]
Exp = explore(E)
# print(Exp)

def sommes(Exp):
    Res = []
    for i in range(len(Exp)):
        l = Exp[i]
        s = sum(l)
        res = [s,i]
        Res.append(res)
    Res.sort()
    return Res

Ls = sommes(Exp)
# print(Ls)

def solution(Ls,Smax):
    n = len(Ls)
    for i in range(n-1,-1,-1):
        s,j = Ls[i]
        if s <= Smax:
            break
    return j

Smax = sum(E)//2
ind = solution(Ls,Smax)
F = Exp[ind]
#print(F)
#print('Smax:',Smax)
#print("Somme solution:",sum(F))

## Programmation dynamique

## Méthode ascendante itérative

def PEEP_it(E):
    D = {}
    n = len(E)
    S = sum(E)//2
    for i in range(n+1):
        D[i,0] = True
    for j in range(1,S+1):
        D[0,j] = False
    for i in range(1,n+1):
        for j in range(1,S+1):
            D[i,j] = D[i-1,j] or (j>=E[i-1] and D[i-1,j-E[i-1]])
    return D

E = [21,3,6,15,12]
D = PEEP_it(E)

import numpy as np
def matrice(f,E):
    n = len(E)
    S = sum(E)//2
    A = 0.5*np.ones([n+1,S+1])
    dico = f(E)
    for i,j in dico:
        A[i,j] = dico[i,j]
    return A

A = matrice(PEEP_it,E)

from matplotlib import pyplot as plt
plt.close('all')
def Spy(fig,Mat):
    plt.figure(fig)
    plt.imshow(Mat)
    plt.show()

Spy(1,A)

## Méthode descendante récursive

def PEEP_rec_ij(i,j,E):
    if j==0 :
        return True
    elif i==0:
        return False
    else:
        return PEEP_rec_ij(i-1,j,E) or (j>=E[i-1] and PEEP_rec_ij(i-1,j-E[i-1],E))

def PEEP_rec_mem(E):
    def rec(i,j,E):
        if (i,j) in D:
            return D[i,j]
        else:
            if j==0 :
                res = True
            elif i==0:
                res = False
            else:
                res = rec(i-1,j,E) or (j>=E[i-1] and rec(i-1,j-E[i-1],E))
            D[i,j] = res
            return res
    D = {}
    ni = len(E)
    nj = sum(E)//2
    for i in range(ni+1):
        for j in range(nj+1):
            rec(i,j,E)
    return D

A = matrice(PEEP_rec_mem,E)
Spy(2,A)

def PEEP_rec_mem_opt(E):
    def rec(i,j,E):
        if (i,j) in D:
            return D[i,j]
        else:
            if j==0 :
                res = True
            elif i==0:
                res = False
            else:
                res = rec(i-1,j,E) or (j>=E[i-1] and rec(i-1,j-E[i-1],E))
            D[i,j] = res
            return res
    D = {}
    ni = len(E)
    nj = sum(E)//2
    for j in range(nj,-1,-1):
        if rec(ni,j,E):
            break
    return D

A = matrice(PEEP_rec_mem_opt,E)
Spy(3,A)

## Solution

def Smax(E):
    D = PEEP_it(E)
    ni = len(E)
    nj = sum(E)//2
    i = ni
    j = nj
    while not(D[i,j]):
        j -=1
    return j

Sm = Smax(E)
print(Sm)

def PEEP(E):
    F = []
    G = []
    D = PEEP_it(E)
    j = Smax(E)
    i = len(E)
    while i>0 or j>0:
        C1 = D[i-1,j]
        e = E[i-1]
        C2 = D[i-1,j] or (j>=e and D[i-1,j-e])
        if C1:
            i -= 1
            G.append(e)
        else: # Donc C2
            i -= 1
            j -= e
            F.append(e)
    return F,G

E = [75,69,43,90,110,58,62,72,86,25]
F,G = PEEP(E)
print(F,sum(F))
print(G,sum(G))

Code correction :

'''ITC2 - 2 - Dictionnaires et programmation dynamique'''

'''2-4 - Partition équilibrée d'entiers positifs'''

## Algorithme par force brute

# Question 1 - explore

def explore_rec(E): # Version récursive
    if len(E)==0:
        return [[]] ##
    else:
        e = E[-1]
        Reste = E[:-1]
        Exp = explore_rec(Reste)
        Res = [] + Exp ##
        for l in Exp:
            Res.append(l+[e])
        return Res

""" Remarque:
On oublie qu'il faut une liste de listes vides
On oublie d'ajouter Exp à Res
Ne pas utiliser pop pour ne pas vider E
e = E[-1] pour correspondre à la fonction itérative explore
"""

E = [2,5,10]
Exp_rec = explore_rec(E)
print(Exp_rec)

def explore(E):
    res = [[]]
    for x in E:
        S = []
        for s in res:
            ss = s + [x]
            S.append(ss)
        res += S
    return res

E = [2,5,10]
Exp = explore(E)
print(Exp)

# Question 2 - Complexité

'''
La taille de res vaut 1, puis 2, puis 4, puis 8 etc
Taille de res à l'itération i: 2^(i-1)
On fait donc n pour i de 0 à n-1 boucles ayant chacune 2^i calculs
2^0 + 2^1 + 2^2 + ... + 2^(n-1)
Soit O(2^n)
'''

# Question 3 - sommes

def sommes(Exp):
    Ls = []
    for i in range(len(Exp)):
        expi = Exp[i]
        s = sum(expi)
        Ls.append([s,i])
    Ls.sort()
    return Ls

Ls = sommes(Exp)
print(Ls)

# Question 4 - solution

def solution(Ls,Smax):
    n = len(Ls)-1
    for i in range(n,-1,-1):
        s,ind = Ls[i]
        if s<=Smax:
            break
    return ind,s

# Quetion 5 - Application

E = [75,69,43,90,110,58,62,72,86,25]
Exp = explore(E)
Ls = sommes(Exp)
Smax = sum(E)//2
ind,s = solution(Ls,Smax)
F = Exp[ind]
print(F,s)

''' Remarque
sort trie de manière lexicographique
Elle trie Ls par la somme d'abord, puis pour les mêmes sommes, par l'indice
explore crée les listes par ordre de nombre de termes croissant
En parcourant la liste Ls depuis la fin, solution renverra pour une même somme, l'indice le plus grand (parcours en arrière), donc la partition F de plus grand nombre de termes.
'''

## Programmation de l’algorithme itératif

# Question 6 - dico

def PEEP_it(E):
    D = {}
    SE = sum(E)
    ni = len(E)
    nj = SE//2
    for i in range(ni+1):
        D[(i,0)] = True
    for j in range(1,nj+1):
        D[(0,j)] = False
    for i in range(1,ni+1):
        for j in range(1,nj+1):
            e = E[i-1]
            D[(i,j)] = D[(i-1,j)] or ((j >= e) and D[(i-1,j-e)])
    return D

E = [21,3,6,15,12]
dico = PEEP_it(E)

""" Remarque
Soit le test (c1 or c2). En Python, c2 ne sera évaluée que si c1 est False. Il faut donc profiter de cet avantage en mettant tout sur le même ligne (oui, pour une fois, j'accepte une longue ligne ;))
"""

""" Versions différentes """

def PEEP_it_bis_1(E):
    D = {}
    SE = sum(E)
    ni = len(E)
    nj = SE//2
    for i in range(ni+1):
        for j in range(nj+1):
            if j==0:
                D[(i,0)] = True
            elif i==0: # donc j>0
                D[(0,j)] = False
            else: # Remarque
                D[(i,j)] = D[(i-1,j)] or ((j >= E[i-1]) and D[(i-1,j-E[i-1])])
    return D

""" Remarque
Attention, certains élèves mettent un elif et la condition totale, ce qui conduit à ne stocker que les True et à une keyerror
Sauf si on initialise avec des False, version ci-dessous, mais qui double le travail...
"""

def PEEP_it_bis_2(E):
    D = {}
    SE = sum(E)
    ni = len(E)
    nj = SE//2
    for i in range(ni+1):
        for j in range(nj+1):
            D[(i,j)] = False
    for i in range(ni+1):
        for j in range(nj+1):
            if j==0:
                D[(i,0)] = True
            elif i>0 and (D[(i-1,j)] or ((j >= E[i-1]) and D[(i-1,j-E[i-1])])):
                D[(i,j)] = True
    return D

# Question 7 - Complexité

'''
On crée une table de taille (n+1)*(S+1)
O(n*S)
'''

# Question 8 - matrice

import numpy as np

def matrice(f,E):
    SE = sum(E)
    ni = len(E)
    nj = SE//2
    dico = f(E)
    A = 0.5*np.ones([ni+1,nj+1])
    for i,j in dico:
        A[i,j] = dico[(i,j)] # True mettra 1 et False 0
    return A

''' Attention
Ne pas parcourir tous les i et j, sinon il y aura des erreurs avec la fonction optimisée de la fin
'''

E = [21,3,6,15,12]
A = matrice(PEEP_it,E)

''' Attention
Ne pas boucler sur tous les i et j car si pour le moment, le dictionnaire contient bien toutes les clés (i,j), nous allons plus tard faire une version qui ne calcule pas tout et il y aura alors ici une keyerror pour les cases non présentes dans le dictionnaire
'''

# Question 9 - Affichage

from matplotlib import pyplot as plt
plt.close('all')

def Spy(fig,M):
    plt.figure(fig)
    plt.imshow(M)
    plt.show()

E = [21,3,6,15,12]
A = matrice(PEEP_it,E)
Spy(1,A)

# Question 10 - S_max

'''
Idéalement, il faudrait voir si dico[n,S] est True, alors il y a une solution parfaite.
On parcours la ligne du bas de la matrice, et on trouve la plus grande valeur S=j atteignable avec n termes - Dernier True sur cette ligne
'''

def S_max(E):
    dico = PEEP_it(E)
    ni = len(E)
    nj = sum(E)//2
    for j in range(nj,-1,-1):
        if dico[(ni,j)]:
            return j

'''
Il y a au moins un True à la dernièer ligne, à la colonne du premier élement de E
'''

E = [21,3,6,15,12]
test = S_max(E)
print("Q10:",test)

## Programmation de l’algorithme récursif

# Question 11 - PEEP_rec_ij

def PEEP_rec_ij(i,j,E): # c2 or c1
    if j==0:
        return True
    elif i==0: # Forcément, j n'est pas nul
        return False
    else:
        e = E[i-1]
        Cond = ((j >= e) and PEEP_rec_ij(i-1,j-e,E)) or PEEP_rec_ij(i-1,j,E)
        return Cond

def PEEP_rec_ij(i,j,E): # c1 or c2
    if j==0:
        return True
    elif i==0: # Forcément, j n'est pas nul
        return False
    else:
        e = E[i-1]
        Cond = PEEP_rec_ij(i-1,j,E) or ((j >= e) and PEEP_rec_ij(i-1,j-e,E))
        return Cond

E = [21,3,6,15,12]
test = PEEP_rec_ij(0,21,E) # False
print(test)
test = PEEP_rec_ij(1,21,E) # True
print(test)

# Question 12 - Complexité

'''
Pire des cas: tous les éléments sont des 1 (e=1)
On aura deux auto appels au rang n-1
Il faut imaginer l'arbre obtenu
         22
    12       11
  02  01   01  00
  On sera en O(2^n)

Remarques:
- La présence des conditions OR et AND en Python fait que si le résultat est connu de manière sûre, le reste n'est pas évalué. Ainsi, en mettant le premier test PEEP_rec_ij(i-1,j,E), s'il est évalué à True, le reste n'est pas fait.
- Dans le cas de 100 fois 1, la table a 100 lignes et 50 colonnes:
 * Avec le test c1 or c2: Il remonte en premier jusqu'en haut, puis redescend et évalue la diagonale de gauche en remontant jusqu'à la première ligne à chaque fois. La complexité est la pire en 2^n
 * Avec le test c2 or c1: Il remonte toute la diagonale sur 50 valeurs et renvoie le résultat immédiatement: O(n)
A priori, il est préférable de faire c2 or c1 de manière à remonter la solution la plus proche de la fin et d'éviter des tests inutiles. je ne changerai pas la suite où je fais c1 or c2
'''

''' Test
n = 100
E = [1 for i in range(n)]
SE = sum(E)
i = n
j = SE//2
PEEP_rec_ij(i,j,E)
'''

'''
En inversant les 2 conditions, le pire des cas devient le meilleur avec un seul parcours en diagonale
'''

# Question 13 - PEEP_rec_mem

def PEEP_rec_mem(E): # c1 or c2
    def rec(i,j,E):
        if (i,j) in dico:
            return dico[(i,j)]
        else:
            if j==0:
                res = True
            elif i==0: # Forcément, j n'est pas nul
                res = False
            else:
                e = E[i-1]
                res = rec(i-1,j,E) or ((j >= e) and rec(i-1,j-e,E))
            dico[(i,j)] = res
            return res
    dico = {}
    ni,nj = len(E),sum(E)//2
    for i in range(ni+1):
        for j in range(nj+1):
            rec(i,j,E)
    return dico

E = [21,3,6,15,12]
A = matrice(PEEP_rec_mem,E)
Spy(2,A)

''' Attetion
j'avais écrit avant:
    c1 = rec(i-1,j,E)
    c2 = (j >= e) and rec(i-1,j-e,E)
    res = (c1 or c2)
Ce qui traite tout le temps les deux conditions alors que les mettre sur la même ligne ne traite la seconde condition que si la première est False. On obtient une image différente
'''

# Question 14 - PEEP_rec_mem_opt

'''
On ne parcoure que la dernière ligne de droite à gauche jusqu'à obtenir un True
'''

def PEEP_rec_mem_opt(E): # Création c1 et c2
    def rec(i,j,E):
        if (i,j) in dico:
            return dico[(i,j)]
        else:
            if j==0:
                res = True
                dico[(i,j)] = res
                return res
            elif i==0: # Forcément, j n'est pas nul
                res = False
                dico[(i,j)] = res
                return res
            else:
                e = E[i-1]
                C1 = (j >= e) and rec(i-1,j-e,E)
                C2 = rec(i-1,j,E)
                res = C1 or C2
                dico[(i,j)] = res
                return res
    dico = {}
    ni,nj = len(E),sum(E)//2
    i = ni
    j = nj
    while not rec(i,j,E):
        j -= 1
    return dico

def PEEP_rec_mem_opt(E): # c2 or c1
    def rec(i,j,E):
        if (i,j) in dico:
            return dico[(i,j)]
        else:
            if j==0:
                res = True
                dico[(i,j)] = res
                return res
            elif i==0: # Forcément, j n'est pas nul
                res = False
                dico[(i,j)] = res
                return res
            else:
                e = E[i-1]
                res = ((j >= e) and rec(i-1,j-e,E)) or rec(i-1,j,E)
                dico[(i,j)] = res
                return res
    dico = {}
    ni,nj = len(E),sum(E)//2
    i = ni
    j = nj
    while not rec(i,j,E):
        j -= 1
    return dico

def PEEP_rec_mem_opt(E): # c1 or c2
    def rec(i,j,E):
        if (i,j) in dico:
            return dico[(i,j)]
        else:
            if j==0:
                res = True
                dico[(i,j)] = res
                return res
            elif i==0: # Forcément, j n'est pas nul
                res = False
                dico[(i,j)] = res
                return res
            else:
                e = E[i-1]
                res = rec(i-1,j,E) or ((j >= e) and rec(i-1,j-e,E))
                dico[(i,j)] = res
                return res
    dico = {}
    ni,nj = len(E),sum(E)//2
    i = ni
    j = nj
    while not rec(i,j,E):
        j -= 1
    return dico

E = [21,3,6,15,12]
A = matrice(PEEP_rec_mem_opt,E)
Spy(3,A)

''' Erreur Keyerror ?
Vous avez probablement fait une fonction Matrice qui parcourt tous les i et j au lieu de ne parcourir que les couples (i,j) clés du dictionnaire. Avec la version optimisée, des cases ne sont pas calculées
'''

## Etapes intermédiaires

# Question 15 - PEEP

def PEEP(E):
    F = []
    G = []
    dico = PEEP_it(E)
    i = len(E)
    j = S_max(E)
    while i>0 or j>0:
        c1 = dico[(i-1,j)]
        e = E[i-1]
        c2 = (j >= e) and dico[(i-1,j-e)]
        if c1:
            i -= 1
            G.append(e)
        else: # donc c2
            i -= 1
            j -= e
            F.append(e)
    return F,G

E = [21,3,6,15,12]
F,G = PEEP(E)
print(F)
print(G)

## Application 1

L_Pds = [75,69,43,90,110,58,62,72,86,25]
P_tot = sum(L_Pds)
print('Poids total:',P_tot)
Res = S_max(L_Pds)
print("Poids trouvé:",Res)
Possible = (Res == P_tot//2)
print("Solution parfaite ?",Possible)
F,G = PEEP(L_Pds)
print(F,sum(F))
print(G,sum(G))

'''
[72, 62, 58, 110, 43] 345
[25, 86, 90, 69, 75] 345
'''

## Application 2

def ap2_PEEP_it(E,S): # Ajout de S - Suppression de la ligne S=
    D = {}
    ni = len(E)
    nj = S # Modification
    for i in range(ni+1):
        D[(i,0)] = True
    for j in range(1,nj+1):
        D[(0,j)] = False
    for i in range(1,ni+1):
        for j in range(1,nj+1):
            c1 = D[(i-1,j)]
            e = E[i-1]
            c2 = (j >= e) and D[(i-1,j-e)]
            D[(i,j)] = c1 or c2
    return D

def ap2_S_max(E,S): # Ajout de S - Suppression de la ligne S=
    dico = ap2_PEEP_it(E,S) # Ajout de S
    ni = len(E)
    nj = S # Modification
    for j in range(nj,-1,-1):
        if dico[(ni,j)]:
            return j

def ap2_PEEP(E,S): # S et j'enlève G inutile partout
    F = []
    G = []
    dico = ap2_PEEP_it(E,S) # S
    i = len(E)
    j = ap2_S_max(E,S) # S
    while i>0 or j>0:
        c1 = dico[(i-1,j)]
        e = E[i-1]
        c2 = (j >= e) and dico[(i-1,j-e)]
        if c1:
            i -= 1
            G.append(e)
        else: # donc c2
            i -= 1
            j -= e
            F.append(e)
    return F,G

L_Prix = [17,15,12,19,18,13,7,9]
Argent = 70
Dep = ap2_S_max(L_Prix,Argent)
print('Dépense',Dep)
print("Solution parfaite ?",Dep==Argent)
F,_ = ap2_PEEP(L_Prix,Argent)
print(F,sum(F))

'''
Dépense 70
Solution parfaite ? True
[7, 19, 12, 15, 17] 70
'''

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Les Sciences Industrielles de l'Ingénieur (SII) et l'Informatique du Tronc Commun (ITC) en CPGE par Denis DEFAUCHY