同一變量排序下的多OBDD合并算法

智慧來

河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南焦作 454000

同一變量排序下的多OBDD合并算法

智慧來

河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南焦作 454000

有序決策圖（OBDD）是一種用于表示布爾表達(dá)式的數(shù)據(jù)結(jié)構(gòu)，并在許多領(lǐng)域得到了廣泛應(yīng)用。在分布式或者動(dòng)態(tài)環(huán)境下，利用已知布爾表達(dá)式的OBDD構(gòu)造目標(biāo)布爾表達(dá)式的OBDD是一個(gè)決定實(shí)際問題解決效率的關(guān)鍵問題?；赟hannon分解原理提出了一個(gè)同一變量排序下的OBDD合并算法。該算法首先建立目標(biāo)布爾表達(dá)式的表存儲(chǔ)模型，然后按照變量排序的逆序，依次處理各個(gè)變量，并且合并取值相同的行，直到所有變量處理完畢。

有序決策圖（OBDD）；同一變量排序；多有序決策圖（OBDD）合并；Apply算法

1 引言

有序二叉決策圖（Ordered Binary Decision Diagram，OBDD）是一種用于表示布爾函數(shù)的數(shù)據(jù)結(jié)構(gòu)[1-2]，是迄今為止最為有效的符號(hào)技術(shù)之一。OBDD已經(jīng)應(yīng)用在粗糙集屬性約簡(jiǎn)表示[3]、局部模式挖掘[4]、并行電力系統(tǒng)恢復(fù)[5]、網(wǎng)絡(luò)可靠性分析[6-7]、約束滿足問題求解[8-10]等眾多領(lǐng)域。

在分布式或者是動(dòng)態(tài)環(huán)境下，利用已知布爾函數(shù)的OBDD構(gòu)造目標(biāo)布爾函數(shù)的OBDD是一個(gè)關(guān)鍵技術(shù)問題。譬如，已知f1、f2和f3的OBDD，構(gòu)造一個(gè)目標(biāo)表達(dá)式f=f1∨(f2∧┐f3)，f的OBDD如何構(gòu)造？

Colorado大學(xué)開發(fā)的CUDD軟件包[11]，里面包含有Apply操作，即

此操作輸入表達(dá)式u1和u2的OBDD，返回表達(dá)式u1op u2的OBDD，其中op是布爾運(yùn)算符。

一個(gè)顯而易見的方法是首先構(gòu)造┐f3的OBDD，然后使用Apply算法求出f2∧┐f3的OBDD，最后再一次使用Apply算法求出的f1∨(f2∧┐f3)的OBDD。顯然，上述過程兩次使用了Apply算法，且每次使用Apply算法都是基于Shannon分解原理的。

到目前為止，現(xiàn)有的研究均是針對(duì)兩個(gè)表達(dá)式的OBDD合成，都沒有涉及多個(gè)表達(dá)式的OBDD合成。例如，古天龍等[12]指出，給定集合S和T，并已知它們的布爾函數(shù)，則集合S和T的并、交和差運(yùn)算等布爾運(yùn)算都可以由相應(yīng)的OBDD操作來高效地加以實(shí)現(xiàn)。愛丁堡大學(xué)的Paul Jackson[13]也對(duì)OBDD操作做了總結(jié)性的研究，指出可以利用Shannon分解原理以及Apply算法對(duì)兩個(gè)表達(dá)式的OBDD進(jìn)行合成。

鑒于上述分析，本文將在Shannon分解原理的基礎(chǔ)上，提出一個(gè)同一變量排序下的多OBDD合并算法，用以構(gòu)造復(fù)合布爾表達(dá)式的OBDD。

2 OBDD及其存儲(chǔ)

OBDD是布爾表達(dá)式的一種有效表示方法，它具有規(guī)范性，即在給定的變量排序下，任一給定的布爾表達(dá)式所對(duì)應(yīng)的OBDD是最簡(jiǎn)且唯一的。

當(dāng)繪制OBDD時(shí)，0分支用虛線表示，1分支用實(shí)線表示，輸出值0和1用葉子結(jié)點(diǎn)表示。OBDD結(jié)構(gòu)體現(xiàn)了Shannon分解原理，即每一個(gè)結(jié)點(diǎn)都是一個(gè)ite（if-then-else）結(jié)構(gòu)。如果用x→f1，f2表示一個(gè)ite(x，f1，f2)結(jié)構(gòu)，則有以下的定義：

顯然，一個(gè)ite(x，f1，f2)結(jié)構(gòu)的意義是：若x成立，則選擇f1分支；否則，選擇f2分支。

在下文中，f[0/x]表示將表達(dá)式f中的變量x用0替換，f[1/x]表示將表達(dá)式f中的變量x用1替換，顯然有：f=x→f[0/x]，f[1/x]，并簡(jiǎn)寫為f=x→f0，f1。

例1有三個(gè)布爾表達(dá)式f1，f2，f3如下：

上述三個(gè)布爾表達(dá)式f1，f2，f3的OBDD如圖1（a）（b）（c）。

另外，還可以采用表格的方式來存儲(chǔ)一個(gè)OBDD，方式如下：每一行存儲(chǔ)一個(gè)結(jié)點(diǎn)的信息；第一列存儲(chǔ)是結(jié)點(diǎn)的標(biāo)識(shí)；第二列，即表頭為var的列，存儲(chǔ)的是結(jié)點(diǎn)表示的變量；第三列，即表頭為0的列，存儲(chǔ)的是結(jié)點(diǎn)的0分支；第四列，即表頭為1的列，存儲(chǔ)的是結(jié)點(diǎn)的1分支。

對(duì)于例1中的三個(gè)布爾表達(dá)式，對(duì)應(yīng)OBDD的表存儲(chǔ)方式見表1（a）（b）（c）。

表1 （a）f1的存儲(chǔ)表

表1 （b）f2的存儲(chǔ)表

表1 （c）f3的存儲(chǔ)表

3 同一變量排序下的多OBDD合并算法

給定義組布爾表達(dá)式f1，f2，…，fm，則可以使用邏輯連接符┐，∨，∧，→，?構(gòu)造出新的布爾表達(dá)式t，即t= F(f1，f2，…，fm)，F(xiàn)表示f1，f2，…，fm的函數(shù)。

同一變量排序下的多OBDD合并，即從f1，f2，…，fm的OBDD出發(fā)，構(gòu)造布爾表達(dá)式t的OBDD。

算法1同一變量排序下的多OBDD合并算法

輸入f1，f2，…，fm的OBDD，布爾表達(dá)式t=F(f1，f2，…，fm)

輸出布爾表達(dá)式t的OBDD

步驟1建立f1，f2，…，fm的OBDD對(duì)應(yīng)的存儲(chǔ)表。

圖1 （a）布爾表達(dá)式f1的OBDD1

圖1 （b）布爾表達(dá)式f2的OBDD2

圖1 （c）布爾表達(dá)式f3的OBDD3

步驟2初始化t的OBDD對(duì)應(yīng)的存儲(chǔ)表如表2所示，每一行存儲(chǔ)一個(gè)結(jié)點(diǎn)，并在存儲(chǔ)表的右側(cè)增加m列，分別存儲(chǔ)該結(jié)點(diǎn)在OBDD1，OBDD2，…，OBDDm中的位置。

表2 初始存儲(chǔ)表

步驟3處理變量xn，使用式子F((t00..00)1，…，(t00..00)m)、F((t00..01)1，…，(t00..01)m)、…、F((t00..01)1，…，(t00..01)m)計(jì)算t00..00、t00..01、…、t11..11的值（共2n-1個(gè)）。

同時(shí)，對(duì)于t00..00、t00..01、…、t11..11中的每一個(gè)行，若取值為（0，0）或（1，1），則將這一行用0或1代替；若t00..00、t00..01、…、t11..11中存在相同的行，則將這些行用同一標(biāo)識(shí)進(jìn)行標(biāo)記。

步驟4設(shè)置循環(huán)變量i并賦初值n-1，當(dāng)i＞0時(shí)循環(huán)執(zhí)行以下操作：

步驟4-1將變量2i個(gè)變量xi+1的值填寫到2i-1個(gè)變量xi的0分支和1分支當(dāng)中。

步驟4-2若取值為（0，0）或（1，1），則將這一行用0或1代替。

步驟4-3在標(biāo)記個(gè)變量xi的這2i-1行中，若存在相同的行，則將這些行用同一標(biāo)識(shí)進(jìn)行標(biāo)記。

步驟4-4將循環(huán)變量i減1，若i＞0，則執(zhí)行步驟4-1，否則循環(huán)結(jié)束。

步驟5刪除冗余行并對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，得到最終的存儲(chǔ)表。

步驟6依據(jù)存儲(chǔ)表建立表達(dá)式的OBDD，算法結(jié)束。

布爾表達(dá)式t=F(f1，f2，…，fm)中變量的數(shù)目決定了存儲(chǔ)表的規(guī)模，存儲(chǔ)變量x1，x2，…，xn所占用的空間是一個(gè)公比為2的等比數(shù)列，因此算法1的空間復(fù)雜度為O(2n)。若以處理一行的時(shí)間作為衡量算法復(fù)雜性的單位時(shí)間，那么算法1的時(shí)間復(fù)雜度為T(2n)。與Apply算法相比，Apply算法一次只能處理一對(duì)表達(dá)式，而本文的算法能夠一次處理任意多個(gè)表達(dá)式，提高了構(gòu)造OBDD的效率。

例1（續(xù)）f=f1∨(f2∧┐f3)，構(gòu)造f的OBDD。

步驟1建立f1，f2，f3的OBDD對(duì)應(yīng)的存儲(chǔ)表，見表1（a）（b）（c）。

步驟2初始化t的OBDD對(duì)應(yīng)的存儲(chǔ)表，如表3所示。

表3 表達(dá)式t的初始化存儲(chǔ)表

步驟3處理變量x3，計(jì)算t00、t01、t10、t11，即

并將t00行的標(biāo)識(shí)修改為0，將t10行的標(biāo)識(shí)修改為1；又因?yàn)閠01和t11相同，所以將t11的標(biāo)識(shí)修改為t01。

步驟4依次處理變量x2，x1：

對(duì)變量x2的處理：對(duì)于結(jié)點(diǎn)t0，0分支為t00，由于t00的標(biāo)識(shí)已經(jīng)修改為0，因此t0的0分支修改為0；對(duì)于結(jié)點(diǎn)t0，0分支為t10，由于t10的標(biāo)識(shí)已經(jīng)修改為1，因此t0的0分支修改為1。

對(duì)變量x1沒有修改，最后得到存儲(chǔ)表見表4。

表4 表達(dá)式t的存儲(chǔ)表

步驟5刪除冗余行并對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，得到最終的存儲(chǔ)表見表5。

步驟6依據(jù)存儲(chǔ)表建立表達(dá)式的OBDD，結(jié)果見圖2。

表5 重新編號(hào)后表達(dá)式t的存儲(chǔ)表

圖2 布爾表達(dá)式f1∨(f2∧┐f3)的OBDD

4 結(jié)束語

在OBDD的應(yīng)用中，利用已知布爾函數(shù)的OBDD構(gòu)造目標(biāo)布爾函數(shù)的OBDD是一個(gè)關(guān)鍵問題。本文利用OBDD的表存儲(chǔ)模型，基于Shannon分解原理提出了一個(gè)同一變量排序下的OBDD合并算法。與Apply算法相比，Apply算法一次只能處理一對(duì)表達(dá)式，而本文的算法能夠一次處理任意多個(gè)表達(dá)式，提高了構(gòu)造OBDD的效率。

[1]Akers S B.Binary decision diagrams[J].IEEE Transactions on Computer，1978，27（6）：509-516.

[2]Bryant R E.Graph based algorithms for Boolean function manipulation[J].IEEE Transactions on Computer，1986，35（8）：677-691.

[3]Wei Qianjin，Gu Tianlong.Symbolic representation for rough set attribute reduction using ordered binary decision diagrams[J].Journal of Software，2011，6（6）：977-984.

[4]Yang Liu，M anadhata P K，Horne W G，et al.Fast submatch extraction using OBDDs[R].[S.l.]：HP Laboratories，2012.

[5]Wang Chong，Vittal V，Sun K.OBDD-based sectionalizing strategies for parallel power system restoration[J].IEEE Transactions on Power System s，2011，26（3）：1426-1433.

[6]陳瑤，李峭，趙長嘯，等.基于OBDD的航空電子網(wǎng)絡(luò)可靠性分析[J].系統(tǒng)工程與電子技術(shù)，2013，35（1）：230-236.

[7]趙勃，肖宇峰，劉巖.基于OBDD的通信網(wǎng)鏈路重要性評(píng)估[J].系統(tǒng)工程與電子技術(shù)，2011，33（10）：2348-2352.

[8]徐周波，古天龍，常亮，等.約束滿足問題求解的符號(hào)OBDD桶消元算法[J].計(jì)算機(jī)科學(xué)，2011，38（7）：200-203.

[9]徐周波，古天龍.裝配序列規(guī)劃問題的CSP模型及其符號(hào)OBDD求解技術(shù)[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2010，22（5）：803-810.

[10]古天龍，楊志飛.基于有序二叉決策圖的裝配序列符號(hào)表示方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2007，19（10）：1315-1320.

[11]Somenzi F.CUDD：CU decision diagram package release 2.4.1[EB/OL].[2013-09-11].http：//vlsi.Colorado.edu/fabio/ CUDD/cudd Intro.htm l.

[12]古天龍，呂思菁，常亮，等.基于OBDD的描述邏輯εL循環(huán)術(shù)語集推理[J].軟件學(xué)報(bào)，2014，25（1）：64-77.

[13]Jackson P.BDD operations[EB/OL].[2013-12-21].www.inf. ed.ac.uk/teaching/courses/ar/slides/bdd-ops.pdf.

ZHI Huilai

School of Computer Science and Technology, Henan Polytechnic University, Jiaozuo, Henan 454000, China

Ordered Binary Decision Diagrams（OBDD）is a Boolean function representation data structure, and has been applied in many fields. In dynamic or distribute environment, how to efficiently build OBDD of the target Boolean expression form the known Boolean expression’s OBDD is a frequent encountered problem. Under identical variable ordering,this paper puts forward a OBDD merging algorithm based on Shannon decomposition principle. In the algorithm, it firstly establishes a storage table for the target Boolean expression, and then under the reverse variable ordering it handles each variable in turn, and combines the rows with same values, until all the variables are handled.

words：Ordered Binary Decision Diagrams（OBDD）; identical variable ordering; multiple Ordered Binary Decision Diagrams（OBDD）merging; Apply algorithm

ZHI Huilai. Multiple OBDD merging algorithm under same variable ordering. Computer Engineering and Applications,2014, 50（17）：20-23.

A

TP18

10.3778/j.issn.1002-8331.1312-0067

國家自然科學(xué)基金（No.60975033）；河南理工大學(xué)博士基金（No.B2011-102）。

智慧來（1981—），男，博士，講師，研究領(lǐng)域包括形式概念分析、知識(shí)表示與推理等。E-mail：zhihuilai@126.com

2013-12-05

2014-03-10

1002-8331（2014）17-0020-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2014-03-19,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1312-0067.htm l