有序二叉決策圖及應(yīng)用

前言

　　布爾代數(shù)是計(jì)算機(jī)科學(xué)和邏輯系統(tǒng)設(shè)計(jì)的重要基石。VLSI系統(tǒng)CAD、軟件測(cè)試和驗(yàn)證、AI規(guī)劃與調(diào)度等領(lǐng)域中的諸多問(wèn)題都?xì)w結(jié)為邏輯函數(shù)及其序列的操作和運(yùn)算。毫無(wú)疑問(wèn)，布爾函數(shù)的表述及其操作對(duì)這些領(lǐng)域中問(wèn)題的合理有效解決起著尤為關(guān)鍵的作用。不幸的是，布爾函數(shù)的可滿足性和等價(jià)性等問(wèn)題的NP完備性所導(dǎo)致的狀態(tài)組合爆炸問(wèn)題嚴(yán)重地制約了大規(guī)模、甚至工業(yè)小規(guī)模問(wèn)題的解決。然而，在實(shí)際問(wèn)題的處理中，對(duì)布爾函數(shù)采取恰當(dāng)?shù)拿枋霾⒔⑾鄳?yīng)描述下的操作算法，可以有效地減緩甚至避免問(wèn)題處理過(guò)程中的狀態(tài)組合復(fù)雜性。有序二叉決策圖（ordered binary decision diagram，0BDD）則是該方面的有益探索和結(jié)果。　　0BDD是一種新型數(shù)據(jù)結(jié)構(gòu)，是迄今為止布爾函數(shù)表述和操作中最為有效的技術(shù)之一。人們對(duì)它的研究最早可追溯到20世紀(jì)50年代Lee的二叉決策程序和20世紀(jì)70年代Aker’s的二叉決策圖（binary decision diagram，BDD）概念。20世紀(jì)80年代Bryant對(duì)BDD附加了變量序和簡(jiǎn)化約束，使之成為布爾表達(dá)式表述的一種規(guī)范型，即OBDD。OB—DD不同于BDD之處在于，OBDD中任一從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑上變量出現(xiàn)的順序保持一致。這一變量序的限制，使得OBDD成為表述布爾函數(shù)的規(guī)范式。Bryant關(guān)于OB—DD構(gòu)造和操作的圖形算法，極大地推進(jìn)了OBDD的廣泛深入研究。為了滿足能夠表述非0—1數(shù)值函數(shù)的應(yīng)用需求，建立了多端二叉決策圖（multi—terminal binary decision dia—gram，MTBDD）、代數(shù)決策圖（algebraic decision diagr。am，ADD）、邊值二叉決策圖（edge—valued binary decision diagram，EVBD[））、二叉矩量圖（binary moment diagram，BMD）等。除BMD之外，OBDD及上述這些擴(kuò)展形式都是依據(jù)布爾函數(shù)的香農(nóng)（Shannon）分解而構(gòu)造的。Kebsehull等基于正Davio分解提出了有序函數(shù)決策圖（ordered functionaldecision diagram，OFDD）；Drechsler等將OBDD和正Davio分解及負(fù)Davio分解復(fù)合，建立了有序Kronecker函數(shù)決策圖（ordered Kronecker functional decision diagram，0KFDD）。在OFDD的基礎(chǔ)上，Bryant和Chen提出了基于正Davio分解規(guī)則的二叉矩量圖。此外，Minato通過(guò)采取不同的簡(jiǎn)化策略給出了適合于組合問(wèn)題有效處理的零壓縮二叉決策圖（zero—suppressed binarly decision diagram，ZBDD）。OBDD中的變量順序的選擇也是研究人員關(guān)注的重要問(wèn)題，研究人員已開(kāi)展了動(dòng)態(tài)變量序、最優(yōu)變量序、啟發(fā)式變量序、無(wú)變量序限制的自由BDD等的研究。

內(nèi)容概要

有序二叉決策圖是布爾函數(shù)的一種規(guī)范表達(dá)形式、一種新型數(shù)據(jù)結(jié)構(gòu)?；?)BDD可以完成布爾函數(shù)的有效表述和操作運(yùn)算，OBDD在VKSI邏輯綜合和驗(yàn)證方面的成功應(yīng)用引起了學(xué)術(shù)界和工業(yè)應(yīng)用界的極大關(guān)注。本書對(duì)()BDD相關(guān)技術(shù)問(wèn)題、()BDD擴(kuò)展形式、()BDD應(yīng)用等方面進(jìn)行了介紹和討淪，主要內(nèi)容包括布爾表達(dá)式及其描述、有序二叉決策網(wǎng)、零壓縮二叉決策圖、代數(shù)決策圖、邊值二叉決策圖、二叉矩量圖、時(shí)問(wèn)變量決策圖、應(yīng)用專題等。    本書可供高零院校計(jì)算機(jī)、電子工程、自動(dòng)化等專業(yè)的高年級(jí)本科生、研究生以及相關(guān)領(lǐng)域的科研和工程技術(shù)人員參考。

書籍目錄

前言第1章 布爾表達(dá)式及其描述  1.1 布爾函數(shù)    1.1.1 布爾代數(shù)    1.1.2 布爾表達(dá)式    1.1.3 布爾函數(shù)    1.1.4 布爾函數(shù)的范式    1.2 命題公式    1.2.1 命題與聯(lián)結(jié)詞    1.2.2 合式公式    1.2.3 命題公式的范式    1.2.4 命題公式與布爾函數(shù)  1.3 邏輯電路    1.3.1 基本邏輯門    1.3.2 邏輯電路的布爾函數(shù)  1.4 布爾表達(dá)式的其他描述形式    1.4.1 真值表    1.4.2 決策樹    1.4.3 二叉決策圖  參考文獻(xiàn)第2章 有序二叉決策圖  2.1 OBDD及其規(guī)范型    2.1.1 OBDD的定義    2.1.2 OBDD的性質(zhì)  2.2 OBDD的簡(jiǎn)化算法    2.2.1 OBDD的簡(jiǎn)化    2.2.2 簡(jiǎn)化算法  2.3 OBDD的構(gòu)造及操作    2.3.1 ()BDD的構(gòu)造    2.3.2 OBDD的操作    2.3.3 補(bǔ)邊OBDD  2.4 OBDD的變量序    2.4.1 OBDD的最小化    2.4.2 OBDD的重排序    2.4.3 OBDD的變量序算法  參考文獻(xiàn)第3章 零壓縮二叉決策圖  3.1 ZBDD及其性質(zhì)    3.1.1 組合集合及其表示    3.1.2 ZBDD的定義    3.1.3 ZBDD的性質(zhì)  3.2 ZBDD的構(gòu)造及基本操作    3.2.1 ZBDD的操作    3.2.2 ZBDD的構(gòu)造    3.2.3 補(bǔ)邊ZBDD  3.3 一元Cube集合代數(shù)    3.3.1 基本概念    3.3.2 基本運(yùn)算    3.3.3 算法實(shí)現(xiàn)    3.3.4 皇后問(wèn)題的求解  3.4 二元Cube集合代數(shù)    3.4.1 二元Cube集的表示    3.4.2 基本操作及算法    3.4.3 數(shù)字電路設(shè)計(jì)  3.5 多項(xiàng)式的隱式表示    3.5.1 變量次數(shù)的表示    3.5.2 多項(xiàng)式系數(shù)的表示    3.5.3 算術(shù)操作的算法實(shí)現(xiàn)  參考文獻(xiàn)第4章 代數(shù)決策圖  4.1 ADD及其性質(zhì)    4.1.1 ADD的定義      4.1.2 ADD的矩陣表示  4.2 ADD基本操作    4.2.1 布爾操作    4.2.2 算術(shù)操作    4.2.3 提取操作  4.3 矩陣乘法計(jì)算    4.3.1 準(zhǔn)環(huán)和半環(huán)    4.3.2 半環(huán)上的矩陣乘算法    4.3.3 準(zhǔn)環(huán)上的矩陣乘算法  參考文獻(xiàn)第5章 邊值二叉決策圖第6章 二叉矩量圖第7章 時(shí)間變量決策圖第8章 應(yīng)用專題

圖書封面

圖書標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    有序二叉決策圖及應(yīng)用 PDF格式下載

---