178
Recherche opérationnelle
Le problème est résolu : en effet, le sous-ensemble
, donne
,
,
.
C'est donc un sous-ensemble terminal non vide. Comme il a une évaluation par excès
supérieure à celle relative au seul autre sommet pendant, on a trouvé l'optimum.
Il va sans dire que sur des problèmes plus riches en données, la procédure peut être plus
longue. Encore une fois, on n'a pas l'assurance de ne pas explorer l'ensemble des
combinaisons possibles ou en tout cas, une partie non négligeable de cet ensemble.
7.4.3.3. Choix des principes de séparation et d’évaluation
L'exposé d'une méthode telle que PSEP laisse une grande latitude pour le choix des
principes de séparation et d'évaluation. Pour arriver le plus possible à l'optimum, il
convient de procéder à ces choix avec circonspection : d'une part, il ne faut pas que le
principe de séparation ''éparpille'' trop les solutions voisines de l'optimum dans les sousensembles qu'il génère; d'autre part, il faut que le principe d'évaluation conduise
rapidement à l'élimination d'une proportion importante de sous-ensembles, c'est-à-dire
qu'apparaissent des sous-ensembles dont l'évaluation est supérieure au minimum de sur
E (ces sous-ensembles ne seront en effet jamais séparés); enfin, la règle de sélection
utilisée dans les PSEP est convenable si le biais qu'introduit l'évaluation par défaut est à
peu près le même sur tous les sous-ensembles candidats.
7.4.3.4. Problèmes de temps et de place en informatique
Les problèmes les plus importants relatifs aux procédures de recherche arborescente sont
d'ordre informatique; avant d'engager les calculs, on ne sait pas en effet combien
d'itérations vont être nécessaires; par ailleurs, le stockage en mémoire de toutes les
informations utiles concernant les sommets candidats peut poser des problèmes de temps
de gestion des périphériques.
Aussi, au lieu de rechercher l'optimum strict de sur , se contente-t-on souvent de
solutions non optimales, mais dont on a lieu de penser qu'elles ne sont pas trop éloignées
de l'optimum : les méthodes utilisées pour obtenir ces solutions satisfaisantes sont dites
heuristiques.
Nous les évoquons dans le chapitre suivant en commençant par un retour sur la notion de
complexité des algorithmes, notion qui justifie l'existence et l'usage de ces méthodes
approchées.
4
16/3
7
X2=0
X2=1
Recherche opérationnelle
Le problème est résolu : en effet, le sous-ensemble
, donne
,
,
.
C'est donc un sous-ensemble terminal non vide. Comme il a une évaluation par excès
supérieure à celle relative au seul autre sommet pendant, on a trouvé l'optimum.
Il va sans dire que sur des problèmes plus riches en données, la procédure peut être plus
longue. Encore une fois, on n'a pas l'assurance de ne pas explorer l'ensemble des
combinaisons possibles ou en tout cas, une partie non négligeable de cet ensemble.
7.4.3.3. Choix des principes de séparation et d’évaluation
L'exposé d'une méthode telle que PSEP laisse une grande latitude pour le choix des
principes de séparation et d'évaluation. Pour arriver le plus possible à l'optimum, il
convient de procéder à ces choix avec circonspection : d'une part, il ne faut pas que le
principe de séparation ''éparpille'' trop les solutions voisines de l'optimum dans les sousensembles qu'il génère; d'autre part, il faut que le principe d'évaluation conduise
rapidement à l'élimination d'une proportion importante de sous-ensembles, c'est-à-dire
qu'apparaissent des sous-ensembles dont l'évaluation est supérieure au minimum de sur
E (ces sous-ensembles ne seront en effet jamais séparés); enfin, la règle de sélection
utilisée dans les PSEP est convenable si le biais qu'introduit l'évaluation par défaut est à
peu près le même sur tous les sous-ensembles candidats.
7.4.3.4. Problèmes de temps et de place en informatique
Les problèmes les plus importants relatifs aux procédures de recherche arborescente sont
d'ordre informatique; avant d'engager les calculs, on ne sait pas en effet combien
d'itérations vont être nécessaires; par ailleurs, le stockage en mémoire de toutes les
informations utiles concernant les sommets candidats peut poser des problèmes de temps
de gestion des périphériques.
Aussi, au lieu de rechercher l'optimum strict de sur , se contente-t-on souvent de
solutions non optimales, mais dont on a lieu de penser qu'elles ne sont pas trop éloignées
de l'optimum : les méthodes utilisées pour obtenir ces solutions satisfaisantes sont dites
heuristiques.
Nous les évoquons dans le chapitre suivant en commençant par un retour sur la notion de
complexité des algorithmes, notion qui justifie l'existence et l'usage de ces méthodes
approchées.
4
16/3
7
X2=0
X2=1