Je commence à rédiger un ouvrage temporairement intitulé Algorithmic for Knowledge Representation. Et j'ai une petite question de vocabulaire mathématique.
J'étiquette mes hiérarchies (arbres n-aires) à l'aide de l'algorithme du nested set model.
Du coup si on a cette hiérarchie :
Où :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5 A | B-----------------C-----D | | | E------F------G H I------J
- A possède 3 enfants : B, C et D
- B possède 3 enfants : E, F et G
- C possède 1 enfant : H
- D possède 2 enfants : I et J
On se retrouve avec cette hiérarchie étiquetée par des intervalles :
Où :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5 [0,10] | [1,5]-------------[5,7]-[7,10] | | | [2,3]-[3,4]-[4,5] [6,7] [8,9]-[9,10]
- un noeud est inférieur à un autre si son intervalle est contenu par celui de l'autre
- un noeud est supérieur à un autre si son intervalle contient celui de l'autre
- un noeud est égal à un autre s'il ont le même intervalle
Sinon :
- un noeud est à gauche de un autre si sa borne maximale est inférieure à la borne minimale de l'autre
- un noeud est à droite de un autre si sa borne minimale est supérieure à la borne maximale de l'autre
J'utilise en plus un algorithme efficace de recherche dans un ensemble d'éléments d'une hiérarchie.
Pour cet algorithme tous les noeuds sont comparables 1 à 1 avec un des 5 résultats ci-dessus. J'ai bien compris qu'il est question d'atteignabilité (reachability).
Ce que je comprends plus mal c'est le genre de relation d'ordre à laquelle j'ai affaire.
Notez que les relation à gauche de et à droite de sont transitives.
Puisque tous les noeuds sont comparables 1 à 1 alors c'est un ordre total ?
Ça paraît bizarre pour une relation d'atteignabilité.
À quel genre d'ordre j'ai vraiment affaire
Partager