2012-11-11

BBD:ぱらぱらめくる『クヌース本4.1』

昨日の続き
二分決定図 BDD
- グラフ状
  - ノードとエッジがある
- ノードからは２本のエッジが出る(特別な２つのノード $\top$ , $\bot$ を除く
- エッジには２種類ある
- ノードから出る２本のエッジは２種類が１本ずつ
- ノードには１本以上のエッジが入る(１つのルートノードは例外で、これには入らない)
- ノードのは順序がある(ルートが１番、 $\top,\bot$ は末尾でこの２つは同位)
- エッジは順序が先のノードから後のノードにのみ向かう
  - ノードはノード順を表すIDと２本のエッジの行く先ノードIDとの３つの情報を持つ
「長さのPrimitiveな列」
- 0,1をn個並べてできる二進列は $2^n$ 通りある
- これはn個の判断分岐のすべての場合に対応する真理値表情報ともいえる
- 今この長さ $2^n$ の真理値情報を前後の２つに分ける
- もし前後２つの長さ $2^{n-1}$ の二進列が同じだったら、それは、第１の判断分岐によらず、残りの $n-1$ 個の判断分岐のみで真理値が決まることを意味する
- 逆に言えば、第１の判断分岐に何かしらの役割があるという状況では、「全長 $2^n$ の真理値情報のうち、前半分と後半分とが一致しているような配列は『要らない』」ことになる
- このように前後半が等しいような配列を「Square」と呼ぶ。また、そのような「Square」な配列を排除した残りの配列を「Primitive」であると言う
- クヌース本では、この「Primitiveな配列」を「ビーズ」と呼んでいる
- 「Primitive」についてはこちらを参照
BDDと「Primitiveな配列」の関係
- BDDの節ノードには「Primitiveな配列」が対応する
- $2^n$ の長さの真理値ベクトルを半分にすることを繰り返して、BDDノードに「Primitiveな配列」を取り出してみる

k <- 3
n <- 2^k
x <- list()
x[[1]] <- matrix(sample(0:1,n,replace=TRUE),nrow=1)

for(i in 2:(k+1)){
	print(x[[i-1]])
	print("-")
	if(i != (k+1)){
		tmp <- rbind(x[[i-1]][,1:2^(k-i+1)],x[[i-1]][,(1+2^(k-i+1)):2^(k-i+2)])
	}else{
		tmp <- matrix(c(x[[i-1]][,1:2^(k-i+1)],x[[i-1]][,(1+2^(k-i+1)):2^(k-i+2)]),ncol=1)
	}
	
	#print(tmp)
	tmp2 <- matrix(tmp[1,],nrow=1)
	for(j in 2:length(tmp[,1])){
		check <- TRUE
		for(j2 in 1:length(tmp2[,1])){
			if(sum(abs(tmp2[j2,]-tmp[j,]))==0){
				check <- FALSE
			}
		}
		if(check){
			tmp2 <- rbind(tmp2,tmp[j,])
		}
	}
	
	x[[i]] <- tmp2
}
x

> x
[[1]]
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
[1,]    1    1    1    1    1    0    1    0

[[2]]
     [,1] [,2] [,3] [,4]
[1,]    1    1    1    1
[2,]    1    0    1    0

[[3]]
     [,1] [,2]
[1,]    1    1
[2,]    1    0

[[4]]
     [,1]
[1,]    1
[2,]    0

- 長さの真偽値配列からBDD的な継承関係を取り出してみる
  - あるノードからの２本のエッジが同じノードに接続するときは、そのノードは不要なノードなので省略する処理をさらに付け加える必要があるが…

k <- 3
n <- 2^k
x <- list()
x[[1]] <- matrix(sample(0:1,n,replace=TRUE),nrow=1)
Edges <- list()
#Nodes <- matrix(c(1,1),nrow=1)
for(i in 2:(k+1)){
	print(x[[i-1]])
	print("-")
	if(i != (k+1)){
		tmp <- rbind(x[[i-1]][,1:2^(k-i+1)],x[[i-1]][,(1+2^(k-i+1)):2^(k-i+2)])
	}else{
		tmp <- matrix(c(x[[i-1]][,1:2^(k-i+1)],x[[i-1]][,(1+2^(k-i+1)):2^(k-i+2)]),ncol=1)
	}
	Edges[[i-1]] <- matrix(0,length(x[[i-1]][,1]),2)
	#print(tmp)
	tmp2 <- matrix(tmp[1,],nrow=1)
	a <- 1
	b <- 1
	Edges[[i-1]][b,a] <- length(tmp2[,1])
	b <- b+1
	if(b==length(x[[i-1]][,1])+1){
		b <- 1
		a <- a+1
	}

	#cnt <- 1
	for(j in 2:length(tmp[,1])){
		check <- TRUE
		for(j2 in 1:length(tmp2[,1])){
			if(sum(abs(tmp2[j2,]-tmp[j,]))==0){
				Edges[[i-1]][b,a] <- j2
				check <- FALSE
			}
		}
		if(check){
			#cnt <- cnt +1
			tmp2 <- rbind(tmp2,tmp[j,])
			Edges[[i-1]][b,a] <- length(tmp2[,1])
			#Nodes <- rbind(Nodes,c(i,tmp2[,1]))
		}
		b <- b+1
		if(b==length(x[[i-1]][,1])+1){
			b <- 1
			a <- a+1
		}
	}
	
	x[[i]] <- tmp2
}
x
Edges

> x
[[1]]
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
[1,]    1    1    0    1    1    1    1    0

[[2]]
     [,1] [,2] [,3] [,4]
[1,]    1    1    0    1
[2,]    1    1    1    0

[[3]]
     [,1] [,2]
[1,]    1    1
[2,]    0    1
[3,]    1    0

[[4]]
     [,1]
[1,]    1
[2,]    0

> Edges
[[1]]
     [,1] [,2]
[1,]    1    2

[[2]]
     [,1] [,2]
[1,]    1    2
[2,]    1    3

[[3]]
     [,1] [,2]
[1,]    1    1
[2,]    2    1
[3,]    1    2

二つのBBDの合成BBDを作ることができる
BDDは変数の順序に依存するから、変数の順序に関する最適化の問題というのが出てくる
- 順序を変えるのに応じてBDDを変化させることもできるとBDDの世界の中での作業になってよい