- 昨日の続き
- 二分決定図 BDD
- グラフ状
- ノードからは2本のエッジが出る(特別な2つのノード,を除く
- エッジには2種類ある
- ノードから出る2本のエッジは2種類が1本ずつ
- ノードには1本以上のエッジが入る(1つのルートノードは例外で、これには入らない)
- ノードのは順序がある(ルートが1番、は末尾でこの2つは同位)
- エッジは順序が先のノードから後のノードにのみ向かう
- ノードはノード順を表すIDと2本のエッジの行く先ノードIDとの3つの情報を持つ
- 「長さのPrimitiveな列」
- 0,1をn個並べてできる二進列は通りある
- これはn個の判断分岐のすべての場合に対応する真理値表情報ともいえる
- 今この長さの真理値情報を前後の2つに分ける
- もし前後2つの長さの二進列が同じだったら、それは、第1の判断分岐によらず、残りの個の判断分岐のみで真理値が決まることを意味する
- 逆に言えば、第1の判断分岐に何かしらの役割があるという状況では、「全長の真理値情報のうち、前半分と後半分とが一致しているような配列は『要らない』」ことになる
- このように前後半が等しいような配列を「Square」と呼ぶ。また、そのような「Square」な配列を排除した残りの配列を「Primitive」であると言う
- クヌース本では、この「Primitiveな配列」を「ビーズ」と呼んでいる
- 「Primitive」についてはこちらを参照
- BDDと「Primitiveな配列」の関係
- BDDの節ノードには「Primitiveな配列」が対応する
- の長さの真理値ベクトルを半分にすることを繰り返して、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)
}
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的な継承関係を取り出してみる
- あるノードからの2本のエッジが同じノードに接続するときは、そのノードは不要なノードなので省略する処理をさらに付け加える必要があるが…
k <- 3
n <- 2^k
x <- list()
x[[1]] <- matrix(sample(0:1,n,replace=TRUE),nrow=1)
Edges <- list()
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)
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
}
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){
tmp2 <- rbind(tmp2,tmp[j,])
Edges[[i-1]][b,a] <- length(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の世界の中での作業になってよい