4.10 Recherches arbo res centes
171
© Dunod – Toute reproduction non autorisée est un délit.
met de l’arbo res cence S i . Au contraire, E(S i ) doit être un mino rant de cette valeur dans
un pro blème de minimi sa tion (comme dans l’algorithme de Little et al.).
• Si l’éva
lua tion E(S i ) d’un som met est infé rieure (pour un pro blème de maxi mi -
sa tion, supérieure pour un pro blème de minimi sa tion) à la valeur d’une solu tion
connue du pro blème, le som met S i n’est pas exploré. Dans ce cas, S i ne peut pas
conte nir une solu tion meilleure que celle déjà obte nue.
• Lorsque pour un som met S i la (ou l’une des) meilleure(s) solu tion(s) de l’ensemble
cor res pon dant est obte nue ou bien s’il appa raît que S i ne contient pas de solu tion,
l’explo ra tion de S i est ter mi née et S i n’a pas de suc ces seur dans l’arbo res cence.
• Sépa ra tion. Lorsque l’on n’est pas dans le cas pré cé dent, l’ensemble S i est séparé
en plusieurs sous- ensembles non vides, chacun comportant moins de solutions que
S i , tels que toute solu tion admis sible conte nue dans S i soit conte nue dans l’un de ces
sous- ensembles. Les suc ces seurs de S i dans l’arbo res cence sont les som mets cor res -
pon dant à ces ensembles.
Une stra té gie de par cours de l’arbo res cence doit être adop tée. Les stra té gies les
plus cou ram ment uti li sées sont soit un par cours en pro fon deur d’abord ou “S.E.S” (cf.
cha pitre 3), soit un par cours où le som met à explo rer en priorité est celui (ou l’un de
ceux) pos sé dant la meilleure éva lua tion parmi ceux non encore explo rés, ou “S.E.P”.
Les prin
cipes de sépa ra tion et d’éva lua tion dépendent du pro blème traité. L’effi
ca cité de la méthode dépend for te ment des prin cipes uti li sés. En pra tique, on consi -
dé rera comme de « bonnes » éva lua tions, des éva lua tions rapides à obte nir et dont
l’écart avec la solu tion opti male du sous- problème asso cié au som met S i consi déré
est petit. Par ailleurs, le déve lop pe ment d’une heu ris tique rapide per met tant d’obte -
nir une bonne solu tion appro chée au pro blème est géné ra
le ment néces saire à l’effi
ca
cité de la méthode. En effet, plus petit est l’écart entre l’éva lua tion d’un ensemble de
solu tions et la valeur d’une solu tion admis sible connue, plus grandes sont les pos si -
bi li tés d’arrê ter après peu d’étapes (sépa ra tions) l’explo ra tion du som met consi déré
et plus rapide sera la résolution du problème.
Pro blème du sac à dos (knapsack)
Le pro blème nommé sac à dos ou encore knapsack est l’un des pro blèmes les plus
clas siques de la recherche opé ra tion nelle. Il peut se pré sen ter in for mel lement de la
façon sui vante. Un ran don neur dis pose d’un sac à dos de volume B ; il a devant lui n
objets cha cun de volume donné a i ; cha cun de ces objets a une uti lité que le ran don -
neur note c i , c i étant un nombre entier posi tif ; le volume cumulé des n objets étant
supé rieur au volume du sac, le ran don neur devra choi sir parmi les objets ceux qu’il
empor tera ; son objec tif est de maxi mi ser la somme des uti li tés des objets empor tés.
Le pro blème se for ma lise de la manière sui vante :
max a
n
i 51
c i x i
a
n
i 51
a i x i < B
x i H 50, 16, 1 < i < n.
µ
171
© Dunod – Toute reproduction non autorisée est un délit.
met de l’arbo res cence S i . Au contraire, E(S i ) doit être un mino rant de cette valeur dans
un pro blème de minimi sa tion (comme dans l’algorithme de Little et al.).
• Si l’éva
lua tion E(S i ) d’un som met est infé rieure (pour un pro blème de maxi mi -
sa tion, supérieure pour un pro blème de minimi sa tion) à la valeur d’une solu tion
connue du pro blème, le som met S i n’est pas exploré. Dans ce cas, S i ne peut pas
conte nir une solu tion meilleure que celle déjà obte nue.
• Lorsque pour un som met S i la (ou l’une des) meilleure(s) solu tion(s) de l’ensemble
cor res pon dant est obte nue ou bien s’il appa raît que S i ne contient pas de solu tion,
l’explo ra tion de S i est ter mi née et S i n’a pas de suc ces seur dans l’arbo res cence.
• Sépa ra tion. Lorsque l’on n’est pas dans le cas pré cé dent, l’ensemble S i est séparé
en plusieurs sous- ensembles non vides, chacun comportant moins de solutions que
S i , tels que toute solu tion admis sible conte nue dans S i soit conte nue dans l’un de ces
sous- ensembles. Les suc ces seurs de S i dans l’arbo res cence sont les som mets cor res -
pon dant à ces ensembles.
Une stra té gie de par cours de l’arbo res cence doit être adop tée. Les stra té gies les
plus cou ram ment uti li sées sont soit un par cours en pro fon deur d’abord ou “S.E.S” (cf.
cha pitre 3), soit un par cours où le som met à explo rer en priorité est celui (ou l’un de
ceux) pos sé dant la meilleure éva lua tion parmi ceux non encore explo rés, ou “S.E.P”.
Les prin
cipes de sépa ra tion et d’éva lua tion dépendent du pro blème traité. L’effi
ca cité de la méthode dépend for te ment des prin cipes uti li sés. En pra tique, on consi -
dé rera comme de « bonnes » éva lua tions, des éva lua tions rapides à obte nir et dont
l’écart avec la solu tion opti male du sous- problème asso cié au som met S i consi déré
est petit. Par ailleurs, le déve lop pe ment d’une heu ris tique rapide per met tant d’obte -
nir une bonne solu tion appro chée au pro blème est géné ra
le ment néces saire à l’effi
ca
cité de la méthode. En effet, plus petit est l’écart entre l’éva lua tion d’un ensemble de
solu tions et la valeur d’une solu tion admis sible connue, plus grandes sont les pos si -
bi li tés d’arrê ter après peu d’étapes (sépa ra tions) l’explo ra tion du som met consi déré
et plus rapide sera la résolution du problème.
Pro blème du sac à dos (knapsack)
Le pro blème nommé sac à dos ou encore knapsack est l’un des pro blèmes les plus
clas siques de la recherche opé ra tion nelle. Il peut se pré sen ter in for mel lement de la
façon sui vante. Un ran don neur dis pose d’un sac à dos de volume B ; il a devant lui n
objets cha cun de volume donné a i ; cha cun de ces objets a une uti lité que le ran don -
neur note c i , c i étant un nombre entier posi tif ; le volume cumulé des n objets étant
supé rieur au volume du sac, le ran don neur devra choi sir parmi les objets ceux qu’il
empor tera ; son objec tif est de maxi mi ser la somme des uti li tés des objets empor tés.
Le pro blème se for ma lise de la manière sui vante :
max a
n
i 51
c i x i
a
n
i 51
a i x i < B
x i H 50, 16, 1 < i < n.
µ