葉雄 楊皓棟

摘要

布爾函數(shù)的可滿足性和等價(jià)性等問題的NP完備性所導(dǎo)致的狀態(tài)組合爆炸問題嚴(yán)重地限制了大規(guī)模、甚至工業(yè)小規(guī)模問題的解決。然而在實(shí)際問題的處理中，對布爾函數(shù)采取恰當(dāng)?shù)拿枋霾⒔⑾鄳?yīng)描述下的操作算法，可以有效地減緩甚至避免問題處理過程中的狀態(tài)組合復(fù)雜性。而本文就是利用了OBDD來建立布爾函數(shù)模型并求解實(shí)際問題，結(jié)果在效率上較傳統(tǒng)方法有很大提升。

【關(guān)鍵詞】組合優(yōu)化 布爾函數(shù) 有序二又決策圖

1 前言

組合優(yōu)化（Combinatorial Optimization）問題，是通過對數(shù)學(xué)方法的研究去尋找離散事件的最優(yōu)編排、分組、次序或篩選等，是運(yùn)籌學(xué)的一個(gè)重要分支。所研究的問題涉及信息技術(shù)、經(jīng)濟(jì)管理、工業(yè)工程、交通運(yùn)輸、通信網(wǎng)絡(luò)等領(lǐng)域。典型的組合優(yōu)化問題有旅行商問題、組合調(diào)度問題等。這一類問題的描述都非常簡單，并且具有很強(qiáng)的工程代表性，但最優(yōu)化求解很困難，其主要原因是求解這些問題的算法需要極長的運(yùn)行時(shí)間和極大的儲存空間，即所謂的“組合爆炸”。然而隨著電子技術(shù)的快速發(fā)展，計(jì)算機(jī)的內(nèi)存空間越來越大，充分利用內(nèi)存空間計(jì)算組合爆炸問題來減少時(shí)間上的消耗，是一種有效的解決方案，那么廣度優(yōu)先搜索（Breadth-First Search，BFS）正是最廣泛的選擇。而BFS最核心的問題，是如何組織和儲存狀態(tài)數(shù)據(jù)，還有重復(fù)狀態(tài)的判定。古天龍?zhí)岢龅挠行蚨鏇Q策圖（Ordered BinaryDecision Diagrams，OBDD），一種基于二叉決策樹（Binary Decision Diagrams，BDD）的新型數(shù)據(jù)結(jié)構(gòu)，則是該方面問題很有效的解決方案。本文將介紹如何通過使用基于有序二叉決策圖的BFS和簡單的并行計(jì)算（ParallelComputing）來對組合優(yōu)化問題進(jìn)行快速求解。

2 有序二叉決策圖

有序二叉決策圖（Ordered Binary DecisionDiagrams，OBDD）是一種基于符號的新型數(shù)據(jù)結(jié)構(gòu)，是布爾函數(shù)的一種有效圖形、數(shù)學(xué)描述技術(shù)，是迄今為止布爾函數(shù)表述和操作中最為有效的技術(shù)之一。OBDD的本質(zhì)是一種對布爾函數(shù)的有序壓縮表達(dá)方式，可以高效地實(shí)現(xiàn)相應(yīng)函數(shù)的運(yùn)算功能，從而達(dá)到僅僅使用少許的數(shù)據(jù)結(jié)構(gòu)就能表示和處理大規(guī)模復(fù)雜的數(shù)據(jù)集的目的。因此OBDD在組合優(yōu)化問題的研究領(lǐng)域中，在保證獲得精準(zhǔn)結(jié)果的情況下能很好地實(shí)現(xiàn)時(shí)間與空間上的優(yōu)化。OBDD具體可以描述為：

二叉決策圖（Binary Decision Diagrams，BDD）：對于從{0，1}ⁿ到{0，1}的布爾函數(shù)f（x₁，x₂，…，x_n），BDD是用于表示布爾函數(shù)族#f（x₁，x₂，…，x_n）的一個(gè)有向無環(huán)圖，它滿足：

（1）BDD中節(jié)點(diǎn)分為根節(jié)點(diǎn)、終節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)三類。沒有父輩節(jié)點(diǎn)或者沒有輸入弧的節(jié)點(diǎn)稱為根節(jié)點(diǎn);沒有后繼子節(jié)點(diǎn)或者沒有輸出弧的節(jié)點(diǎn)稱為終節(jié)點(diǎn);除根節(jié)點(diǎn)和終節(jié)點(diǎn)之外的節(jié)點(diǎn)或者具有輸入和輸出弧的節(jié)點(diǎn)稱為內(nèi)部節(jié)點(diǎn);

（2）終節(jié)點(diǎn)有2個(gè)，分別標(biāo)記為0和1。終節(jié)點(diǎn)t具有屬性r.val∈{0，1}，表示布爾常量0和1;

（3）非終節(jié)點(diǎn)u具有四元組屬性（f^u，var，low，high），其中，f^u表示節(jié)點(diǎn)u所對應(yīng)的布爾函數(shù)，f^u∈#f（x₁，x₂，…，x_n）（如果u是根節(jié)點(diǎn)，則f^u=f（x₁，x₂，…，x_n））var表示節(jié)點(diǎn)u的標(biāo)記變量;low表示u.var=0（節(jié)點(diǎn)u的標(biāo)記變量var取值為0）時(shí)，節(jié)點(diǎn)u的0-分枝子節(jié)點(diǎn);high表示u.va2=1（節(jié)點(diǎn)u的標(biāo)記變量var取值為1）時(shí)，節(jié)點(diǎn)u的1-分枝子節(jié)點(diǎn);

（4）每個(gè)非終節(jié)點(diǎn)均具有兩條輸出分枝弧，將它們和各自的兩個(gè)分枝子節(jié)點(diǎn)連接在一起。節(jié)點(diǎn)u和u.low的連接弧稱為0-邊，節(jié)點(diǎn)u和u.high的連接弧稱為1-邊;

（5）BDD的任一有向路徑上，布爾函數(shù)f（x₁，x₂，…，x_n）中的每個(gè)變量至多出現(xiàn)一次。在圖1表示中，通常用方框表示終節(jié)點(diǎn)，用圓圈表示其它節(jié)點(diǎn)，節(jié)點(diǎn)之間通過虛線或者實(shí)線連接。通常，假設(shè)連接弧的方向向下，0-邊用虛線表示，卜邊用實(shí)線表示。

定義1：對于從{0，1}ⁿ到{0，1}的布爾函數(shù)f（x₁，x₂，…，x_n）和定變量序π，在表示布爾函數(shù)族#f（x₁，x₂，…，x_n）的BDD中，如果任一有向路徑上的變量x₁，x₂，…，x_s均以變量序π所規(guī)定的的次序依次出現(xiàn)，則稱該BDD為布爾函數(shù)f（x₁，x₂，…，x_n）的有序二叉決策圖。

定義2：每個(gè)OBDD上的節(jié)點(diǎn)u代表了一個(gè)從{0，1}ⁿ到{0，1}的布爾函數(shù)fⁿ滿足：

（1）若u是終結(jié)點(diǎn)，則：

f^u=u.val

（2）若u是非終節(jié)點(diǎn)，則：

其中u.var取值1和0后得到的布爾函數(shù)，即節(jié)點(diǎn)u的子節(jié)點(diǎn)uligh和u.low所對應(yīng)的布爾函數(shù)。如圖2所示。

3 問題描述

本文通過求解一個(gè)組合優(yōu)化問題的實(shí)例Solitare Game來達(dá)到研究的目的。問題可以簡單描述為：在一個(gè)指定規(guī)模（規(guī)?？杀硎緸镹-m，即在NXN的正方形棋盤上挖去4個(gè)m×m的角落。圖3表示了一個(gè)7-2規(guī)模的棋盤）的格子棋盤上，有若干棋子，每次合法移動(dòng)能消除一枚棋子，給定起始和終止?fàn)顟B(tài)，求解移動(dòng)路徑。設(shè)棋盤的規(guī)模為n，即有n個(gè)格子，不失一般性地設(shè)起始狀態(tài)為棋盤中有n個(gè)棋子，終止?fàn)顟B(tài)中無棋子，則移動(dòng)的步數(shù)為n步，在第步移動(dòng)時(shí)可以選擇的移動(dòng)方式有剩余棋子數(shù)（n-i+1）乘以4個(gè)方向，即4（n-i+1），則總狀態(tài)數(shù)為40n！。我們將采用并行雙向廣度優(yōu)先搜索算法來實(shí)現(xiàn)求解，通過OBDD數(shù)據(jù)結(jié)構(gòu)來加快運(yùn)算速度和減小空間占用。

本文先以7-2規(guī)模的棋盤為例講解算法原理，最后使用多種規(guī)模測試。

4 并行雙向廣度優(yōu)先搜索算法

雙向廣度優(yōu)先搜索算法，顧名思義，就是分別從起始狀態(tài)和終止?fàn)顟B(tài)開始廣度優(yōu)先搜索。當(dāng)兩個(gè)搜索相遇，即搜索到同一狀態(tài)時(shí)，搜索結(jié)束，相遇的這一狀態(tài)及其搜索路徑為問題的最優(yōu)解。雙向廣度優(yōu)先搜索的過程如圖4。因?yàn)閺V度優(yōu)先搜索的完備性和其能搜索最優(yōu)解的特點(diǎn)，可以保證搜索不會遺漏解，并且如果有解則解時(shí)最優(yōu)的。

因?yàn)榻M合優(yōu)化問題的不可預(yù)測性，我們很難使用啟發(fā)式搜索算法來求解，故采用能求得最優(yōu)解的廣度優(yōu)先搜索算法。由于給定了起始和終止?fàn)顟B(tài)，所以我們可以采用雙向的廣搜來進(jìn)一步壓縮解空間，則其中每個(gè)單向搜索的解空間為總解空間大小為，使效率提高了倍。

在具體實(shí)現(xiàn)上，我們利用多核CPU的優(yōu)勢，使用雙線程來實(shí)現(xiàn)雙向并行搜索，以提高搜索效率。

4.1 問題建模與OBDD表示

顯然的，上述棋盤的每一種狀態(tài)都可以被描述一個(gè)變量x_i（i為整數(shù)）。存在一個(gè)從{0，1}ⁿ到{0，1}¹的布爾表達(dá)式f（x₁，x₂，x₃，…，x_n），其中每一個(gè)變量代表棋盤的一個(gè)狀態(tài)集。當(dāng)經(jīng)歷合適的狀態(tài)集，即33個(gè)變量被的激活時(shí)，f的值為真，而這33個(gè)變量對應(yīng)的狀態(tài)集中包含著我們要找的路徑。

根據(jù)描述，我們可以對該式中的變量逐次進(jìn)行香農(nóng)展開（Shannon's expansion），并將其展開過程用如下圖形的形式表示：根節(jié)點(diǎn)表示布爾函數(shù)f（x₁，x₂，x₃，…，x₃₃）自身，從根節(jié)點(diǎn)引出兩個(gè)分枝，分別表示經(jīng)過某個(gè)變量x_i的第一次香農(nóng)展開后所得到的輸入模式（x₁，…，x_i-₁，0，x_i+1，…，33）和（x₁，…，x_i-1，1，x_{i+1，…，33}）下的布爾函數(shù)

布爾函數(shù)可進(jìn)一步進(jìn)行香農(nóng)展開，并將它們和各自所展開得到的分量和分量連接;類似地，將每次展開所得到的布爾函數(shù)再進(jìn)行進(jìn)一步的香農(nóng)展開，必然得到0-分量和1-分量中的一個(gè)或者兩個(gè)同時(shí)取常值0或1。基于此，可得到題目中狀態(tài)的二叉決策圖（BDD）表示。結(jié)合題目來談，這里0和1，表示兩個(gè)狀態(tài)集之間的關(guān)系是可達(dá)還是不可達(dá)的。

也就是說尋找路徑問題可以歸結(jié)為尋找布爾表達(dá)式問題，布爾表達(dá)式又可以對應(yīng)一個(gè)或多個(gè)二叉決策圖，這樣，問題就轉(zhuǎn)變成了二叉決策圖的構(gòu)建問題。由于所求二叉決策圖的每一個(gè)節(jié)點(diǎn)對應(yīng)于棋盤的狀態(tài)集，而棋盤每一步棋子的消耗造成了非同步狀態(tài)集之間的差異，從而使得這樣構(gòu)建的二叉決策圖是絕對有序的，即天然是有序二叉決策圖（OBDD）。

4.2 狀態(tài)保存

廣度優(yōu)先搜索相比于深度優(yōu)先搜索，時(shí)間消耗更少，空間消耗更大，是以空間換取時(shí)間的算法。算法通過保存當(dāng)前搜索樹高度的所有狀態(tài)，并利用這些狀態(tài)直接推出下一層的所有狀態(tài)，重復(fù)這一步驟直到找到解。所以狀態(tài)的保存方式是解決問題在時(shí)間和空間上消耗多少的關(guān)鍵。本文采用OBDD這一數(shù)據(jù)結(jié)構(gòu)來保存這些狀態(tài)。如上文所述，OBDD是一種通過二進(jìn)制保存的數(shù)據(jù)結(jié)構(gòu)，比起傳統(tǒng)保存方法可以節(jié)省大量空間和I/O時(shí)間。本文通過把BDD抽象成一個(gè)二維的布爾數(shù)組，把有棋子抽象為1，無棋子抽象為0，來保存整個(gè)棋盤狀態(tài)。傳統(tǒng)的廣度優(yōu)先搜索利用隊(duì)列來保存當(dāng)前層的所有狀態(tài)，而本文直接利用OBDD數(shù)據(jù)結(jié)構(gòu)的樹形特點(diǎn)，直接將狀態(tài)保存在OBDD中。

4.3 判重

廣度優(yōu)先搜索的判重一般通過一個(gè)標(biāo)記數(shù)組來實(shí)現(xiàn)，必須用過哈希或者全排列的方式才能將狀態(tài)與數(shù)組下標(biāo)——對應(yīng)，這樣不僅浪費(fèi)了大量時(shí)間來實(shí)現(xiàn)狀態(tài)與下標(biāo)間的轉(zhuǎn)換，還需要想出一個(gè)合理的方式來安排下標(biāo)，而且對于狀態(tài)數(shù)太過龐大的問題，程序還會因?yàn)閿?shù)組過大而過不了編譯。本文使用的OBDD數(shù)據(jù)結(jié)構(gòu)完美地解決了這個(gè)問題，無論是什么狀態(tài)，只要能用BDD來表示，就能在OBDD上直接判重。

4.4 基于OBDD的快速路徑搜索算法

一般的路徑搜索問題可以描述為：考慮一個(gè)已知的有起點(diǎn)和終點(diǎn)的超大規(guī)模有向圖，其頂點(diǎn)代表當(dāng)前系統(tǒng)的一個(gè)狀態(tài)，邊代表可以從某一狀態(tài)通過單步操作到達(dá)另一狀。求這樣一條路徑，從起點(diǎn)出發(fā)，到終點(diǎn)結(jié)束。由于本文討論的問題模型中所有單步操作代價(jià)相同，故有向圖的邊的權(quán)重都為1。

對于上述問題，建立一個(gè)OBDD（有序二元決策圖）。該OBDD的根就是起始狀態(tài)，葉節(jié)點(diǎn)是1代表到達(dá)了終點(diǎn)狀態(tài)，0代表到達(dá)了非所需終點(diǎn)狀態(tài)的最終狀態(tài)。一個(gè)簡單的OBDD模型如圖5所示。

x₁代表起始狀態(tài)，通過不同路徑（自上往下），經(jīng)過或不經(jīng)過中間狀態(tài)x₂和x₃到達(dá)最終狀態(tài)。到達(dá)1表示到達(dá)了所需的最終狀態(tài)，即終點(diǎn)狀態(tài)，到達(dá)0表示到達(dá)了非所需的最終狀態(tài)。而問題所求既是一條從x₁到1的路徑。使用OBDD的求解步驟即是建立OBDD樹的過程，從問題的起始狀態(tài)出發(fā)，枚舉當(dāng)前OBDD中所有狀態(tài)的子節(jié)點(diǎn)，放入OBDD中，并刪除它們的父節(jié)點(diǎn)，如此循環(huán)直到達(dá)到目標(biāo)狀態(tài)。對于上述Solitare問題，具體求解步驟如下：

Step 1：枚舉所有可能的操作{x，y，z}，表示位于x的棋子跳過y的棋子，進(jìn)入z空位;

Step 2：通過所有可能的操作{x，y，z}生成棋盤的轉(zhuǎn)移矩陣T;

Step 3：將棋盤起始狀態(tài)S加入到OBDD1中，目標(biāo)狀態(tài)D加入到OBDD2中;

Step 4：取當(dāng)前OBDD1中的所有狀態(tài)，通過T得到所有子狀態(tài)并放入OBDD1_temp中，取當(dāng)前OBDD2中所有狀態(tài)，通過T得到所有父狀態(tài)并放入OBDD2_temp中;

Step 5：令OBDD=OBDD1_temp，OBDD2=OBDD2_temp;

Step 6：若OBDD1∩OBDD2≠，則說明已找到路徑，否則回到Step 4。

4.5 結(jié)果與分析

對于上述問題，在所有程序用C語言編程，在ubuntu操作系統(tǒng)環(huán)境下采用gcc編譯，實(shí)驗(yàn)在CPU英特爾）Intel（R）Core（TM）i5-5200UCPU@2.20GHz（4CPUs），8192MB RAM微機(jī)上進(jìn)行的測試環(huán)境下，輸出結(jié)果如表1所示。

B-size：問題的規(guī)模，以N-m表示

Time：得出解所耗費(fèi)的時(shí)間

Nodes：搜索過程中耗費(fèi)的節(jié)點(diǎn)數(shù)

States：經(jīng)歷的狀態(tài)數(shù)

可以看出，在狀態(tài)數(shù)方面，基于OBDD的單向搜索算法（以下簡稱單向搜索算法）對暴力搜索的優(yōu)勢是巨大的，僅僅在7-3，僅僅只有13個(gè)棋格的小規(guī)模下，暴搜的狀態(tài)數(shù)約是基于OBDD的算法的10^-5倍，到了7-2，33個(gè)棋格下，這個(gè)數(shù)字則變成 10¹²，隨著規(guī)模增大，這個(gè)應(yīng)該還會變得更大。

而基于OBDD的雙向并行搜索算法（以下簡稱雙向并行算法），相較于單向搜索算法在小規(guī)模時(shí)的優(yōu)勢并不明顯，對狀態(tài)數(shù)和節(jié)點(diǎn)數(shù)的改進(jìn)很小。而在稍大些的規(guī)模的實(shí)驗(yàn)中，都取得了令人滿意的效果，狀態(tài)數(shù)和時(shí)間耗費(fèi)降到了原來的十分之一，節(jié)點(diǎn)數(shù)降為原來的二分之一。充分說明了，相對于單向搜索算法，雙向并行算法在空間與時(shí)間上的耗費(fèi)都是很小的。

5 總結(jié)

布爾函數(shù)的可滿足性和等價(jià)性等問題的NP完備性所導(dǎo)致的狀態(tài)組合爆炸問題嚴(yán)重地限制了大規(guī)模、甚至工業(yè)小規(guī)模問題的解決。然而在實(shí)際問題的處理中，對布爾函數(shù)采取恰當(dāng)?shù)拿枋霾⒔⑾鄳?yīng)描述下的操作算法，可以有效地減緩甚至避免問題處理過程中的狀態(tài)組合復(fù)雜性。而本文就是利用了OBDD來建立布爾函數(shù)模型并求解實(shí)際問題，結(jié)果在效率上較傳統(tǒng)方法有很大提升。

參考文獻(xiàn)

[1]Alan Bundy，Lincoln WaIleR.Bread th-First Search.Springer BerlinHeidelberg，1984.

[2]古天龍.一類新型抽象數(shù)據(jù)類型：有序二又決策圖[J].桂林電子科技大學(xué)學(xué)報(bào)，2010，30（05）：374-388.

[3]Akers.Binary Decision Diagrams[J].IEEE Transactions on Computers，2006，C-27（06）：509-516.

[4]V Kumar，A Grama，A Gupta，G Karypis.Introduction to parallel computing：design and analysis of algorithms.China Machine Press，2003，22（02）：N12.

[5]古天龍，徐周波.有序二又決策圖及應(yīng)用[J].科學(xué)出版社，2009.