4.10 Recherches arbo res centes
163
© Dunod – Toute reproduction non autorisée est un délit.
Remarque 2 L’heu ris tique de Balas- Hammer a fourni ici une solu tion de coût
3 535, très voi sin du coût opti mal 3 529 : ceci en illustre la qua lité…
4.10 recherches Arbo res centes
4.10.1 Pro blème du voya geur de com merce
Ima gi nons un voya geur de com merce qui doit visi ter de nom breuses villes (cha cune
une fois et une seule) et reve nir à son point de départ. Si l’on dis pose de la matrice
des coûts de tran sport de ville à ville (qu’on pourra sup po ser non symé trique pour
cor ser le pro blème), le voya geur de com merce recherche un cir cuit hamiltonien de
valeur mini male.
Pen dant de longues années, de nom breux chercheurs ont tenté d’inven ter un algo -
rithme conduisant à l’optimum de ce pro blème (NPdifficile) ; on n’en trou vait pas et
l’on n’était pas cer tain de la vali dité des solu tions ingé nieuses pro po sées par les uns
et les autres pour des exemples numé riques rela ti ve ment impor tants pour l’époque,
modestes aujourd’hui... (entre 40 et 50 villes). Bien entendu, ces solu tions étaient
obte nues à l’aide d’heu ris tiques, car il n’était pas ques tion d’énu mé rer les 1 n 2 12 !
cir cuits pos sibles. C’est alors que Little et al. (1963) ont appli qué au pro blème une
pro cé dure de recherche arbo res cente, qui a per mis d’obte nir des solu tions opti males,
mais en des temps de cal cul par fois assez long.
De nom breux per fec tion ne ments sont appor tés conti nuel le ment à des méthodes
de ce type, qui sortent du cadre de cet ouvrage ; on résout désormais, optimalement,
des problèmes dépassant le millier de villes.
En fait de recherches arbo res centes, nous trai tons ici d’abord l’exemple du voya geur
de com merce (mais sans abor der la conver gence et la finitude de la méthode employée).
Signa lons, que les ini tiales SEP., très employées en France pour carac té ri ser la
classe des méthodes arborescentes mises au point, en 1964-65, par B. Roy et son
équipe, signi fient « Sépa
ra tion et Eva lua
tion Pro gres
sives ». Nous allons jus
te
ment don ner un exemple d’un prin cipe de sépa ra tion dicho to mique, consis tant à
aug men ter ou non un ensemble d’un élé ment, en mesu rant l’effi ca cité de l’une ou
de l’autre déci sion par l’éva lua tion de la borne infé rieure d’un coût. Tan dis que les
ini tiales SES : « Sépa ra tion et Eva lua tion Séquen tielle » cor res pondent à une stra -
té gie de par cours en pro fon deur d’abord (cf. cha pitre 3) ; la méthode boo léenne de
Faure et Malgrange (1962) employait déjà impli ci te ment cette stra té gie (elle est
décrite en fin de cha
pitre 1).
Pour évi ter des lon gueurs, l’exemple choisi, à n 5 5 villes, sera celui d’un
voya geur de com merce demeu rant dans la ville A et dési reux de se rendre une fois
et une seule dans les villes B, C, D, Ε et F, avant de reve nir chez lui. La matrice
des coûts est don née ci après (les tirets rem placent des valeurs infi nies) ; il s’agit
évi dem ment de déter mi ner, parmi les 1 n 2 12 ! 5 120 cir cuits hamiltoniens, celui
de valeur mini male. L’énumération exhaustive de 1 n 2 12 ! est impraticable dès
que n . 15 ou 20 (cf chapitre 2).
163
© Dunod – Toute reproduction non autorisée est un délit.
Remarque 2 L’heu ris tique de Balas- Hammer a fourni ici une solu tion de coût
3 535, très voi sin du coût opti mal 3 529 : ceci en illustre la qua lité…
4.10 recherches Arbo res centes
4.10.1 Pro blème du voya geur de com merce
Ima gi nons un voya geur de com merce qui doit visi ter de nom breuses villes (cha cune
une fois et une seule) et reve nir à son point de départ. Si l’on dis pose de la matrice
des coûts de tran sport de ville à ville (qu’on pourra sup po ser non symé trique pour
cor ser le pro blème), le voya geur de com merce recherche un cir cuit hamiltonien de
valeur mini male.
Pen dant de longues années, de nom breux chercheurs ont tenté d’inven ter un algo -
rithme conduisant à l’optimum de ce pro blème (NPdifficile) ; on n’en trou vait pas et
l’on n’était pas cer tain de la vali dité des solu tions ingé nieuses pro po sées par les uns
et les autres pour des exemples numé riques rela ti ve ment impor tants pour l’époque,
modestes aujourd’hui... (entre 40 et 50 villes). Bien entendu, ces solu tions étaient
obte nues à l’aide d’heu ris tiques, car il n’était pas ques tion d’énu mé rer les 1 n 2 12 !
cir cuits pos sibles. C’est alors que Little et al. (1963) ont appli qué au pro blème une
pro cé dure de recherche arbo res cente, qui a per mis d’obte nir des solu tions opti males,
mais en des temps de cal cul par fois assez long.
De nom breux per fec tion ne ments sont appor tés conti nuel le ment à des méthodes
de ce type, qui sortent du cadre de cet ouvrage ; on résout désormais, optimalement,
des problèmes dépassant le millier de villes.
En fait de recherches arbo res centes, nous trai tons ici d’abord l’exemple du voya geur
de com merce (mais sans abor der la conver gence et la finitude de la méthode employée).
Signa lons, que les ini tiales SEP., très employées en France pour carac té ri ser la
classe des méthodes arborescentes mises au point, en 1964-65, par B. Roy et son
équipe, signi fient « Sépa
ra tion et Eva lua
tion Pro gres
sives ». Nous allons jus
te
ment don ner un exemple d’un prin cipe de sépa ra tion dicho to mique, consis tant à
aug men ter ou non un ensemble d’un élé ment, en mesu rant l’effi ca cité de l’une ou
de l’autre déci sion par l’éva lua tion de la borne infé rieure d’un coût. Tan dis que les
ini tiales SES : « Sépa ra tion et Eva lua tion Séquen tielle » cor res pondent à une stra -
té gie de par cours en pro fon deur d’abord (cf. cha pitre 3) ; la méthode boo léenne de
Faure et Malgrange (1962) employait déjà impli ci te ment cette stra té gie (elle est
décrite en fin de cha
pitre 1).
Pour évi ter des lon gueurs, l’exemple choisi, à n 5 5 villes, sera celui d’un
voya geur de com merce demeu rant dans la ville A et dési reux de se rendre une fois
et une seule dans les villes B, C, D, Ε et F, avant de reve nir chez lui. La matrice
des coûts est don née ci après (les tirets rem placent des valeurs infi nies) ; il s’agit
évi dem ment de déter mi ner, parmi les 1 n 2 12 ! 5 120 cir cuits hamiltoniens, celui
de valeur mini male. L’énumération exhaustive de 1 n 2 12 ! est impraticable dès
que n . 15 ou 20 (cf chapitre 2).