はじめに
前回の記事↓ で、Daily Akari というパズルの ZDD による解法をサラッと紹介しました。
kntychance.hatenablog.jp
しかし、どうにも 「ZDD とはなんぞや？」「よくわからんが難しそう」といった風に感じている人がなんとなく多そうな気がしており、これは由々しき事態だなと。
ZDD はすんごくシンプルなアイデア で色々な問題を解けてしまう激面白データ構造なので、何としてでも布教したいと思いました。
なので、アルゴリズム 学徒だけでなくプログラミングにそこまで明るくない非応用数学 系の人々にも届くように一から丁寧に解説していきます。ゴールがあった方がいいと思うので、Daily Akari ソルバーの作成 を目標にしてしまいましょう。
目指せ、一家に一台 ZDD！
なお、全体の実装例は ↓ に置いてあります。
（本記事シリーズでは Java の方を実装していきます。）
github.com
この記事でやること
ZDD の概要の解説
ZDD のベースとなるクラスの解説・実装（Java JDK 24）
ZDD の布教！！！！！！
この記事でやらないこと
ZDD の演算の話（第2回でガッツリやる予定。ZDD の激面白ポイントはここ。）
Daily Akari の話（第3回で入る予定。気長にやりましょう。）
1. ZDD の概要
1.1. ZDD とは
Zero-supressed Binary Dicision Diagram の略です。日本語では「ゼロサプレス （抑制？）型二分決定グラフ 」になります。あまり日本語で呼ばれているところは見ないですが、提案されたのは日本の教授、湊真一先生です[1]。2025年現在は京大で教鞭をとられています。
与えられた集合 台集合 、アイテム 、各部分集合 組合せ集合 と呼びます。
例えば、
【図 1.1-1】
【図 1.1-1】において、赤い辺を 0-枝 、青い辺を 1-枝 と呼びます。また、一番上の 根 、一番下の 0-終端節点 、1-終端節点 と呼びます。
ZDD において、根から1-終端節点までのパスが各組合せ集合に対応します。
すなわち、各パスについて節点から出る際に
1-枝を通るなら、その節点のアイテムを組合せ集合に追加する。
0-枝を通るなら、追加しない。
とすることで組合せ集合と対応付けます。（【図 1.1-2】）
【図 1.1-2】 根から1-終端節点までのパスが組合せ集合に対応
特に、この対応付けになぞらえると、0-終端節点のみからなる ZDD は部分集合族
以上が、ZDD の"読み方"になります。
この説明だけ聞くと「どこからそのグラフは降ってきたんですか？」という疑問が出ると思うので、次はその解説をします。
1.2. ZDD の基礎的な構成方法
前節に引き続き、台集合
まず、【図 1.2-1】に示す完全二分決定木 を考えます。
【図 1.2-1】 完全二分決定木
さて、このままだと節点数が
そこで、次の2つの圧縮規則 （【図 1.2-2】）を導入します。
削除規則 ：共有規則 ：
【図 1.2-2】 削除規則と共有規則
この2つの圧縮規則を、【図 1.2-1】で示した完全二分決定木に対し（任意の手順で）繰り返し適用することで、最終的に【図 1.1-1】に示す ZDD が得られます*1 。また、この圧縮規則が適用できない状態のことを既約である と言います*2 。
というわけで、ZDD の構成法が得られました。
しかし、この構成法には大きな問題があります。
というのも、最初に完全二分決定木を作ってしまうと、その時点で計算量が爆発してしまいます。
目標としている Daily Akari ソルバーにおいては、台集合をマス全体として、解であるような灯りの置き方（=マスの部分集合）全体から成る ZDD を構成します。グリッドサイズは最大 *3 、完全二分決定木の節点数は
というわけで、本節で解説した完全二分決定木を経由する構成法は、現実的ではありません。ただし、2種類の圧縮規則とアイテムの添字順（=完全二分決定木上でアイテムをどの順に置くか）によって ZDD の形状が定まっている ということは、知識として知ってくおくとよいでしょう。
次項では、「じゃあ結局 ZDD ってどう作るの？」という疑問に答えていきます。
1.3. ZDD の効率的な構成方法
1.3.1. 部分集合族の分解
ZDD の各接点は、それ自体を根とする ZDD と捉えられ、対応する部分集合族が存在します。そこで、根の0-枝の先と1-枝の先がそれぞれどのような部分集合族を表しているかを考えます。
以下、台集合を
また、便利な記号として、部分集合族 二項演算子
\begin{equation} \mathcal{P} \triangleleft e_i := \{P \cup \{e_i\} \mid P \in \mathcal{P}\} \tag{1}\end{equation}
すると、任意の非空な組合せ集合を少なくとも1つもつ部分集合族
\begin{align} e_i & := \min(\bigcup_{P \in \mathcal{P}} P) \\ \mathcal{P}_0 & := \{P \mid e_i \notin P \in \mathcal{P}\} \tag{2}\\ \mathcal{P}_1 & := \{P \setminus \{e_i\} \mid e_i \in P \in \mathcal{P} \} \end{align}
（アイテムの大小は添字で比較するものとします。 ）とおいたとき、次式が成り立ちます。
\begin{equation} \mathcal{P} = \mathcal{P}_0 \cup (\mathcal{P}_1 \triangleleft e_i) \tag{3}\end{equation}
この 式(3) は、【図 1.3.1-1】に示す ZDD の抽象図をそのまま表現しています。
【図 1.3.1-1】 式(3) と ZDD
ふわふわとお絵描きしていたものが、かっちりと扱えそうになってきましたね。
1.3.2. 圧縮規則の再帰 的な適用
さて、勘のいい読者は気づかれているかもしれませんが、式(3) は ZDD の再帰 的な構成方法を示唆しています。
すなわち、
この枝を ｴｲﾔｯ!! する操作に圧縮規則を適用したものが、次の手続き
そうでないなら、以下の節点を作成して返す。ただし、等価な節点を既に作成済みならそれを返す。
この手続きを用いることで、与えられた部分集合族 再帰 的に記述できます。
上記以外なら、式(2) により
というわけで、ZDD の良い構成方法が得られました。
しかし、この 部分集合族 *4 。 大事なのは、このように再帰 的に記述できることを理解しておくことです。
（ちなみに、最初からこの
「え、じゃあ結局 ZDD ってどうやって使うの？？？」
とツッコミが入るかもしれませんが、解説する分量の都合上、次回までお待ちください。実際のところそのあたりが ZDD で一番面白い話で「おわりに」の章でも軽く触れますが、本記事ではとにかく ZDD のベースとなる部分の実装を目指します。
1.3.2項 にて 等価節点をどのように保存・検索するのか という点にも着目しなくてはなりません。いわゆるデータ構造 ってやつです。（ZDD も部分集合族を表現するためのデータ構造と言えます。）
計算機で扱える基本的なデータ構造として、配列 があります。これは、複数のデータを1列に並べたもので、任意の非負整数 *5 のデータの読み書きを高速に処理できます。なお、計算機のメモリにも限りがあるため、配列の長さとして有限な非負整数
そして、配列を流用するデータ構造として、ハッシュテーブル というものがあります。
ja.wikipedia.org
ハッシュテーブルは、保存したいデータに対し予め用意した"いい感じの関数"を使って ハッシュ関数 ハッシュ関数 で得られた整数値のことをハッシュ値
（用意した関数が単射 でない場合、異なるデータに対して同じ番地が充てられてしまう場合があり、これを衝突 と呼びます。衝突した場合にどう保存するかは別途取り決めておく必要があるのと、そもそも衝突があまり起きないように関数を定義することが重要です。）
ハッシュテーブルに ZDD の節点を保存できれば、検索が高速にできてうれしいです。なので、サクッとハッシュ関数 を作ってしまいましょう*6 。
ハッシュ関数 を作る上での便利な道具として、Xorshift と RollingHash という 2 つの関数を使います。具体的な中身はリンク先の解説が易しいのでそちらを参照ください。
0-終端節点のハッシュ値 を ハッシュ値 を
終端節点でない節点 ハッシュ値 は既に求まっていると仮定します。
この ハッシュ値 を次のように定義します：
\begin{align} \text{hash}(\mathcal{P}) := \text{RollingHash}(& \text{Xorshift}(i+1), \\ & \text{Xorshift}(\text{hash}(\mathcal{P}_0)+1), \tag{4} \\ & \text{Xorshift}(\text{hash}(\mathcal{P}_1)+1)) \end{align}
要するに、アイテムと枝の先にある2節点のハッシュ値 から自身のハッシュ値 を定めているわけですね。これでハッシュ関数 の完成です。
以上で ZDD のベースとなる考え方の解説は終了です。
次章からは実装に入っていきます。
2. 実装
zddForDailyAkari パッケージに、続く3つのクラスを実装します。
なお、3つ目の ZDD_Visualizer はなくてもDailyAkari は解けるので、飛ばしても問題ありません。
2.1. RollingHash クラス
import java.util.List;
import java.util.Random;
public class RollingHash {
public int m;
private int r;
public RollingHash(int m) {
this .m = m;
Random random = new Random();
this .r = random.nextInt(2 , m);
}
public int hash(List<Object> list) {
long l = r;
long h = 0 ;
for (Object e : list) {
h += xorshift(e.hashCode() + 1 ) * l;
h %= m;
l = l * r % m;
}
return (int ) h;
}
public int xorshift(int x) {
x ^= x << 13 ;
x ^= x >> 17 ;
x ^= x << 15 ;
return Integer.remainderUnsigned(x, m);
}
}式(4) に基づいたハッシュ関数 を実装したクラスです。 RollingHash という名前ですが、中に Xorshift も内蔵しています。
コンストラク タは 法 m を引数に取り、コンストラク タ内で基数 r を乱択しています。これは Rolling Hashについて（survey + 研究） | maspyのHP にて解説された内容を実装したものになります。
2.2. ZDD<T>、ZDD<T>.ZDD_Node クラス
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
public class ZDD<T> {
public int n;
public ArrayList<T> items;
public HashMap<T, Integer> idx;
public ZDD_Node zero_terminal;
public ZDD_Node one_terminal;
public RollingHash rollingHash = new RollingHash(1401055423 );
public HashMap<ZDD_Node, ZDD_Node> node_table = new HashMap<>();
public ZDD(ArrayList<T> arrayList) {
this .n = arrayList.size();
this .items = (ArrayList<T>)arrayList.clone();
this .idx = new HashMap<>();
this .zero_terminal = new ZDD_Node(null , null , null );
this .one_terminal = new ZDD_Node(null , null , null );
zero_terminal.hash = rollingHash.xorshift(n+1 );
one_terminal.hash = rollingHash.xorshift(n+2 );
for (int i = 0 ; i < n; ++i) idx.put(items.get(i), i);
}
public ZDD_Node get_node(T top, ZDD_Node zero, ZDD_Node one) {
if (one == zero_terminal) return zero;
ZDD_Node node = new ZDD_Node(top, zero, one);
if (node_table.containsKey(node)) {
node = node_table.get(node);
} else {
node_table.put(node, node);
}
return node;
}
public class ZDD_Node {
public T top;
public ZDD_Node zero;
public ZDD_Node one;
public int hash;
public ZDD_Node(T top, ZDD_Node zero, ZDD_Node one) {
this .top = top;
this .zero = zero;
this .one = one;
if (top != null ) {
this .hash = rollingHash.hash(Arrays.asList(idx.get(top), zero, one));
}
}
@Override
public int hashCode() {
return this .hash;
}
@Override
public boolean equals(Object other) {
if (this == other) return true ;
if (other instanceof ZDD<?>.ZDD_Node o) {
if (this .top == null || o.top == null ) return this == o;
return this .top.equals(o.top)
&& this .zero == o.zero
&& this .one == o.one;
} else {
return false ;
}
}
}
}ZDD クラスと、その内部クラスとして節点を表す ZDD_Node クラスを実装しています。これは、台集合や節点のハッシュテーブルを ZDD クラスに管理してもらいたいという思想があるからです。 また、1.3.2項 ので解説した
T はアイテムのクラスを表します。ZDD<T> のコンストラク タは台集合として ArrayList <T> を引数に取り、ArrayList での順に沿ってアイテムの添字を決定します。
決定した添字は HashMap<T, Integer> idx に保存しています。
ZDD_Node クラスでは hashCode() と eauals() をオーバーライドしています。
注意点として、equals() 内の
this.zero == o.zero && this.one == o.one
としている箇所を
this.zero.equals(o.zero) && this.one.equals(o.one)
としてしまうと、equals() が終端節点まで再帰 的に呼び出されてしまい計算量が爆発してしまいます。インスタンス かどうかの比較）で十分です。
同様に、終端節点まで hashCode() が再帰 的に呼び出されることを回避するため、コンストラク タ内でハッシュ値 を予め計算し保存しておくようにしています。
2.3. ZDD_Visualizer<T> クラス
外部ライブラリである jung-2.0.1 を利用するため、導入方法をまず紹介します。
まず、下記リンクからライブラリの圧縮ファイルをダウンロードしてください。
sourceforge.net
ダウンロードした圧縮ファイルを適当なディレクト リに解凍しておき（.jar ファイルがいっぱい入っています。）、自身の java 実行環境に合わせてクラスパスを通せばよいです。
ここでは一応、筆者の環境（vscode , Extension Pack For Java ）でのパスの通し方を紹介しておきます。
画面左下の ☕java Ready と表示された箇所をクリック
【図 2.3-1】 Java Ready をクリック
Open Project Settings を選択
【図 2.3-2】 Open Project Settings
Libraries タブを開き、解凍した .jar ファイルを追加する。
【図 2.3-4】 Libraries タブを開き、解凍した .jar ファイルを追加する。
Apply Settings をクリック
【図 2.3-4】 Apply Settings をクリック
以上で完了です。
導入出来たら、実装例をそのままコピペしてもらえばよいです。ZDD の本筋とは関係ないので解説は省略します。
参考にした記事 ↓（ライブラリの設計思想がなんとなくわかります）
JUNG 2: Javaライブラリ: 篠田孝祐
あとは API とにらめっこしました。
jung2 2.0 API
import javax.swing.JFrame;
import org.apache.commons.collections15.Transformer;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Font;
import java.awt.Paint;
import java.awt.Rectangle;
import java.awt.Shape;
import java.awt.geom.Arc2D;
import edu.uci.ics.jung.algorithms.layout.FRLayout;
import edu.uci.ics.jung.algorithms.layout.Layout;
import edu.uci.ics.jung.graph.DirectedSparseMultigraph;
import edu.uci.ics.jung.visualization.BasicVisualizationServer;
import edu.uci.ics.jung.visualization.decorators.ToStringLabeller;
import edu.uci.ics.jung.visualization.renderers.Renderer.VertexLabel.Position;
import java.util.ArrayDeque;
import java.util.HashSet;
public class ZDD_Visualizer<T> {
public class Vertex{
ZDD<T>.ZDD_Node node;
String label;
public Vertex(ZDD<T>.ZDD_Node node) {
this .node = node;
this .label = setLabel();
}
@Override
public String toString() {
return label;
}
@Override
public boolean equals(Object other) {
if (this == other) return true ;
if (other instanceof ZDD_Visualizer<?>.Vertex o) {
return this .node == o.node;
} else {
return false ;
}
}
@Override
public int hashCode() {
return this .node.hashCode();
}
private String setLabel() {
if (this .node == zdd.zero_terminal) return "⊥" ;
if (this .node == zdd.one_terminal) return "T" ;
return this .node.top.toString();
}
}
public class Edge {
Vertex vFrom;
Vertex vTo;
int label;
public Edge(Vertex vFrom, Vertex vTo, int label) {
this .vFrom = vFrom;
this .vTo = vTo;
this .label = label;
}
}
ZDD<T> zdd;
public ZDD_Visualizer(ZDD<T> zdd) {
this .zdd = zdd;
}
public void visualize(ZDD<T>.ZDD_Node root) {
DirectedSparseMultigraph<Vertex, Edge> graph = new DirectedSparseMultigraph<>();
Vertex vRoot = new Vertex(root);
graph.addVertex(vRoot);
HashSet<Vertex> foundNodes = new HashSet<>();
ArrayDeque<Vertex> queue = new ArrayDeque<>();
queue.add(vRoot);
foundNodes.add(vRoot);
while (!queue.isEmpty()) {
Vertex vNode = queue.poll();
if (vNode.node == zdd.zero_terminal || vNode.node == zdd.one_terminal) continue ;
Vertex vZero = new Vertex(vNode.node.zero);
Vertex vOne = new Vertex(vNode.node.one);
if (!foundNodes.contains(vZero)) {
foundNodes.add(vZero);
graph.addVertex(vZero);
queue.add(vZero);
}
if (!foundNodes.contains(vOne)) {
foundNodes.add(vOne);
graph.addVertex(vOne);
queue.add(vOne);
}
if (!graph.addEdge(new Edge(vNode, vZero, 0 ), vNode, vZero)) System.err.println("can't create" );;
if (!graph.addEdge(new Edge(vNode, vOne, 1 ), vNode, vOne)) System.err.println("can't create" );;
}
Layout layout = new FRLayout(graph);
BasicVisualizationServer visualizationServer = new BasicVisualizationServer(layout, new Dimension(800 , 600 ));
visualizationServer.getRenderContext().setVertexLabelTransformer(new ToStringLabeller<>());
visualizationServer.getRenderer().getVertexLabelRenderer().setPosition(Position.CNTR);
Transformer<Vertex, Font> vertexLabelFontTransformer = new Transformer<>() {
public Font transform(Vertex vertex) {
return new Font(visualizationServer.getFont().getFontName(), Font.BOLD, 24 );
}
};
visualizationServer.getRenderContext().setVertexFontTransformer(vertexLabelFontTransformer);
Transformer<Vertex, Paint> vertexColorTransformer = new Transformer<>() {
public Paint transform(Vertex vertex) {
if (vertex.node == zdd.zero_terminal) return new Color(0xff6666 );
if (vertex.node == zdd.one_terminal) return new Color(0x6666ff );
return Color.WHITE;
}
};
visualizationServer.getRenderContext().setVertexFillPaintTransformer(vertexColorTransformer);
Transformer<Vertex, Shape> vertexShapeTransformer = new Transformer<>() {
public Shape transform(Vertex vertex) {
if (vertex.node == zdd.zero_terminal || vertex.node == zdd.one_terminal) return new Rectangle(-5 ,-5 ,30 ,40 );
return new Arc2D.Double(-7 , -7 , 30 , 30 , 0 , 360 , Arc2D.OPEN);
}
};
visualizationServer.getRenderContext().setVertexShapeTransformer(vertexShapeTransformer);
Transformer<Edge, Paint> edgeColorTransformer = new Transformer<>() {
public Paint transform(Edge edge) {
return edge.label == 0 ? Color.RED : Color.BLUE;
}
};
visualizationServer.getRenderContext().setEdgeDrawPaintTransformer(edgeColorTransformer);
visualizationServer.getRenderContext().setArrowDrawPaintTransformer(edgeColorTransformer);
visualizationServer.getRenderContext().setArrowFillPaintTransformer(edgeColorTransformer);
JFrame frame = new JFrame("ZDD_visualizer" );
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.getContentPane().add(visualizationServer);
frame.pack();
frame.setVisible(true );
}
}
2.4. テスト
import java.util.ArrayList;
import java.util.Arrays;
public class JungTest {
public static void main(String[] args) {
String[] items = {"a" , "b" , "c" };
ArrayList<String> arrayList = new ArrayList<>(Arrays.asList(items));
ZDD<String> zdd = new ZDD<>(arrayList);
ZDD_Visualizer<String> visualizer = new ZDD_Visualizer<>(zdd);
ZDD<String>.ZDD_Node n1 = zdd.get_node("c" , zdd.zero_terminal, zdd.one_terminal);
ZDD<String>.ZDD_Node n2 = zdd.get_node("b" , n1, zdd.one_terminal);
ZDD<String>.ZDD_Node n3 = zdd.get_node("a" , n1, n2);
visualizer.visualize(n3);
}
}
実行結果：
【図 2.4-1】 ZDD_Visualizer による図示
おわりに+次回予告
お疲れ様でした。
今回は ZDD のベースとなる考え方として、再帰 的な構築法を解説しました。
しかし、実際のところまだ ZDD の嬉しさについては全く解説していません。
ZDD のハイパー面白ポイントは部分集合族の“演算”が ZDD 上でも扱える という点にあり、これにより様々な組合せ問題 、すなわち条件を満たす組合せ集合全体からなる部分集合族を求める問題 が簡単に解けてしまうのです。
そして、まさに今回目標としている Daily Akariも組合せ問題の一種で、ZDD の演算だけで解けちゃうわけです。凄い。
次回はそんな ZDD の演算を解説していきます。お楽しみに。
参考文献
S. Minato: "Zero-Suppressed BDDs and Their Applications", International Journal on Software Tools for Technology Transfer, Vol. 3, No. 2, pp. 156-170, Springer, May 2001.
宇宙の原子の数は10^80程度 - よくある誤解と正しい知識
Google Chromeが採用した、擬似乱数生成アルゴリズム「xorshift」の数理 – びりあるの研究ノート
Rolling Hashについて（survey + 研究） | maspyのHP
JUNG 2: Javaライブラリ: 篠田孝祐
jung2 2.0 API
なら、
の根を返す。
の根
なら、0-終端節点を返す。
なら、1-終端節点を返す。
を得て、
を返す。
:
を何かしらの正整数値に飛ばす疑似乱数発生器
:
を何かしらの法
の整数値に飛ばすハッシュ関数
