Bonjour,
 
Je rencontre une difficulté dans un de mes programmes en C/C++ que je n'arrive pas à résoudre de manière intuitive (et je manque de connaissances théoriques en algorithmie).
 
Voici en bref, le cœur du problème :
 
Mon programme est conçu pour analyser et valider des séquences d'éléments. Quelques exemples de séquences à valider :  {A}, {A, B, C}, {B, C, D},  {A, D}, etc.
 
L'ensemble des séquences valides est décrit de manière formelle sous la forme d'un arbre "logique" (<= désignation personnelle de l'arbre que j'utilise). Un exemple d'arbre logique "validant" :
 

Cet arbre permet de valider l'ensemble des séquences suivantes : {A}, {B,C} et {A,D}. Toutes les autres séquences sont donc rejetées par mon programme.
 
Actuellement, mon programme peut :
- accéder aux éléments d'une séquence à valider.
- accéder aux nœuds et feuille de l'arbre "logique".
 
Sauf que voila, je suis bloqué, je n'arrive pas à définir et à implémenter la fonction C/C++ (récursive) qui permet de valider une séquence donnée par rapport à un arbre logique donné !
 
Pouvez vous m'aider à résoudre ce problème ? Pensez vous que je dois revoir en profondeur la conception de mon programme (l'arbre notamment) pour revenir à un problème plus courant ou une solution plus optimale ?
 
Merci.
 
Amicalement,
X.

L'arbre en question, il t'est imposé ou c'est toi qui l'a conçu ?
J'arrive pas à trouver un "algorithme" commun à l'ensemble des noeuds, comme s'il fallait faire un cas particulier sur chacun des noeuds, ce qui enlève tout intérêt à l'utilisation d'un arbre  
 
Les séquences {B,C} et {C,B}, j'imagine qu'elles doivent être considérées comme différentes ? Ce qui me choque, c'est que le "B" et le "C" sont au même niveau alors qu'on s'attendrait plutôt à ce qu'ils soient à des niveaux différents, pour rendre compte de l'ordre imposé  
 
On peut le changer, cet arbre ?!?
 
edit : en lisant le post jusqu'au bout, il semble que oui  
J'y réfléchis, c'est intéressant comme sujet

t'as pas reinventé le parsing là ?
y a largement plus simple pour faire ça

Bon, j'ai trouvé un truc. Pas forcément très satisfaisant mais ca devrait fonctionner  
 
1 noeud contient 2 infos :
- 1 booléen "feuille" qui indique si le noeud peut représenter la fin d'un chaîne
- 1 liste de couples (lettre, arbre), représentant l'ensemble des fils du noeud, chacun indexé par une lettre (cette liste peut bien sur être vide)
 
L'algorithme devient assez simple :  

C'est plus amusant de réinventer la roue et de jouer avec des arbres

 
Bonsoir,
 
Je réponds dans l'ordre de vos messages. En effet, il est envisageable de changer cet arbre si c'est une impasse.
 
L'arbre est implémenté de telle façon qu'on peut facilement distinguer les nœuds des feuilles. Les structures de données associées aux nœuds et aux feuilles sont identiques. Cette structure contient une valeur qui est soit le nom de l'opérateur logique (nœud), soit le nom d'un élément de la séquence (feuille).
 
Dans mon cas, {B,C} et {C,B} sont des séquences équivalentes et valides pour un arbre donné. L'ordre d'apparition des éléments dans une séquence n'a donc aucune importance dans mon cas d'application.
 
Je traite les messages suivants.
 
Amicalement,
X.

Euh, tout d'abord : tu travailles en C, ou en C++ ? Les deux langages diffèrent, et donc les solutions disponibles également.

 
Bonjour,
 
Je ne suis pas sur de bien comprendre ta réponse. J'ai souhaité présenté mon problème de manière assez conceptuelle, peut être trop. En effet, l'objectif de mon application n'est pas d'analyser des chaines de caractères.  
 
D'ailleurs, l'ordre des éléments n'est pas significatif.  
 
En fait, les éléments de mes séquences ne sont pas des caractères. Il s'agit plutôt de structures de données complexes que je peux identifier à l'aide d'un numéro unique (un entier).  Mes séquences sont en fait constituées d'une suite d'identifiants (32bits) mêles à d'autres informations (de taille variable) qui ne sont pas significatives dans un premier temps.
 
Amicalement,
X.

 
Bien que ma difficulté se situe dans un plan purement algorithmique, je compile mon application en C++.  
 
Amicalement,
X.

Oui, en effet. J'avais mal lu le post d'origine. Je me souviens m'être penché sur un problème similaire il y a quelques années, et de l'avoir résolu de manière... pour le moins alambiquée, avec des arbres aussi (edit : je suis en train de me rappeler de ma méthode de l'époque, et avec le recul, c'était assez horrible). Il doit y avoir plus simple.

Je déplace ce sujet dans "Algorithme", il y aura plus sa place, et d'autres personnes plus calées interviendront peut-être.

 
 
Je ne suis pas très familier du pseudo-code. Il va me falloir un peu de temps pour te répondre. Je me rends compte que l'arbre que j'ai créé n'est pas facile à interpréter.  
 
Par défaut dans mon implémentation, je considère qu'une feuille est un élément de la séquence valide, et qu'un noeud de l'arbre avec au moins un fils est forcément un opérateur logique.

Voici l'embryon d'algo récursif sur lequel je me suis arrête. Il ne répond pas à mon problème car il est trop "permissif".
 

 
Il est trop permissif car il valide toute séquence,  qui comprend (englobe) une séquence valide.
 
Amicalement,
X.

J'ai du mal à savoir de quoi tu pars exactement pour te proposer des alternatives.  Une chose à regarder éventuellement, c'est les BDD (Binary Decision Diagram).
 
L'arbre que tu donnes ressemble à une équation mise sous forme normale conjonctive, à une chose importante près: tu considères implicitement dans ton ET l'absence de toutes les variables non présentes.  Donc ton ET(A, D) signifie ET(A, !B, !C, D).  Le problème de ton algo est qu'il ne vérifie pas ces absences.

OK, oublie mon 2ème message alors  
 
S'il n'y a pas d'ordre, je ne vois pas ce que la notion d'arbre va nous apporter

 
Tu as en effet soulevé le problème majeur de mon algorithme (vérifier les absences). Je ne vois aucune solution simple pour corriger ce problème.  
 
Je jette un œil aux BDD.  
 
Amicalement,
X.
 

 
En effet, j'ai peut être mal posé le problème. Je travaille de manière très intuitive sur cet apsect de mon application n'ayant pratiquement aucune base en algorithme. Merci tout de même pour ton aide !    
 
La structure de données que j'utilise ressemble à un arbre, mais cela n'a probablement rien à voir avec les arbres utilisés par les algorithmes de tri. La mention de Un Programmeur à la Binary Decision Diagram est peut être une piste.

En faisant des recherches sur la BDD, je tombe sur quelque chose de tres proche de ma pensée. Propositional directed acyclic graph (PDAG)

Un moyen assez simple de fixer to algo est de comparer en plus le nombre de fils du noeud ET avec le nombre d'éléments dans ta séquence.

 
Bonjour,
 
Partons sur cette idée et fixons quelques règles du jeu :
- Une feuille me rapporte 1 point si l'élément porté par la feuille est dans ma séquence. Grosso modo, 1 correspond à une condition qui retourne TRUE.
- Un nœud logique (ET) retourne 0 si au moins un fils retourne 0. Je propage le fait qu'une condition ait retourné FALSE.
- Un nœud logique (ET) retourne N, le nombre de points cumulés de l'ensemble de ses fils.
- Un nœud logique (OU) retourne N, le nombre de points correspondant au nombre de point maximum retourné par l'un de ses fils.
- Globalement, le nombre de points à la racine doit être strictement égal au nombre d'éléments de ma séquence pour que celle ci soit valide.
 
 
En pseudo-code, cela donnerait ceci :
 

 
Sauf erreur de ma part, en appliquant cet algorithme, je parviens à mes fins.... dans la plupart des cas. En effet, cela impose des contraintes sur mon arbre "logique". Je ne serais pas qualifier ces contraintes mais je peux donner quelques exemples.
 
Prenons par exemple différents arbres "logique" permettant de valider les séquences suivantes : {A,B,C,D}, {A,B,D}, {B,C,D}.
 
Je peux proposer un premier arbre logique en visant quelque chose d'assez concis :

 
Mais je peux aussi proposer un second arbre logique, plus explicite :

Note : Celui la est complètement nul, puisque ca reviens à créer la liste de toutes les séquences autorisées (un simple tableau de listes chainées répondrait à mon problème).
 
Je peux également proposer cet arbre qui met en défaut l'algorithme présenté ci-dessus.

 
Par conséquent, je pense avoir déplacé le problème.  Au moment de la création de mon arbre logique, je dois soit effectuer un contrôle pour etre sur que l'algorithme va fonctionner correctement, soit corriger de manière automatique mon arbre en respectant des règles que je n'arrive pas bien à formuler encore. Qu'en penses vous ?
 
Amicalement,
X.

Je n'ai peut-etre pas ete clair, mais je partais avec l'idee que ton arbre etait sous forme normale disjonctive (un OU de ET), pas un arbre plus complet.  Pour de tels arbres, il faudrait d'abord que toi tu definisses le sens que tu veux donner aux operations, parce qu'il n'est pas clair pour moi.  Par exemple dans la derniere forme que tu donnes, avoir un D rends impossible de remplir la condition de gauche mais est indispensable pour remplir la condition de droite...

Plutot que d'essayer de partir sur ta formalisation qui semble problematique, ne pourrais-tu pas nous donner ton probleme dans les termes dans lequel ton probleme se pose?

 
Bonjour,
 
Bien, je vais me renseigner sur ce que signifie "une forme disjonctive".
 
Je souhaite que les conditions (OU) et (ET) s'utilisent de la manière la plus naturelle. Dans le dernier arbre, si la séquence ne contient pas l'élément D, la condition de droite retourne 0 (ou FAUX) et c'est bien ce que je souhaite puisque les séquences valides doivent contenir un D.... Je n'ai peut être pas bien compris le sens de ta remarque.
 
 
EDIT --
 
J'avais mal lu ta remarque. Un (ET) retourne VRAI si tous les fils retournent VRAI. Jusque la tout va bien. Une feuille retourne VRAI si l'élément porté par cette feuille apparait dans la séquence en cours d'analyse.
A partir du moment où ma séquence comprend les éléments {A,B} ou {B,C}, la condition de gauche retourne VRAI.
 
EDIT --

 
Ok. Le principe des éléments et des séquences n'a pas changé. Mon application est configurée avec l'ensemble des séquences valides. Mon probleme se situe donc à deux niveaux :  
- trouver une formalisation la plus concise possible pour l'ensemble de séquences valides,
- trouver l'algorithme qui me permet de valider le plus rapidement possible un séquence donnée par rapport à l'ensemble des séquences valides.
 
Est-ce que cet expression de besoin est suffisamment claire ?  
 
La solution que je veux absolument éviter est la suivante :
- garder en mémoire la liste de toutes les séquences valides => trop de mémoire perdue si les séquences ont de nombreux éléments, et qu'une grande partie des ces éléments sont communs à plusieurs séquences.
- parcourir l'ensemble des séquences valides jusqu'à trouver celle qui correspond à la séquence analyser => trop de temps perdu à chaque analyse.
 
Ce dernier point peut être compensé en utilisant une fonction de hachage pour faire un premier tri parmi les séquences valide, mais cette alternative ne résout pas le premier problème, et tend même à l'aggrave (stocker les hash des séquences valides en plus des séquences valides elles mêmes).
 
Amicalement,
X.

Effectivement, je veux éviter si possible la forme normale disjonctive. Je veux pouvoir "factoriser" au mieux les éléments qui apparaissent dans l'arbre. J'ai une trés forte contrainte en terme de mémoire disponible pour stocker l'ensemble des séquences valides.

Qui est-ce qui va s'occuper de passer de l'ensemble des sequences a la forme compacte?
 
En passant, sequence pour moi implique une notion d'ordre qui est tout a fait absente de la discussion jusqu'a present.

A défaut de pouvoir automatiser le processus d'élaboration de l'arbre, celle-ci est manuelle. Je n'ai pas d'autres alternatives pour l'instant.
 
Tu as raison. Peut être que le terme combinaison est plus approprié. Est ce que tu vois un meilleur terme à utiliser ?

Autre chose qui pourrait t'etre utile: http://en.wikipedia.org/wiki/Espre [...] _minimizer

Intéressant.
 
Si je tourne de 90° mon fameux "arbre logique", j'ai l'impression de voir un circuit logique avec des portes OR et des porte AND... au lieu d'électronique, j'aurais du faire informatique dans mon école d'ing. !
 
Si je pars d'une table de vérité, je peux effectivement générer de manière automatique mon arbre logique.
 
J'ai l'impression que je pourrais implémenter mon programme différemment. Ce serait plutôt une simulation de circuit logique qu'un arbre avec des algorithmes récursifs....

 
Je viens de télécharger un outil qui s'appuie sur cette méthode de réduction.
 
Voici le résultat avec mes exemples précédents :
 

 
La première équation doit correspond à la forme normale disjonctive dont tu parlais.
 
La seconde correspond à la forme réduite que j'avais trouvé à la main.
 
Cela donne une piste sérieuse pour passer optimiser mon arbre logique entre la saisie utilisateur et la forme réduite exploitée par mon application.
 

Tu remarqueras qu'il y a des negations ce qu'aucun de tes arbres n'a.

En effet, cet arbre "logique" ne convient pas.  
 
Quelle alternative s'offre à moi. J'ai l'impression que mon besoin est d'implémenter une grosse fonction logique avec N entrées logiques (1 entrée correspond à un élément de ma combinaison, 0 pour absent, 1 pour présent dans la combinaison en cours d'analyse) et 1 sortie logique (1 = combinaison valide / 0 = combinaison invalide).
 
Cette fonction étant configurable en cours d'exécution, je me demande comment l'implémenter. Sous quelle forme. C'est un graphe ? Autre chose ? Je cherche...

Il te faut la possibilite d'une negation.  Donc soit tu doubles tes variables par une version niee (A et Abar), soit tu as un operateur unaire de negation (NOT), soit tu utilises d'autres fonctions (NAND, NOR, XOR).  NAND ou NOR seul suffit. (AND ou OR) et (NOT ou NAND ou NOR) suffit aussi.
 
Apres, tu peux utiliser un arbre ou un graphe (acyclique).  Un graphe peut etre plus dense.  Les differentes variantes de BDD sont des graphes de cette sorte (avec des contraintes et des proprietes).
 
Tu vas avoir combien de variables?

Ok, je viens d'ajouter à mon application le nœud logique NOT. Je peux donc construire tout arbre ou graphe avec des opérateur AND, OR, NOT maintenant.
 
Je regarde le graphe acyclique....
 

L'ordre de grandeur est le millier. Cette histoire de négation m'inquiète un peu... il faudrait pouvoir les rendre implicite dans ma représentation.

Une idee -- qui vaut ce qu'elle vaut.
 
Associer un univers a un noeud.  Cet univers est herite par tout l'arbre en dessous sauf s'il est ecrase.  Ensuite avoir deux types de noeuds ET, un normal et un qui implicitement a une negation pour toutes les variables qui ne sont pas en dessous.

Ok. Je comprends l'idée. Merci.
 
Par contre, j'ai encore du mal à voir ou cela m'amène en terme d'algorithme (pseudo code) et de modélisation de l'arbre (comment faire apparaitre l'univers à un nœud ET).

Afin de clore le sujet rapidement, je fais le point sur la solution technique que je vais certainement choisir.
 
 
 
1) Je fais évoluer mon arbre "logique" pour être conforme à un graphe de type PDAG (Propositional directed acyclic graph).
 
2) Les feuilles de ce graphe représentent les éléments de mes combinaisons. Chaque élément apparait une seule et unique fois dans le graphe. Plusieurs nœuds logiques peuvent pointer sur un même élément.
>>> ca me permet de gagner de l'espace mémoire de manière significative.
 
3) L'évaluation d'une feuille est réalisée de la façon suivante :
  - TRUE si l'élément porté par la feuille appartient à la combinaison en cours d'analyse,
  - FALSE sinon.
 
4) Pour minimiser la taille du graphe en mémoire et pour éviter d'avoir à décrire explicitement tous les éléments qui doivent être absents des combinaisons valides, j'opte pour la technique de dénombrement des feuilles évaluées VRAI pendant le parcours du graphe. Au final, la combinaison est validée si le PDAG retourne VRAI et si le nombre de feuilles évaluées correspond au nombre d'éléments dans la combinaison en cours d'analyse. Les règles que j'applique pour le dénombrement sont simples : Un nœud logique (ET) retourne la somme des fils si tous les fils sont évalué VRAI, (OU) retourne le maximum des fils qui sont VRAI.
 
5) La fonction logique représentée par le graphe doit être soit FND, soit factorisée, voire réduite. Cela peut être fait de manière intuitive pour les combinaisons les plus simples. Une forme factorisée/réduite peut être obtenue à partir d'une forme normal disjonctive ou d'une table de vérité en utilisant les outils disponibles sur Internet.
 
Sauf erreur de ma part, le problème est résolu. Je tag le titre de ce thread en conséquence.
 
Merci pour votre aide.    
 
Amicalement,
X

A noter que la solution la plus compacte serait le BDD mais la production d'un tel graphe semble problématique (ordonnancement optimal des variables difficile à obtenir).