Bonjour !

J'ai énormément de mal à donner un titre à ma question mais je vais vous exposer les faits.

Je cherche à obtenir un sous ensemble de nœuds dans chaque arbre de telle façon que pris 2 à 2, les arbres soient différents et que ces arbres soient minimaux. Par arbre minimal je veux dire qu'on ne peut pas trouver un sous-ensemble de noeuds plus petit qui soit différenciable des autres sous-ensembles issus des autres arbres.

Pour le moment, j'ai un algo qui retire les noeuds qui sont communs à tous les arbres de ma liste que j'appellerai diffArbre.

J'ai pensé à l'algorithme suivant, il a une compléxité exponentielle :
Je possède une liste d'arbres dont les noeuds sont triés (au moins 2) issue de diffArbre.
J'itère sur les arbres :
J'itère sur les noeuds :
Je retire le noeud courant de l'arbre courant
Si diffArbre contient un sous arbre nul, je remet le noeud que j'ai retiré et j'entre dans les fils et j'applique l'algo courant sur l'ensemble des sous-arbres de même niveaux (je ne sais pas si c'est clair)
Sinon, je m'intéresse au noeud voisin
Fin itération sur les noeuds
Je passe à l'arbre suivant
Fin itération sur les arbres

Cet algorithme rend des arbres minimaux mais pas optimaux. Enfin... je crois, j'ai écrit l'algo de tête et je l'ai aussi fait tourné de tête.

Le fait que l'arbre minimal soit optimal est un gros plus, mais il n'est pas indispensable.

Le truc important est que j'aimerai diminuer ma complexité. J'aimerai savoir si vous aviez des idées pour y parvenir ou si vous aviez connaissance de problèmes similaires ou de thèses à ce sujet ou encore des mots clés précis pour m'aider à trouver des informations à ce sujet.

je vous remercie