Sélection de la stratégie de découpe

Une stratégie de découpe possible consiste à découper récursivement jusqu'à l'obtention des $K$ multi-ensembles finaux. Cette séquence de découpes peut être représentée par un arbre binaire complet (un arbre dont chaque noeud possède exactement deux fils). Cet arbre est appelé l'arbre de découpe (voir Figure 6.5).

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 $K$ feuilles soit : $\frac{1}{K}C_{2(K-1)}^{K-1}$ [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ù $K<N<<\frac{1}{K}C_{2(K-1)}^{K-1}$) et d'élaguer cet arbre de façon à ne conserver que les $K$ 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 $K$ multi-ensembles nécessaires.