TD5 : Algorithmes gloutons, Programmation dynamique (problème du sac à dos)

Énoncé

TD 5

EX 1

1)

p = 5
k = 3
def glouton(somme):
  global p
  global k
  for j in range(k,-1,-1):
    if (somme - p**j>0):
      g = glouton(somme - p**j)
      g.append(p**j)
      return g
  else:
    return [1]

print(glouton(17))

Par récurrence sur $k$, montrons que $glouton$ est optimal :

  • Pour $k = 0$ : c’est clair
  • Pour $k>0$ : soit $j ≝ \max {i ∈ ⟦0,k⟧ \vert somme - p^i > 0 } ≠ ∅$.

Montrons que $glouton(somme - p^j) ∪ {j}$ est de cardinal minimal, pour toute $somme$.

On pose \(x ≝ \sum_{i=0}^k b_i p^i\) où les $b_i$ sont donnés par l’algo glouton.

$\sum\limits_{i=0}^k a_i p^i$ : solution optimale

\[𝛼 ≝ x - b_k p^k, 𝛼<p^k\]

\(𝛼 = \sum\limits_{i=0}^{k-1} b_i p^i\) : optimal, par HR.

\[𝛼 = x-b_k p^k = \sum\limits_{i=0}^{k-1} a_i p^i + (a_k - b_k)p^k\]

Donc $a_k = b_k$, et $(b_0, ⋯, b_k)$ est optimal.

NB : En fait, les $b_i$ sont les coefficients de la $somme$ écrite en base $p$, en moins de $k$ chiffres.

2) Dans le système $(1,3,4)$ : $6=4+1+1$, pourtant $3+3$ est meilleur.

3)

Donnée : M

for i=2 to M do
  min (
    for j = 1 to k do
      T[i-Pj]
    )
  T[i] <- T1

Programmation dynamique : Un moyen conceptuellement simple de trouver le nombre $M_S(v)$ de pièces permettant de rendre la valeur $v$ dans le système de pièces $S=(c_1,\ldots,c_n)$, est la programmation dynamique. En effet, supposons qu’on sache rendre de façon optimale toutes les valeurs strictement inférieure à $v$. Pour rendre $v$, il faut au moins une pièce, à prendre parmi $n$ possibles. Une fois choisie cette pièce, la somme restante inférieure strictement à $v$, donc on sait la rendre de façon optimale. Il suffit donc d’essayer les $n$ possibilités :

$M_S(v)=1+\min_{1\leq i\leq n} M_S(v-c_i).$ Le nombre de calculs à effectuer est proportionnel à $v$, donc exponentiel en la taille de $v$.

BFS : Un Arbre enraciné peut être construit. Sa racine est la somme à rendre. Un nœud représente une somme intermédiaire. Les fils d’un nœud correspondent aux sommes restant à rendre selon la dernière pièce rendue (chaque pièce correspondant à une couleur d’arête attitrée).

La construction de l’arbre se fait en BFS, c’est-à-dire qu’on calcule les fils de tous les nœuds d’un niveau avant de passer au niveau suivant, et on s’arrête dès qu’un nœud 0 est trouvé : le chemin allant de la racine à ce nœud permet de rendre la monnaie avec un minimum de pièces.

EX 2

${x_1, ⋯, x_n}$

Algo naïf :

  • on trie par ordre croissant
    • si ils sont sur une droite en dimension $n$ : on les trie par ordre lexicographique.
  • on prend le segment $[x_i, x_{i+1}]$
  • on réitère avec le premier point hors du segment.

Il est optimal, car en notant $z_1, ⋯, z_r = x_1, x_{i_2}, ⋯, x_{i_r}$ les points qui sont extrémité gauche d’un des segments crées par l’algo naïf.

Comme tous les $z_i$ sont à distance strictement plus grande que $1$ les uns des autres, ils sont dans des segments différents pour toute solution optimale, laquelle crée donc au moins autant de segments que l’algo naïf.

EX 3

1)

Algo hyper naïf : on considère l’ensemble des parties convenables : les parties $P∈𝒫(⟦1,n⟧)$ dont le poids (= la somme des poids de ses éléments) est inférieur à $n$ : on y cherche la partie qui maximise la fonction “valeur” (=somme des valeurs des éléments).

Complexité: en $O(2^n)$, puisque qu’on parcours l’ensemble des parties de $⟦1,n⟧$ (pour déterminer si chacune à une valeur convenable ou non).

M2

$w$   $w_1$   $w_n$  
$0$ ⋯ $v_1$ ⋯ $v_n$ ⋯
\[T(i) = \begin{cases} OU : T(i-w_1) + v_1 \\ \vdots \\ OU : T(i-w_n) + v_n \\ \end{cases}\]

⟶ le max.

T : tableau de taille W+1
∀i∈⟦0,n⟧, T[i]=0

Pour i=1 à W:
  Pour k=1 à n:
    Si (i-w_k)≥0:
      T[i] ⟵ max(T[i], v_k + T[i-w_k])
Retourne T[W]

Invariant : pour tout $i$, $T[i]$ est la récompense maixmale pour un sac à dos de taille $i$.

Complexité : En posant $M=\max_i (v_i)$, la complexité :

  • en mémoire est en $O(W\times \log(nM))$
  • temporelle : $O(Wn)$

NB : on peut aussi ne mettre qu’une fois un élément, en retenant dans un array ceux qui ont déjà été mis.

Pq NP-complet ?: car la complexité est mesurée en fonction de la taille de l’entrée : i.e en unaire ⟹ $O(Wn)$ est exponentiel par rapport à $O(\log(W))$ (nb de chiffres de l’entrée = taille de l’entrée).

2)

L’ensemble des parties convenable est $𝒫(⟦1,n⟧)$.

Complexité : comme on parcourt $𝒫(⟦1,n⟧)$ (pour chercher la partie en laquelle le maximum de la fonction “valeur pondérée” est atteint), $C = O(2^n)$

M2

On trie les éléments par ordre décroissant de rapport qualité/prix, et on les place les uns après les autres : arrivé à la fin, on met une fraction adéquate de l’élément à placer.

T[n], S, j, P, b
for i=1 to n :
  T[i] ⟵ (v_i/w_i, w_i)
trier(T)
i=1
while(i≤n and b)
  if T[i][1]<W-P:
    S ⟵ T[i][0] × T[i][1] + S
    P ⟵ T[i][1] + P
    i++
  Sinon
    S ⟵ S + (W-P)×T[i][0]
    b ⟵ false

Leave a comment