おねえさんを組み合わせ爆発から救うために、経路を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で解説されています。本編でのページ数は少ないですが、演習問題でかなりのページが割かれています。
- 作者: Donald E. Knuth,和田英一
- 出版社/メーカー: アスキー・メディアワークス
- 発売日: 2011/05/20
- メディア: 大型本
- 購入: 2人 クリック: 17回
- この商品を含むブログ (14件) を見る
目次
『フカシギの数え方』 おねえさんといっしょにみんなも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){ //t・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); } } }