Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
170
pla cés dans une même boîte ne doit pas être supé rieure à la taille de la boîte). Un algo rithme
glou ton four nis sant une solu tion appro chée au pro blème est le sui vant : ini tia le ment, les
objets sont triés par taille décrois sante : a 1 > a 2 > c > a i > a i 1 1 > c > a n ; les
objets sont pla cés un à un, sui vant l’ordre résul tant du tri effec tué, dans la pre mière boîte
pou vant les conte nir ; si aucune boîte déjà utilisée ne peut conte nir un objet, l’objet est
placé dans une boîte vide. Le mathéma ti cien amé ri cain D. Johnson a mon tré que, pour
toute ins tance du pro blème de bin packing, en notant c H le nombre de boîtes uti li sées
par une solu tion four nie par l’algo rithme pré cé dent et c
*
le nombre de boîtes uti li sées
dans une solu
tion opti male, la garan tie rela tive de per for mance de l’algo rithme véri fie :
c H /c
* <
11
9
. Ainsi en uti li sant l’heu ris tique gour mande pro po sée pour résoudre ce pro -
blème, nous sommes assu rés que le nombre de boîtes uti li sées n’excède, dans le pire des
cas, que de 22,3 % le nombre minimal de boîtes néces saires.
Le lec teur inté ressé par ce sujet pourra consul ter l’ouvrage [11] entiè re ment
dédié à l’approxi
ma tion des pro
blèmes algorithmiquement dif
fi ciles.
Après avoir intro duit la notion de recherche arbo res cente en résol vant par l’algo -
rithme de Little et al. le pro blème du voya geur de com merce (pra ti cable pour des ins -
tances ayant moins d’une cen taine de villes), nous pré ci sons main te nant cette notion et
l’appli quons à deux autres pro blèmes. Le pro blème du sac à dos et la pro gram ma tion
linéaire en nombres entiers (ce der nier pro blème, déjà ren contré au cha pitre 1, est
repris ulté rieu re ment dans le cha pitre 8 consa cré à la pro gram ma tion linéaire).
4.10.2 Recherches arbo res centes par sépa ra tion
et éva lua tion
Nous allons main te nant pré sen ter une méthode géné rale per met tant la réso lu tion
des pro blèmes d’opti mi sation NP
difficiles. Nous avons déjà signalé que seules des
méthodes énu mé ra tives (qu’on souhaite le moins exhaustives possible) sont à même
de résoudre ces pro blèmes : la méthode décrite ici a pour objec tif de mener à bien
l’énu mé ra tion des solu tions réa li sables du pro blème traité en essayant d’évi ter le
plus pos sible l’énu mé ra tion expli cite de cet ensemble.
Dans cet ouvrage, cette méthode est illus trée à tra vers trois exemples très clas -
siques de la recherche opé ra tion nelle. Deux de ces exemples ayant pour cadre la
pro gram ma tion linéaire en nombres entiers sont situés plus bas dans ce para graphe ;
le troi sième, l’algo rithme dû à Little et al., résol vant le pro blème du voya geur de
com merce vient d’être pré senté, a servi d’introduction pour ce paragraphe.
Le prin cipe de la méthode est le sui vant :
• Une arbo res cence est déve lop pée au cours de l’algo rithme. Chaque som met de
cette arbo res cence cor res pond à un sous- ensemble de solu tions admis sibles (on
dit aussi : réa li sables) du pro blème ; la racine de l’arbo res cence cor res pon dant à
l’ensemble de toutes les solu tions réa li sables.
• Éva lua tion. Pour cha cun des som mets S i , une valeur E(S i ) appe lée éva lua tion du
som met, est cal cu lée via, le plus sou vent, une fonc tion appe lée fonc tion d’éva lua tion.
Pour un pro blème de maxi mi sa tion, cette valeur E(S i ) doit être un majo rant de la valeur
de la meilleure solu tion conte nue dans l’ensemble des solu tions cor res pon dant au som -
170
pla cés dans une même boîte ne doit pas être supé rieure à la taille de la boîte). Un algo rithme
glou ton four nis sant une solu tion appro chée au pro blème est le sui vant : ini tia le ment, les
objets sont triés par taille décrois sante : a 1 > a 2 > c > a i > a i 1 1 > c > a n ; les
objets sont pla cés un à un, sui vant l’ordre résul tant du tri effec tué, dans la pre mière boîte
pou vant les conte nir ; si aucune boîte déjà utilisée ne peut conte nir un objet, l’objet est
placé dans une boîte vide. Le mathéma ti cien amé ri cain D. Johnson a mon tré que, pour
toute ins tance du pro blème de bin packing, en notant c H le nombre de boîtes uti li sées
par une solu tion four nie par l’algo rithme pré cé dent et c
*
le nombre de boîtes uti li sées
dans une solu
tion opti male, la garan tie rela tive de per for mance de l’algo rithme véri fie :
c H /c
* <
11
9
. Ainsi en uti li sant l’heu ris tique gour mande pro po sée pour résoudre ce pro -
blème, nous sommes assu rés que le nombre de boîtes uti li sées n’excède, dans le pire des
cas, que de 22,3 % le nombre minimal de boîtes néces saires.
Le lec teur inté ressé par ce sujet pourra consul ter l’ouvrage [11] entiè re ment
dédié à l’approxi
ma tion des pro
blèmes algorithmiquement dif
fi ciles.
Après avoir intro duit la notion de recherche arbo res cente en résol vant par l’algo -
rithme de Little et al. le pro blème du voya geur de com merce (pra ti cable pour des ins -
tances ayant moins d’une cen taine de villes), nous pré ci sons main te nant cette notion et
l’appli quons à deux autres pro blèmes. Le pro blème du sac à dos et la pro gram ma tion
linéaire en nombres entiers (ce der nier pro blème, déjà ren contré au cha pitre 1, est
repris ulté rieu re ment dans le cha pitre 8 consa cré à la pro gram ma tion linéaire).
4.10.2 Recherches arbo res centes par sépa ra tion
et éva lua tion
Nous allons main te nant pré sen ter une méthode géné rale per met tant la réso lu tion
des pro blèmes d’opti mi sation NP
difficiles. Nous avons déjà signalé que seules des
méthodes énu mé ra tives (qu’on souhaite le moins exhaustives possible) sont à même
de résoudre ces pro blèmes : la méthode décrite ici a pour objec tif de mener à bien
l’énu mé ra tion des solu tions réa li sables du pro blème traité en essayant d’évi ter le
plus pos sible l’énu mé ra tion expli cite de cet ensemble.
Dans cet ouvrage, cette méthode est illus trée à tra vers trois exemples très clas -
siques de la recherche opé ra tion nelle. Deux de ces exemples ayant pour cadre la
pro gram ma tion linéaire en nombres entiers sont situés plus bas dans ce para graphe ;
le troi sième, l’algo rithme dû à Little et al., résol vant le pro blème du voya geur de
com merce vient d’être pré senté, a servi d’introduction pour ce paragraphe.
Le prin cipe de la méthode est le sui vant :
• Une arbo res cence est déve lop pée au cours de l’algo rithme. Chaque som met de
cette arbo res cence cor res pond à un sous- ensemble de solu tions admis sibles (on
dit aussi : réa li sables) du pro blème ; la racine de l’arbo res cence cor res pon dant à
l’ensemble de toutes les solu tions réa li sables.
• Éva lua tion. Pour cha cun des som mets S i , une valeur E(S i ) appe lée éva lua tion du
som met, est cal cu lée via, le plus sou vent, une fonc tion appe lée fonc tion d’éva lua tion.
Pour un pro blème de maxi mi sa tion, cette valeur E(S i ) doit être un majo rant de la valeur
de la meilleure solu tion conte nue dans l’ensemble des solu tions cor res pon dant au som -