2.2 Complexité des Problèmes
55
© Dunod – Toute reproduction non autorisée est un délit.
Nous allons montrer que cet algorithme très simple possède une garantie relative
de performance.
Les boîtes étant de capacité A, une solution optimale vérifie C* $
1
A a
n
i 51
a i ,
car chaque objet est placé dans une boîte. Maintenant nous montrons une propriété
de l’algorithme : à toute étape de l’exécution de l’algorithme, il est impossible que
deux boîtes aient leur contenu inférieur ou égal à
A
2
: en effet, si tel était le cas, les
objets placés dans l’une de ces deux boîtes auraient du être placés dans l’autre boîte.
Ainsi, lorsque l’exécution de l’algorithme est achevée, au plus une boîte peut avoir
un contenu inférieur ou égal à
A
2
, les C 2 1 autres boîtes ayant un contenu supérieur
à
A
2
, nous avons ainsi :
C 2 1
2
,
1
A a
n
i 51
a i . En regroupant les inégalités, nous obtenons :
C 2 1
2
,
1
A a
n
i 51
a i # C* ; alors en divisant chaque membre par C il vient :
1
2
2
1
2C
#
C*
C
et, C et C* étant entiers :
1
2
#
C*
C
, soit
C
C*
# 2.
Dans l’exemple, au pire le nombre d’étagères achetées sera toujours inférieur au
double du nombre minimal. En fait, on peut montrer que le rapport d’approximation
de cet, algorithme est de l’ordre de 1, 7.
L’algorithme est de complexité polynomiale, nous avons donc un algorithme
polynomial avec une garantie relative de performance pour le problème du bin
packing (ce problème étant NP-difficile, il n’existe pas d’algorithme polynomial
pour le résoudre exactement sauf si P 5 NP).
Le lecteur pourra également se référer au chapitre 4, à la fin du paragraphe 10 de
cet ouvrage où un deuxième algorithme polynomial avec une garantie relative de
performance pour le problème du bin packing est présenté.
Les métaheuristiques
Les métaheuristiques les plus fréquemment utilisées pour fournir des solutions
approchées à des problèmes NP-difficiles ont pour principal attrait d’être suffisamment génériques pour s’adapter facilement à de nombreux problèmes. Si ces
heuristiques fournissent généralement assez rapidement des solutions approchées,
elles ne fournissent cependant aucune garantie sur l’écart entre le coût de la solution fournie et le coût d’une solution optimale. Des études statistiques faites sur les
métaheuristiques telles que le recuit simulé et la recherche “tabou” ont montré, pour
certains types de problèmes, la bonne qualité des solutions obtenues. Le recuit simulé
et la recherche tabou sont deux méthodes de voisinage : c’est-à-dire des méthodes
dans lesquelles, à chaque itération, à partir d’une solution courante S, un voisinage
V(S) de cette solution est déterminé. Ensuite, une nouvelle solution S’ appartenant à
ce voisinage V(S) est choisie, suivant un critère probabiliste. Contrairement aux classiques méthodes dites “de descente”, la nouvelle solution courante S’ peut être de
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
55
© Dunod – Toute reproduction non autorisée est un délit.
Nous allons montrer que cet algorithme très simple possède une garantie relative
de performance.
Les boîtes étant de capacité A, une solution optimale vérifie C* $
1
A a
n
i 51
a i ,
car chaque objet est placé dans une boîte. Maintenant nous montrons une propriété
de l’algorithme : à toute étape de l’exécution de l’algorithme, il est impossible que
deux boîtes aient leur contenu inférieur ou égal à
A
2
: en effet, si tel était le cas, les
objets placés dans l’une de ces deux boîtes auraient du être placés dans l’autre boîte.
Ainsi, lorsque l’exécution de l’algorithme est achevée, au plus une boîte peut avoir
un contenu inférieur ou égal à
A
2
, les C 2 1 autres boîtes ayant un contenu supérieur
à
A
2
, nous avons ainsi :
C 2 1
2
,
1
A a
n
i 51
a i . En regroupant les inégalités, nous obtenons :
C 2 1
2
,
1
A a
n
i 51
a i # C* ; alors en divisant chaque membre par C il vient :
1
2
2
1
2C
#
C*
C
et, C et C* étant entiers :
1
2
#
C*
C
, soit
C
C*
# 2.
Dans l’exemple, au pire le nombre d’étagères achetées sera toujours inférieur au
double du nombre minimal. En fait, on peut montrer que le rapport d’approximation
de cet, algorithme est de l’ordre de 1, 7.
L’algorithme est de complexité polynomiale, nous avons donc un algorithme
polynomial avec une garantie relative de performance pour le problème du bin
packing (ce problème étant NP-difficile, il n’existe pas d’algorithme polynomial
pour le résoudre exactement sauf si P 5 NP).
Le lecteur pourra également se référer au chapitre 4, à la fin du paragraphe 10 de
cet ouvrage où un deuxième algorithme polynomial avec une garantie relative de
performance pour le problème du bin packing est présenté.
Les métaheuristiques
Les métaheuristiques les plus fréquemment utilisées pour fournir des solutions
approchées à des problèmes NP-difficiles ont pour principal attrait d’être suffisamment génériques pour s’adapter facilement à de nombreux problèmes. Si ces
heuristiques fournissent généralement assez rapidement des solutions approchées,
elles ne fournissent cependant aucune garantie sur l’écart entre le coût de la solution fournie et le coût d’une solution optimale. Des études statistiques faites sur les
métaheuristiques telles que le recuit simulé et la recherche “tabou” ont montré, pour
certains types de problèmes, la bonne qualité des solutions obtenues. Le recuit simulé
et la recherche tabou sont deux méthodes de voisinage : c’est-à-dire des méthodes
dans lesquelles, à chaque itération, à partir d’une solution courante S, un voisinage
V(S) de cette solution est déterminé. Ensuite, une nouvelle solution S’ appartenant à
ce voisinage V(S) est choisie, suivant un critère probabiliste. Contrairement aux classiques méthodes dites “de descente”, la nouvelle solution courante S’ peut être de
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ