Discussion :

[Ravaka]

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

[pseudocode]

J'ai bien tout lu mais je n'ai pas tout compris... tu souhaites extraire une sorte de "signature" unique pour chaque arbre en "élaguant" les sous-arbres communs ?

[acx01b]

ce que j'ai compris:

tu as N arbres: A1,A2....An

ce que tu veux c'est trouver le plus petit ensemble (en nombre de noeuds ?) B1,B2,...,Bn
où pour tout i: Bi est un sous-arbre de Ai,
et où pour tout i,j: i différent de j => Bi différent de Bj

le cas le plus simple serait: si Q est une feuille de Ai, et n'est dans aucun autre arbre, alors Bi = Q

le cas général serait (complexité en N^2 ?):
- pour chaque sous arbre de chaque arbre, on regarde s'il est sous arbre d'un des autres arbres
- ainsi on a pour chaque arbre la liste de ses sous arbres qui ne sont pas dans les autres arbres
- finalement pour chaque arbre on prend le plus petit sous arbre qui n'est pas dans les autres arbres

[Ravaka]

Je vais regarder le subtree Merci de tout coeur pour les indications.

[Ravaka]

J'ai bien tout lu mais je n'ai pas tout compris... tu souhaites extraire une sorte de "signature" unique pour chaque arbre en "élaguant" les sous-arbres communs ?

Oui, tout à fait

ce que tu veux c'est trouver le plus petit ensemble (en nombre de noeuds ?) B1,B2,...,Bn

Oui, plus petit ensemble en nombre de noeuds

En tout cas, je vais regarder ton algorithme, mais il n'est pas en N^2 car il y a au moins le nombre de noeuds de chaque arbre qui entre en jeu ^^

[acx01b]

en N^2 ou peut - être moins vu les algo de subtree matching que tu trouves sur google: N c'est le nombre de neuds en tout pas le nombre d'arbre