arbre_decoupeArbre de découpe représentant une stratégie de découpe de en 5 multi-ensembles.
Le nombre de découpes possibles par cette stratégie est donc
égal au nombre d'arbres binaires complets possédant exactement
feuilles soit :
[FGS90].
Ce nombre est trop important pour envisager une énumération
exhaustive de toutes les stratégies. Chou et al. [CTM89],
Lin et al. [LSC91] et Balasubramanian et al. [BA91] ont
suggéré de créer un arbre intermédiaire avec N feuilles (où
) et d'élaguer cet arbre de
façon à ne conserver que les
feuilles qui conduisent à une
erreur quadratique minimale. Selon Wu [WZ91], cette stratégie
implique un surcoût trop important par rapport à l'amélioration
apportée. Il recommande donc de ne générer que les
multi-ensembles nécessaires.