Aller au contenu

Programmation dynamique - TP 2

Ce TP applique la méthode du chapitre sur la programmation dynamique : récurrence naïve, mémoïsation, tabulation puis reconstruction.

Subset-Sum

On s'intéresse ici au problème SUBSET-SUM : étant donné un ensemble d'entiers \(v_0, \dots, v_{n-1} \in \mathbb{N}^*\) et un entier \(T \in \mathbb{N}\) cible, existe-t-il \(\{ i_1, \dots, i_k\} \subset \range{0}{n-1}\) tel que \(T = v_{i_1} + \dots + v_{i_k}\) ? Autrement dit, existe-t-il un sous-ensemble des valeurs de somme \(T\) ?

On va considérer les valeurs dans un tableau values et pour représenter un sous-ensemble, un tableau subset de même taille de booléens (True ou False) qui représentera l'ensemble des values[i] pour lesquels subset[i] vaut True.

Question 1

Écrire une fonction get_subset telle que get_subset(values, subset) renvoie la liste des éléments du sous-ensemble.

Corrigé 
def get_subset(values, subset):
    s = []
    for i in range(len(values)):
        if subset[i]:
            s.append(values[i])
    return s

Tests :

assert(get_subset([1,2,3,4,5],
    [True,False,True,True,False]) == [1,3,4])
assert(get_subset([1,2], [False,False]) == [])
assert(get_subset([1,2], [True,True]) == [1,2])
"OK"

Résolution par backtracking

On va résoudre récursivement ce problème en énumérant tous les sous-ensembles.

\(\mathop{Recherche}(i, S, T)\) :

  • si \(T = 0\), on renvoie le sous-ensemble \(S\) ;
  • si \(i \ge n\), on échoue ;
  • si \(v_i \le T\), on lance \(\mathop{Recherche}(i+1, S \cup \{v_i\}, T-v_i)\) :
    • si cela a réussi, on renvoie ce sous-ensemble ;
  • on renvoie le résultat de \(\mathop{Recherche}(i+1, S, T)\).

Il suffit donc de lancer \(\mathop{Recherche}(0, \emptyset, T)\) pour essayer d'obtenir une décomposition.

Question 2

Écrire une fonction subsetsum_bt telle que subsetsum_bt(values, i, subset, target) renvoie un sous-ensemble de values permettant d'obtenir target s'il en existe un et renvoie None sinon.

Corrigé 
def subsetsum_bt(values, i, subset, target):
    if target == 0:
        return get_subset(values, subset)
    if i >= len(values):
        return None
    if values[i] <= target and not subset[i]:
        subset[i] = True
        v = subsetsum_bt(values, i+1, subset, target-values[i])
        if v != None:
            return v
        subset[i] = False
    return subsetsum_bt(values, i+1, subset, target)

On peut tester cette fonction ainsi avec \(0\) et \(\emptyset\) (un tableau de False).

subsetsum_bt([1,3,5,7],0,[False,False,False,False],10)

subsetsum_bt([1,3,5,7],0,[False,False,False,False],15)

subsetsum_bt([1,3,5,7],0,[False,False,False,False],2)

On obtient respectivement [3, 7], [3, 5, 7] et None.

Tests :

assert(subsetsum_bt([1,3,5],0,[False,False,False],4) == [1,3])
assert(subsetsum_bt([1,3,5,7],0,[False,False,False,False],10) == [3,7])
"OK"

On remarque que cet algorithme va énumérer tous les sous-ensembles dans le pire cas, donc il est en \(O(2^n)\) pour \(n\) valeurs. On ne connaît pas d'algorithme de complexité polynomiale pour ce problème : il s'agit d'un problème dit NP-complet, et en trouver un permettrait de résoudre le fameux problème P = NP.

On va essayer d'utiliser la programmation dynamique ici.

Problème de décision

On va se restreindre à une version plus simple ici où se pose la question de savoir si c'est possible ou non d'atteindre \(T\) mais sans chercher explicitement le sous-ensemble qui le réalise.

Question 3

Écrire une fonction subsetsum_rec_aux telle que subsetsum_rec_aux(values, target, i) renvoie un booléen indiquant si le nombre target peut être atteint par un sous-ensemble de valeurs dans values d'indice \(\ge i\).

Corrigé 
def subsetsum_rec_aux(values, target, i):
    if target == 0:
        return True
    if i >= len(values):
        return False
    b = subsetsum_rec_aux(values, target, i+1)
    if values[i] <= target:
        b = b or subsetsum_rec_aux(values, target-values[i], i+1)
    return b

Tests :

assert(subsetsum_rec_aux([1,3,4], 0, 0))
assert(subsetsum_rec_aux([1,3,4], 4, 0))
assert(subsetsum_rec_aux([1,3,4], 1, 0))
assert(subsetsum_rec_aux([1,3,4], 8, 0))
assert(not subsetsum_rec_aux([1,3,4], 2, 0))
assert(not subsetsum_rec_aux([1,3,4], 9, 0))
"OK"

Question 4

Écrire une fonction subsetsum_rec telle que subsetsum_rec(values, target) renvoie le booléen indiquant si target peut être écrit comme la somme d'un sous-ensemble des valeurs dans values en utilisant subsetsum_rec_aux.

Corrigé 
def subsetsum_rec(values, target):
    return subsetsum_rec_aux(values, target, 0)

Tests :

assert(subsetsum_rec([1,3,4], 0))
assert(subsetsum_rec([1,3,4], 4))
assert(subsetsum_rec([1,3,4], 1))
assert(subsetsum_rec([1,3,4], 8))
assert(not subsetsum_rec([1,3,4], 2))
assert(not subsetsum_rec([1,3,4], 9))
"OK"

Question 5

Écrire une fonction summable qui renvoie la liste croissante des nombres qu'on peut atteindre pour un ensemble de valeurs donné.

Corrigé 
def summable(values):
    s = sum(values)
    return [ k for k in range(s+1) if subsetsum_rec(values, k) ]

Tests :

assert(summable([1,3,4]) == [0,1,3,4,5,7,8])
assert(summable([1,2,6,18]) == [0, 1, 2, 3, 6, 7, 8,
    9, 18, 19, 20, 21, 24, 25, 26, 27])
"OK"

Mémoïsation

Question 6

Écrire une fonction subsetsum_memo_aux telle que subsetsum_memo_aux(values, target, i, cache) renvoie un booléen indiquant si le nombre target peut être atteint par un sous-ensemble de valeurs dans values d'indice \(\ge i\) en utilisant le dictionnaire cache pour mémoriser les valeurs des couples (target, i).

Corrigé 
def subsetsum_memo_aux(values, target, i, cache):
    if (target, i) in cache:
        return cache[(target, i)]
    if target == 0:
        b = True
    elif i >= len(values):
        b = False
    else:
        b = subsetsum_memo_aux(values, target, i+1, cache)
        if values[i] <= target:
            b = b or subsetsum_memo_aux(values, target-values[i], i+1, cache)
    cache[(target, i)] = b
    return b

Tests :

assert(subsetsum_memo_aux([1,3,4], 0, 0, {}))
assert(subsetsum_memo_aux([1,3,4], 4, 0, {}))
assert(subsetsum_memo_aux([1,3,4], 1, 0, {}))
assert(subsetsum_memo_aux([1,3,4], 8, 0, {}))
assert(not subsetsum_memo_aux([1,3,4], 2, 0, {}))
assert(not subsetsum_memo_aux([1,3,4], 9, 0, {}))
assert(not subsetsum_memo_aux([ 2*i for i in range(100) ], 265, 0, {}))
"OK"

Question 7

Écrire une fonction subsetsum_memo telle que subsetsum_memo(values, target) renvoie le booléen indiquant si target peut être écrit comme la somme d'un sous-ensemble des valeurs dans values en utilisant subsetsum_memo_aux.

Corrigé 
def subsetsum_memo(values, target):
    return subsetsum_memo_aux(values, target, 0, {})

Tests :

assert(subsetsum_memo([1,3,4], 0))
assert(subsetsum_memo([1,3,4], 4))
assert(subsetsum_memo([1,3,4], 1))
assert(subsetsum_memo([1,3,4], 8))
assert(not subsetsum_memo([1,3,4], 2))
assert(not subsetsum_memo([1,3,4], 9))
assert(not subsetsum_memo([ 2*i for i in range(100) ], 265))
"OK"

Tabulation

Pour résoudre ce problème par tabulation, on va devoir utiliser des matrices.

Question 8

Écrire une fonction matrix telle que matrix(n, m, v) renvoie une matrice, i.e. un tableau de tableaux, de n tableaux de m valeurs v.

Par exemple, matrix(3, 2, 0) doit renvoyer [[0,0],[0,0],[0,0]].

Corrigé 
def matrix(n,m,v):
    mat = []
    for i in range(n):
        mat.append([v] * m)
    return mat

Tests :

assert(matrix(2,3,0) == [[0,0,0],[0,0,0]])
assert(matrix(3,2,0) == [[0,0],[0,0],[0,0]])
assert(matrix(1,1,'a') == [['a']])
m = matrix(2,2,0)
m[0][0] = 1
assert(m == [[1,0],[0,0]])
"OK"

Question 9

Écrire une fonction subsetsum_tab telle que subsetsum_tab(values, target) renvoie le booléen indiquant si target peut être écrit comme la somme d'un sous-ensemble des valeurs dans values en utilisant une matrice de booléens pour tabuler.

Corrigé

Ici b[i][t] indique si t peut être atteint avec les valeurs d'indice \(\ge i\).

def subsetsum_tab(values, target):
    n = len(values)
    b = matrix(n+1, target+1, False)
    b[n][0] = True
    for i in reversed(range(n)):
        b[i][0] = True
        for t in range(1, target+1):
            b[i][t] = b[i+1][t]
            if t >= values[i]:
                b[i][t] = b[i][t] or b[i+1][t-values[i]]
    return b[0][target]

Tests :

assert(subsetsum_tab([1,3,4], 0))
assert(subsetsum_tab([1,3,4], 4))
assert(subsetsum_tab([1,3,4], 1))
assert(subsetsum_tab([1,3,4], 8))
assert(not subsetsum_tab([1,3,4], 2))
assert(not subsetsum_tab([1,3,4], 9))
assert(not subsetsum_tab([ 2*i for i in range(100) ], 265))
"OK"

Si on a \(n\) valeurs et une cible \(T\), l'algorithme tabulé utilise \(O(nT)\) espace mémoire pour la table et la même complexité en temps pour la remplir. On a donc un algorithme qui est polynomial en \(n\) pour résoudre SUBSET-SUM, P = NP et je vais aller empocher le million de dollars de l'institut Clay.

Question 10

So long 👋

ou pas ?

Corrigé

Ce n'est pas une complexité polynomiale en la taille de l'entrée : l'entier \(T\) est représenté sur environ \(\log_2 T\) bits, et \(T\) est donc exponentiel en sa taille. Avec des valeurs et une cible de l'ordre de \(2^{n}\), la table a \(n 2^n\) cases. On dit que l'algorithme est pseudo-polynomial : il n'est efficace que lorsque \(T\) reste petit.

Questions annexes

Question 11

À l'aide de ces fonctions, déterminer le plus petit nombre qui ne soit pas la somme d'un sous-ensemble de l'ensemble de valeurs \(\{1, 2, 3, 5, 7, \dots, 97\}\) constitué des nombres premiers plus petits que 100 et de 1.

Note : comme l'ensemble de valeurs ne change pas, il est sûrement plus efficace de conserver un unique cache ou de reprendre la tabulation pour conserver la table.

Question 12

Reprendre la fonction subsetsum_tab pour qu'elle renvoie un sous-ensemble dans le cas où la cible peut être écrite comme une somme, et None sinon.

Note : on pourra utiliser une matrice indiquant à l'indice \((i,t)\) si on utilise la \(i\)-ème valeur dans la décomposition de \(t\).

Corrigé

On reconstruit en partant de \((0, T)\) : si dec[i][v] est vrai, on prend values[i] et on continue avec v - values[i]. On maintient ainsi l'invariant « b[i][v] est vrai », ce qui garantit qu'on termine avec v nul.

def subsetsum_tab(values, target):
    n = len(values)
    b = matrix(n+1, target+1, False)
    dec = matrix(n+1, target+1, False)
    b[n][0] = True
    for i in reversed(range(n)):
        b[i][0] = True
        for t in range(1, target+1):
            b[i][t] = b[i+1][t]
            if t >= values[i]:
                b[i][t] = b[i][t] or b[i+1][t-values[i]]
                if b[i+1][t-values[i]]:
                    dec[i][t] = True
    if not b[0][target]:
        return None
    v = target
    subset = []
    for i in range(n):
        if dec[i][v]:
            subset.append(values[i])
            v = v-values[i]
    return subset

Question 13

Si la liste de valeurs est en ordre croissant, que peut-on dire du cardinal du sous-ensemble renvoyé ?

Distance d'édition

Étant donné deux chaînes de caractères \(A\) et \(B\) de longueurs respectives \(n\) et \(m\), on veut transformer la chaîne \(A\) en la chaîne \(B\) en effectuant un minimum d'opérations parmi celles-ci :

  • supprimer un caractère n'importe où ;
  • insérer un nouveau caractère n'importe où ;
  • changer un caractère en n'importe quel autre.

Ce nombre d'opérations est appelé la distance d'édition de \(A\) à \(B\).

Par exemple : chien \(\rightarrow\) chen \(\rightarrow\) chan \(\rightarrow\) chat

Question 14

Appliquer la méthodologie de la programmation dynamique pour calculer cette distance efficacement.

Question 15

En déduire une fonction renvoyant une suite de chaînes de longueur minimale pour passer d'une chaîne à une autre.

Exemple : pour chien et chat on obtiendra ['chien', 'chen', 'chan', 'chat'].