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 jmaxi0,k|sommepi>0.

Montrons que glouton(sommepj)j est de cardinal minimal, pour toute somme.

On pose xi=0kbipi où les bi sont donnés par l’algo glouton.

i=0kaipi : solution optimale

𝛼xbkpk,𝛼<pk

𝛼=i=0k1bipi : optimal, par HR.

𝛼=xbkpk=i=0k1aipi+(akbk)pk

Donc ak=bk, et (b0,,bk) est optimal.

NB : En fait, les bi 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 MS(v) de pièces permettant de rendre la valeur v dans le système de pièces S=(c1,,cn), 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 :

MS(v)=1+min1inMS(vci). 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

x1,,xn

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 [xi,xi+1]
  • on réitère avec le premier point hors du segment.

Il est optimal, car en notant z1,,zr=x1,xi2,,xir les points qui sont extrémité gauche d’un des segments crées par l’algo naïf.

Comme tous les zi 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(2n), puisque qu’on parcours l’ensemble des parties de 1,n (pour déterminer si chacune à une valeur convenable ou non).

M2

w   w1   wn  
0 v1 vn
T(i)={OU:T(iw1)+v1OU:T(iwn)+vn

⟶ 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=maxi(vi), la complexité :

  • en mémoire est en O(W×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(2n)

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