おねえさんを組み合わせ爆発から救う：ZDDがおねえさんを救う

おねえさんを組み合わせ爆発から救うために、経路をBDDとして表しました。
http://d.hatena.ne.jp/nowokay/20121017#1350435805

ところで、「F」に至る経路で、ある辺を通るとした場合に即「F」となっているものが半分あります。
その節点を使うとしたときに、結果が偽になるのであれば、それは節点ごと不要だと言えます。そこで、そのような節点は省略してしまいます。

このような図を、ゼロ抑制BDD(Zero suppressed BDD)、略してZDDと呼びます。
「F」をすべて省略することもできます。ただし、BDDとは違って、どちらでも同じ結果になる場合も、それぞれの接続を表示する必要があります。

そうすると、2x2マスの経路でも、次のように表すことができます。かなり節点の数が減っていることがわかります。

「T」に至るパスの数が、経路の数です。

さまざまな組み合わせをBDDで表示すると、ある項目を使うとした場合にFになるということがかなり多くあります。ZDDは、このような、組み合わせを効率よく保持する図だといえます。

3x3マスの場合もちょっとすっきりしてます。

ところで、1x1マスの場合はどうなったかというと、こんなに単純になっています。経路の組み合わせも一目瞭然です。

最初の二分決定木と比べると、まったくわかりやすさが違います。

まるで、宇宙人襲来といって、こういうイメージを持って対策していたのが、

実際の宇宙人はこんな感じだった、という拍子抜け感です。

これで、おねえさんを組み合わせ爆発から救うことができそうです。
ただ、ZDDが経路をコンパクトに保持するとはいえ、ZDDの構築ではあいかわらず組み合わせ爆発が起きてしまっています。問題は、このようなZDDをいかに効率よく構築するか、ということになります。

ZDDについては、The Art of Computer Proguramingの7.1.4で解説されています。本編でのページ数は少ないですが、演習問題でかなりのページが割かれています。

The Art of Computer Programming Volume 4, Fascicle 1 Bitwise Tricks & Techniques; Binary Decision Diagarms 日本語版 (ASCII Addison Wesley Programming Se)

目次
『フカシギの数え方』 おねえさんといっしょにみんなも25万年数えよう
おねえさんを組み合わせ爆発から救う：格子グラフを生成する
おねえさんを組み合わせ爆発から救う：2分決定木を作る
おねえさんを組み合わせ爆発から救う：無駄を省いてBDDを作る
おねえさんを組み合わせ爆発から救う：ZDDがおねえさんを救う
おねえさんを組み合わせ爆発から救う：完結編おねえさんは星になった

ソースはこちら。BDD構築の場合と、ほとんど変わっていません。実行には、ここまでの3つのソースも必要です。

package simpath;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import kis.jgraphsample.CreateBdd.ThroughNode;
import kis.jgraphsample.CreateLattice.LatticeEdge;
import kis.jgraphsample.CreateTree.DiagramNode;
import kis.jgraphsample.CreateTree.EdgeNode;
import kis.jgraphsample.CreateTree.LeafNode;

public class CreateZdd {
    public static void main(String[] args){
        //格子グラフの生成
        ArrayList<CreateLattice.LatticeEdge> edges = new ArrayList<>();
        Map<Integer, CreateLattice.LatticeNode> nodeMap = new LinkedHashMap<>();
        CreateLattice.generateGraph(3, nodeMap, edges);

        String param = CreateBdd.solveRoute(edges, nodeMap);
        
        //BDDの生成
        //param = "fftftffffftftffffftfttfftftffftt";
        List<List<DiagramNode>> layers = createZdd(edges, param);
        
        //表示
        //CreateTree.paintDiagram(layers, 250, 250, 40, 50);
        CreateTree.paintDiagram(layers, 400, 640, 40, 50);
        //CreateTree.paintDiagram(layers, 1150, 800, 35, 30);
    }
    /** BDDの生成 */
    static List<List<DiagramNode>> createZdd(ArrayList<LatticeEdge> edges, String param) {
        List<List<CreateTree.DiagramNode>> layers = new ArrayList<>();
        List<DiagramNode> layer = new ArrayList<>();
        layers.add(layer);
        Map<String, CreateTree.EdgeNode> edgeMap = new HashMap<>();
        ThroughNode tn = new ThroughNode();
        createZdd(layers, edges, edgeMap, 0, param, tn, false);
        return layers;
    }
    /** BDD各ノードの生成 */
    static void createZdd(List<List<CreateTree.DiagramNode>> layers,
            ArrayList<CreateLattice.LatticeEdge> edges,
            Map<String, CreateTree.EdgeNode> edgeMap,
            int height, String param, EdgeNode en, boolean pre)
    {

        if(layers.size() <= height){
            layers.add(new ArrayList<DiagramNode>());
        }
        List<DiagramNode> layer = layers.get(height);
        
        LeafNode ln = null;
        if(param.equals("t")){
            //tの終端
            ln = new CreateTree.LeafNode(true);
        }else if(param.indexOf("t") < 0){
            //fだけのときは非表示
            return;
        }
        if(ln != null){
            //ｔ・fが決まった
            if(pre){
                en.right = ln;
            }else{
                en.left = ln;
            }
            layer.add(ln);
            return;
        }

        String left = param.substring(0, param.length() / 2);
        String right = param.substring(param.length() / 2);
        if(right.indexOf("t") < 0){
            //右がf
            ThroughNode tn = new ThroughNode();
            if(pre){
                en.right = tn;
            }else{
                en.left = tn;
            }
            layer.add(tn);
            //くりかえす
            createZdd(layers, edges, edgeMap, height+1, left, tn, pre);
            return;
        }
        //分岐の生成
        EdgeNode nn = edgeMap.get(param);
        boolean gen = false;
        if(nn == null){
            //新しくでた組み合わせ
            gen = true;
            LatticeEdge le = edges.get(height);
            nn = new EdgeNode(le);
            layer.add(nn);
            edgeMap.put(param, nn);
        }
        if(pre){
            en.right = nn;
        }else{
            en.left = nn;
        }
        //くりかえす
        if(gen){
            createZdd(layers, edges, edgeMap, height+1, left, nn, false);
            createZdd(layers, edges, edgeMap, height+1, right, nn, true);
        }
    }
}