Binary Decision Diagrams
Take a map of mainland USA, and consider the following problems:
Suppose you want to visit every state capitol exactly once, traveling on highways. Which route is shortest? Which route is longest? What is the mean and standard deviation of all the routes?
Weight the states by any means, for example, by reading their two-letter code as a number in base 36. Then find a set of states such that no two members of the set are adjacent, and the total weight is maximized.
There are several ways to colour the map with four colours such that no two adjacent states have the same colour. If the colours have weight 2, 3, 5 and 7, which colourings have the least total weight?
Or consider these:
How many ways can you tile a chessboard using 1x1, 2x1 and 3x1 rectangles? What if we also have pieces that look like 2x2 boxes with one tile missing?
List all 5-letter words that remain words after replacing a b with o.
How can we solve these efficiently?
Families and ZDDs
Take the second map problem for example. Let U (the universe) be the set of all mainland USA states. Any selection of non-adjacent states can be viewed as a subset of U.
Consider F, the set of all such subsets. For clarity, we call a set of subsets of U such as F (equivalently, a subset of the power set of U) a family of sets over U. Thus "set" usually means a subset of U, and "family" means a collection of these subsets. Hypergraphs are equivalent to families of sets, but we follow Knuth’s lead and prefer "families" over "hypergraphs", due to greater familiarity.
It turns out we can describe F in terms of basic families that by themselves are easy to describe. If we had a clever method to represent families on a computer, we might be able to quickly construct a representation for F from the basic families. If the method were really clever, we could subsequently determine the set in F of maximum weight, and solve the problem.
A ZDD is a really clever data structure that represents a family of sets. ZDD stands for zero-suppressed binary decision diagram but this is unimportant.
Combinatorial problems such as the above can be viewed as asking questions about a particular family of sets. With ZDDs, we can answer them efficiently.
Computer Musings by Professor Donald E. Knuth, in particular, "Fun With Zero-Suppressed Binary Decision Diagrams (ZDDs)" and "Fun With Binary Decision Diagrams (BDDs)"
Roughly speaking, BDDs beat ZDDs when the membership of many elements is often irrelevant, while ZDDs beat BDDs when many elements are often absent. I focus on ZDDs, because when I started these notes I was interested in a problem that I felt was better suited for ZDDs.
I wonder if anyone’s looked at a sort of hybrid BDD-ZDD, where each edge contains another bit signifying whether it should be interpreted as a BDD edge or a ZDD edge (we’d disallow LO and HI edges with the same destination as well as HI edges pointing to the FALSE node). I suspect the relevant algorithms could be made to work with a hybrid BDD, and getting the best of both worlds may benefit some problems. Perhaps we could go further and define edges tailored for particular problems, e.g. an edge between i and j might mean every second element between i and j must be present, and another type of edge might mean exactly one of the elements in that range is present.