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

前言

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

內(nèi)容概要

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

書籍目錄

前言第1章 布爾表達式及其描述  1.1 布爾函數(shù)    1.1.1 布爾代數(shù)    1.1.2 布爾表達式    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 布爾表達式的其他描述形式    1.4.1 真值表    1.4.2 決策樹    1.4.3 二叉決策圖  參考文獻第2章 有序二叉決策圖  2.1 OBDD及其規(guī)范型    2.1.1 OBDD的定義    2.1.2 OBDD的性質(zhì)  2.2 OBDD的簡化算法    2.2.1 OBDD的簡化    2.2.2 簡化算法  2.3 OBDD的構(gòu)造及操作    2.3.1 ()BDD的構(gòu)造    2.3.2 OBDD的操作    2.3.3 補邊OBDD  2.4 OBDD的變量序    2.4.1 OBDD的最小化    2.4.2 OBDD的重排序    2.4.3 OBDD的變量序算法  參考文獻第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 補邊ZBDD  3.3 一元Cube集合代數(shù)    3.3.1 基本概念    3.3.2 基本運算    3.3.3 算法實現(xiàn)    3.3.4 皇后問題的求解  3.4 二元Cube集合代數(shù)    3.4.1 二元Cube集的表示    3.4.2 基本操作及算法    3.4.3 數(shù)字電路設(shè)計  3.5 多項式的隱式表示    3.5.1 變量次數(shù)的表示    3.5.2 多項式系數(shù)的表示    3.5.3 算術(shù)操作的算法實現(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 矩陣乘法計算    4.3.1 準環(huán)和半環(huán)    4.3.2 半環(huán)上的矩陣乘算法    4.3.3 準環(huán)上的矩陣乘算法  參考文獻第5章 邊值二叉決策圖第6章 二叉矩量圖第7章 時間變量決策圖第8章 應(yīng)用專題

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

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

---