Arbres et arborescences
173
de même niveau, on décrit l'arborescence suivant l'ordre de Tarry qui lui est
associé, en considérant que les sommets en cul-de-sacs sont les sommets
terminaux vides et les sommets terminaux non vides.
La procédure s'arrête lorsque toutes les évaluations de sommets non encore
séparés sont supérieures à la meilleure évaluation trouvée pour un sommet
terminal non vide : pour appliquer ce type de procédure, il faut donc déjà savoir
à peu près où se situera l'optimum pour organiser l'arborescence de façon à
exhumer assez vite les meilleures solutions.
- les PSEP (Procédures de Séparation et d'Evaluation Progressive) où le choix du
sommet à séparer se fonde sur la considération des évaluations des sommets
pendants (sur lesquels on a le choix). C'est le cas de la procédure que nous
avons utilisée pour résoudre notre exemple. Ces procédures sont souvent plus
pénibles à programmer que les précédentes mais, par les possibilités
d'orientation qu'une bonne fonction d'évaluation permet, elles sont plus souvent
appliquées. Nous fournirons donc dans le paragraphe suivant des précisions sur
les règles qu'elles mettent en jeu.
7.4.2.2. Les méthodes PSEP
Principe de base
Les conditions auxquelles doivent répondre les principes de séparation et d'évaluation
des méthodes PSEP sont les suivantes :
1) Principe de séparation :
Condition de finitude :
Si l'on prend un sous-ensemble, qu'on le sépare en sous-ensembles et que l'on sépare
encore ses sous-ensembles etc ... la suite obtenue est finie.
Condition de conservation
Soit
un sous-ensemble; la méthode de séparation donne des
avec
où
S(q) désigne l'ensemble des indices des sous-ensembles obtenus à partir de
(sousensembles ''descendants'' de ); on doit avoir :
Condition d'arrêt :
On n'aura pas à séparer un sous-ensemble
dans deux cas :
- il est vide,
- on peut calculer le minimum sur et l'élément ou les éléments correspondants.
est terminal non vide.
173
de même niveau, on décrit l'arborescence suivant l'ordre de Tarry qui lui est
associé, en considérant que les sommets en cul-de-sacs sont les sommets
terminaux vides et les sommets terminaux non vides.
La procédure s'arrête lorsque toutes les évaluations de sommets non encore
séparés sont supérieures à la meilleure évaluation trouvée pour un sommet
terminal non vide : pour appliquer ce type de procédure, il faut donc déjà savoir
à peu près où se situera l'optimum pour organiser l'arborescence de façon à
exhumer assez vite les meilleures solutions.
- les PSEP (Procédures de Séparation et d'Evaluation Progressive) où le choix du
sommet à séparer se fonde sur la considération des évaluations des sommets
pendants (sur lesquels on a le choix). C'est le cas de la procédure que nous
avons utilisée pour résoudre notre exemple. Ces procédures sont souvent plus
pénibles à programmer que les précédentes mais, par les possibilités
d'orientation qu'une bonne fonction d'évaluation permet, elles sont plus souvent
appliquées. Nous fournirons donc dans le paragraphe suivant des précisions sur
les règles qu'elles mettent en jeu.
7.4.2.2. Les méthodes PSEP
Principe de base
Les conditions auxquelles doivent répondre les principes de séparation et d'évaluation
des méthodes PSEP sont les suivantes :
1) Principe de séparation :
Condition de finitude :
Si l'on prend un sous-ensemble, qu'on le sépare en sous-ensembles et que l'on sépare
encore ses sous-ensembles etc ... la suite obtenue est finie.
Condition de conservation
Soit
un sous-ensemble; la méthode de séparation donne des
avec
où
S(q) désigne l'ensemble des indices des sous-ensembles obtenus à partir de
(sousensembles ''descendants'' de ); on doit avoir :
Condition d'arrêt :
On n'aura pas à séparer un sous-ensemble
dans deux cas :
- il est vide,
- on peut calculer le minimum sur et l'élément ou les éléments correspondants.
est terminal non vide.