Arbres et arborescences
175
dans
On arrête la procédure, sauf s'il existe des
tels que
auquel
cas, il pourrait y avoir des solutions équivalentes que l'on peut rechercher en séparant les
répondant à
c)
est non terminal non vide, on le sépare et on examine ses suivants en calculant
l'évaluation par défaut pour chacune d'entre eux.
Phase 3 Examen
Le calcul de l'évaluation par défaut en chacun des suivants de
peut faire apparaître
deux circonstances intéressantes :
- un suivant
de
est vide et l'on s'en aperçoit lors de cette phase; on peut
alors le supprimer tout de suite de
(sur l'exemple traité, nous ne
procédions pas à cet examen systématique des suivants, mais on aurait pu
évidemment le faire).
- un suivant
de
est tel qu'il existe un sommet terminal non vide
avec
et tel que
; alors, le minimum cherché ne peut être dans et
on élimine également de
Soit
l'ensemble des suivants de non éliminés, on posera :
c'est-à-dire que l'on élimine
qui n’est plus sommet pendant, puis on conserve
l'ensemble des sous-ensembles séparables et intéressants, et on revient à la phase de
sélection. Pour l'itération
représente bien l'ensemble des sommets candidats
à la séparation.
Cet algorithme peut être résumé par l'ordinogramme général suivant :
p= 0
Sélection de
Séparation
Un optimum
est trouvé
Examen des
suivants
ensemble des
non éliminés