Comment implémenter efficacement les diagrammes de décision binaires (BDD)?

Vous trouverez des informations sur les diagrammes de décision binaires ici BDD on wikipedia.Comment implémenter efficacement les diagrammes de décision binaires (BDD)?

L'approche la plus simple consiste à construire BDT (Binary Decision Tree) et à le réduire en raison de deux règles:
- Fusionner les sous-graphes isomorphes.
- Éliminer tout noeud dont les deux enfants sont isomorphes.
Mais il y a un problème majeur BDT peut être vraiment énorme par rapport à BDD. Y at-il un moyen de construire BDD sans construire le BDT en premier?

Source

2010-11-02 Tomek Tarczynski

Vous construisez jamais l'arbre de décision non partagée. Le BDT n'est qu'un moyen d'expliquer les BDD. –

Puisqu'il s'agit d'une signification différente de bdd par rapport à la balise bdd, je vais supprimer cette balise. –

Une liste des implémentations existantes de diagrammes de décision binaires (~ 50) dans diverses langues peut être trouvée [ici] (https://github.com/johnyf/tool_lists/blob/master/bdd.md). –

Utilisez les algorithmes Mk (créer un nœud) et Build (construire BDD) à partir de Andersen, pages 16-17. Je n'ai pas joué avec BDD dans un certain temps, mais je crois que H ou T devrait être une table de hachage. Utilisez des tables de hachage pour que les deux soient du bon côté.

Source

2010-11-02 11:13:26

Merci, l'ensemble du document sera très utile. –

La façon de construire le BDD provient de l'arbre d'analyse de l'expression représentant la fonction booléenne que vous essayez de construire.

Ie, si vous voulez que le BDD pour (A + B) (C + D), vous devez d'abord parse (A + B) (C + D) dans un arbre:..

 
    . 
/\ 
+ + 
/\/\ 
A B C D

puis construire le BDD récursivement - vous avez besoin de méthodes qui peuvent former l'AND et le OU de deux BDDS, et le cas de base (BDD variable unique).

Cela fonctionne aussi bien pour les circuits logiques (voir comme analyse DAG au lieu d'arbre).

Ces notes sur BDD expliquent comment implémenter AND et OR, également les tables de hachage qui sont nécessaires pour faire fonctionner les choses efficacement: http://bit.ly/cuClGe

Source

2010-11-02 15:18:43 user486972

Comment implémenter efficacement les diagrammes de décision binaires (BDD)?

Répondre

Questions connexes