亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        基于符號OBDD的子圖同構(gòu)約束求解算法

        2019-12-27 08:59:14劉桂珍徐周波
        關(guān)鍵詞:實驗

        劉桂珍, 徐周波

        (桂林電子科技大學(xué) 計算機與信息安全學(xué)院,廣西 桂林 541004)

        作為一種結(jié)構(gòu)化數(shù)據(jù),圖數(shù)據(jù)所含語義信息豐富,實際生活中大部分數(shù)據(jù)都能夠轉(zhuǎn)化為圖進行描述。圖匹配技術(shù)是實現(xiàn)圖數(shù)據(jù)高效處理的重要方法之一,其目標是確定模式圖和目標圖中頂點和邊之間的對應(yīng)關(guān)系,從而判斷2個圖之間的相似度。圖匹配問題可通過定義子圖同構(gòu)、圖同構(gòu)、最大公共子圖等方式進行求解。其中,子圖同構(gòu)要求2個圖的頂點和邊之間嚴格遵循一一對應(yīng)關(guān)系,匹配結(jié)果與模式圖的結(jié)構(gòu)和屬性完全一致[1]。子圖同構(gòu)主要應(yīng)用于生物化學(xué)[2]、社交網(wǎng)絡(luò)[3]等對匹配要求較高的領(lǐng)域。目前,已存在Ullman算法[4]、VF2算法[5]等大量經(jīng)典的子圖同構(gòu)求解算法,但隨著圖數(shù)據(jù)規(guī)模的不斷增大,這些算法的復(fù)雜度呈指數(shù)級增長,無法有效完成問題的求解。

        約束滿足問題(constraint satisfaction problem,簡稱CSP)作為人工智能領(lǐng)域一種通用的求解范例,在裝配規(guī)劃、調(diào)度配置、圖匹配等領(lǐng)域有著廣泛的應(yīng)用[6]。研究人員已經(jīng)提出了眾多基于CSP的子圖同構(gòu)求解算法[7-9]。約束滿足問題的求解屬于NP-hard問題,因此,在對子圖同構(gòu)問題進行約束求解過程中,其計算復(fù)雜度較高。為此,引入有序二叉決策圖(ordered binary decision diagram,簡稱OBDD)概念及其相關(guān)的符號操作技術(shù)[10-11]。OBDD是布爾函數(shù)的一種等價形式的圖形表示,具有高緊湊性、易操作等特點,其所有的運算操作都以集合的方式進行處理,能夠在CSP求解過程中提供一種隱式表示和搜索的方法,同時能降低組合復(fù)雜度和狀態(tài)空間復(fù)雜度。文獻[12-13]采用基于OBDD的符號算法,通過實驗證明了符號技術(shù)能提高CSP的求解效率。Cortadella等[14]將符號OBDD運用于子圖同構(gòu)問題的求解中,并通過實驗證明了基于OBDD的方法明顯優(yōu)于傳統(tǒng)的Ullman算法,但該算法未充分利用圖中的結(jié)構(gòu)信息,導(dǎo)致求解過程中存在冗余搜索。針對上述問題,提出了基于符號OBDD的子圖同構(gòu)約束求解算法。

        1 相關(guān)基礎(chǔ)知識

        1.1 子圖同構(gòu)

        給定模式圖Gp=(Np,Ep)與目標圖Gt=(Nt,Et),其中Np和Nt分別為2個圖頂點的集合,Ep、Et分別為2個圖邊的集合,且模式圖與目標圖均為無向圖。

        定義1對于給定的模式圖Gp=(Np,Ep)有?u,u′∈Np,且(u,u′)∈Ep,目標圖Gt=(Nt,Et)有?v,v′∈Nt,(v,v′)∈Et,若存在一個單射函數(shù)f:Np→Nt,滿足?(u,u′)∈Ep??(v,v′)∈Et,且Gp?Gt,則Gp與Gt的子圖是同構(gòu)的。模式圖和目標圖示例如圖1所示。

        圖1 模式圖和目標圖示例

        1.2 約束滿足問題

        約束滿足問題(CSP)是人工智能和計算機科學(xué)領(lǐng)域中一項重要研究內(nèi)容[12]。一個約束滿足問題一般可定義為一個三元組P〈V,D,C〉,其中:

        1)V為由n個變量v1,v2,…,vn組成的有限變量集,即V={v1,v2,…,vn}。

        2)D為n個變量的值域集組成的集合,對于?vi∈V,有Di∈D,i=1,2,…,n,即D={D1,D2,…,Dn}。

        3)C為約束關(guān)系集合,C={c1,c2,…,cm},m=1,2,…;約束ci與變量集{vi1,vi2,…,vij}?X相關(guān),ci?D(xi1)×D(xi2)×… ×D(xij),則稱ci為定義在變量集{vi1,vi2,…,vij}?X上的j元約束(i=1,2,…,m,1≤j≤n);若C中所有約束均為一元或二元約束,則稱該CSP為二元CSP,本文只討論二元CSP的求解。

        CSP的求解目標就是在滿足約束集C的所有約束條件下,找到變量集V在值域D的一個解或所有解。

        1.3 有序二叉決策圖

        有序二叉決策圖(OBDD)是布爾函數(shù)的一種圖形、數(shù)學(xué)描述技術(shù)。

        定義2對于從{0,1}n到{0,1}的布爾函數(shù)f(x1,x2,…,xn)和給定變量序π,在表示布爾函數(shù)族#f(x1,x2,…,xn)的二叉決策圖(binary decision diagram,簡稱BDD)中,若任一有向路徑上的變量x1,x2,…,xn均以變量序π所規(guī)定的次序依次出現(xiàn),則稱該BDD為布爾函數(shù)f(x1,x2,…,xn)的有序二叉決策圖。

        OBDD是一個有向無環(huán)圖,節(jié)點包含根節(jié)點、終節(jié)點和內(nèi)部節(jié)點3種類型。其中,終節(jié)點有且僅有2個,用來表示布爾常量的0和1。每個非終節(jié)點都有2條輸出的分支分別連接到下一節(jié)點,即0分支和1分支。在OBDD任何一條路徑上,每個變量都依照變量序π所限定的次序出現(xiàn)一次。

        OBDD常用的符號操作包括Apply操作、ITE操作、置換操作和量化操作,能夠?qū)崿F(xiàn)許多布爾函數(shù)的運算,以解決由問題規(guī)模變大帶來的組合爆炸問題。

        1.4 弧一致性技術(shù)

        CSP求解方法主要分為基于回溯的搜索方法和基于推理的方法兩大類[13]?;谒阉鞯姆椒ㄖ饕曰诨厮莸姆椒榇?,回溯算法是一種完備的算法,能夠求出問題所有的解,但求解較大規(guī)模的CSP效率較低?;谕评淼姆椒ㄖ饕s束傳播算法、桶消元算法、樹分解算法等,能夠縮減問題的規(guī)模。其中,約束傳播算法是指在變量賦值過程中,將與變量相關(guān)的約束條件進行判斷,若存在一組賦值情況不滿足約束條件,則對該賦值進行刪除,并通過約束傳播的方式將該刪除操作擴展到整個搜索空間。

        約束傳播技術(shù)主要包括節(jié)點一致性技術(shù)、弧一致性(arc consistency,簡稱AC)技術(shù)[15-16]、路徑一致性技術(shù)等。其中,弧一致性技術(shù)是提高CSP求解效率的一種方法,能夠在求解過程中對不滿足約束條件的值進行過濾,其定義如下。

        定義3對于二元CSP約束圖中的任一約束C(xi,yi),若xi的值域能滿足xi上的一元約束的每一個值a,都能在xj的值域中找到一個值b滿足xj上的一元約束,且(a,b)滿足C(xi,yi),則稱它是弧一致的。

        根據(jù)定義3可知,當(dāng)且僅當(dāng)約束圖的每一條約束都滿足弧一致,則說明一個CSP是弧一致的。本算法采用弧一致性技術(shù)與回溯算法相結(jié)合方法對子圖同構(gòu)進行求解。在子圖同構(gòu)回溯求解過程中,對約束條件進行弧一致性檢查,將不滿足弧一致的分支不進行拓展,減少搜索次數(shù),達到降低狀態(tài)空間復(fù)雜度的目的。

        2 基于OBDD的子圖同構(gòu)約束求解算法

        2.1 子圖同構(gòu)問題的CSP模型

        給定模式圖Gp=(Np,Ep)與目標圖Gt=(Nt,Et),通過建立子圖同構(gòu)問題的CSP模型,將子圖同構(gòu)問題轉(zhuǎn)化為CSP進行求解。為此,定義一個CSP三元組P〈V,D,C〉,其中:

        1)V={v1,v2,…,vn},表示n個變量的有限集,分別對應(yīng)于模式圖的n個頂點{u1,u2,…,un}。

        2)D={D1,D2,…,Dn},表示變量X對應(yīng)的值域集,D中的值分別對應(yīng)于目標圖中的m個頂點{w1,w2,…,wm}。

        3)C={c1,c2,…,ci}為約束關(guān)系集。根據(jù)目標圖和模式圖的特征,建立以下約束條件:

        度約束c1。對于?u∈Np,頂點u的度數(shù)表示為d(u);對于?w∈Nt,頂點w的度數(shù)表示為d(w),則有

        d(u)

        (1)

        邊約束c2。設(shè)a(u)表示u的所有鄰接點,若有?u,u′∈Np∧?u′∈a(u),在Gt中滿足?w,w′∈Nt,且?w′∈a(w),則有

        ?(u,u′)∈Ep??(w,w′)∈Et。

        (2)

        相鄰約束c3。對于?u,u′∈Vp,?w,w′∈Vt,若u和u′是Gp中任意2個相鄰的頂點,即

        a(u)={u′|(u,u′)∈Ep},

        (3)

        設(shè)f(u)為變量vu在目標圖中對應(yīng)的取值,若滿足f(u)=w,則有f(u′)=w′,且w和w′滿足:

        a(w)={w′|(w,w′)∈Et}。

        (4)

        局部全不同約束c4。在滿足c3的條件下,對于模式圖中任意頂點u及其鄰接點u′、u″所對應(yīng)的變量在目標圖中的取值分別為f(u′)、f(u″),滿足:

        (5)

        全局全不同約束c5。令T()表示全局全不同約束(GAllDifferent),對于Gp中各個頂點所對應(yīng)的變量V={v1,v2,…,vn},在Gt所對應(yīng)的取值均不相同,約束表示為

        ?vi∈X?T({f(vi)|vi=f(vi)}),i=1,2,…,n。

        (6)

        CSP求解的目標是找到變量集V的完全賦值,使約束集C定義的約束條件均得到滿足。CSP的一個解表示找到一個子圖同構(gòu)的解,CSP的所有解表示在目標圖中找到所有與模式圖同構(gòu)的子圖。

        2.2 CSP模型的符號OBDD描述

        表1 變量的編碼與布爾表示形式

        根據(jù)OBDD的表示方法及相關(guān)操作,得到變量的OBDD表示形式。例如,在已知變量序π:x0

        圖2 變量v1的OBDD表示

        CSP模型的約束條件可描述為:

        1)度約束c1。通過OBDD符號操作計算圖中各個頂點的度。例如,設(shè)模式圖Gp對應(yīng)的OBDD表示為Gp(x,y),其頂點編碼為X=(x1,x2,…,xn),則采用OBDD操作技術(shù)中的存在量化操作?X(Gp(x,y))進行計算,結(jié)果為真的賦值的個數(shù),即任意頂點u∈Gp的度數(shù)。

        2)邊約束c2。約束圖中的邊表示頂點與頂點之間的二元關(guān)系,針對模式圖,設(shè)邊的兩端頂點分別用二進制向量X=(x1,x2,…,xn),Y=(y1,y2,…,yn)表示,得到圖Gp中的邊的編碼分別為:000001、000010、000011、001000、001010、001100、001101、010000、010001、010011、011000、011010、011100、011101、100001、100011、101001、101011。

        邊的起始節(jié)點用x表示,終節(jié)點用y表示,則節(jié)點之間的邊用x到y(tǒng)的二元關(guān)系表示。對于模式圖Gp,CSP模型中的約束條件c2可表示為一個布爾函數(shù):

        根據(jù)上述布爾函數(shù)Gp(x,y),在已知變量序π:x0

        圖3 Gp中邊約束c2的OBDD表示

        同理,對于目標圖中邊的兩端頂點分別用二進制向量V=(v1,v2,…,vn),W=(w1,w2,…,wn)表示。在已知變量序π的前提下,得到約束條件c2的OBDD表示如圖4所示。

        圖4 Gt中邊約束c2的OBDD表示

        3)相鄰約束c3。采用OBDD中的“合取操作”,可以依次得到各個頂點的所有相鄰頂點。例如,對于圖Gp中的頂點u1,其對應(yīng)的相鄰約束可表示為一個布爾函數(shù):

        根據(jù)該布爾函數(shù)可得到相應(yīng)的OBDD表示形式。根據(jù)上述方法,依次得到各個頂點的相鄰約束。

        2.3 符號求解算法

        基于OBDD的子圖同構(gòu)約束求解算法偽代碼為算法1,構(gòu)建OBDD的偽代碼為算法2。

        算法1OBDD-SI

        輸入:P(X,D,C)、變量集X、值域D、約束集C、變量匹配順序S;

        輸出:得到CSP的解,返回result。

        1 procedure Pre(P(X,D,C))

        2 if 滿足d(u)≤d(v) doD←D′;

        3 procedure solver

        4 CreateOBDD(P(X,D,C)); Pre(P(X,D,C));

        5 ifX=? then

        6 return result;

        7 else

        8xi=VarOrder(S);//根據(jù)變量序進行匹配

        9X=X-{vi};

        10 whileD(vi)≠? do;

        11a=ValueSelect(vi);//對變量vi進行賦值

        12D(vi)=D(vi)-{a};//從值域中刪除a

        13S(vi)=ITE(vi,0,1);//構(gòu)建OBDD

        14 APPLY(G,func(x),0);//根據(jù)OBDD中的Apply操作進行判斷

        15 if 滿足AC(X,D,C) then solver

        16 else return false

        17 return result。

        算法2CreateOBDD

        輸入:圖的頂點數(shù)n;

        輸出:G的OBDD表示。

        1 for (i=1 ton) do

        2 pos=v&(int)pow(2,i);//轉(zhuǎn)換成二進制

        3 if pos=0

        4p=ITE(x,0,1);//創(chuàng)建節(jié)點

        5 elsep=ITE(1,x,0);

        6 endif

        7E=ITE(func,p,0);//創(chuàng)建邊

        8G=ITE(E,1,0);//創(chuàng)建圖

        9 endfor

        10 returnG。

        算法2的主要求解步驟為:

        1) 構(gòu)建子圖同構(gòu)的CSP模型P〈X,D,C〉,基于已知的變量序π,對CSP模型進行OBDD描述。

        2) 預(yù)處理。通過OBDD符號操作計算圖中各頂點的度,根據(jù)約束條件c1,從值域中刪除不可能成為變量取值的值,從而完成對變量值域的初步縮減。

        3) 設(shè)變量集V={v1,v2,…,vn}為初始等待隊列Q,結(jié)合步驟2)的計算結(jié)果,得到頂點最大度數(shù)匹配順序π;當(dāng)?shù)却犃蠶不為空時,根據(jù)匹配順序π,從中取出變量x1,x2,…,xn依次進行賦值。

        4) 在變量賦值過程中執(zhí)行弧一致檢查。采用OBDD的Apply操作對當(dāng)前賦值是否滿足約束條件進行判斷,將約束條件進行“合取操作”。操作結(jié)果若非空集,則證明滿足約束條件,繼續(xù)從Q中取出下一個變量進行賦值;若OBDD符號操作得到的結(jié)果為空集,則算法產(chǎn)生回溯,對當(dāng)前變量重新賦值。重復(fù)執(zhí)行上述過程,直至變量集V中所有的變量都被賦值,且所有變量的賦值均滿足約束條件C。此時算法執(zhí)行結(jié)束,得到目標圖與模式圖所有同構(gòu)的子圖,完成對子圖同構(gòu)問題的求解。

        3 實驗分析

        基于符號OBDD的子圖同構(gòu)約束求解算法(OBDD-SI),結(jié)合了Colorado大學(xué)開發(fā)的CUDD軟件包,在VS2012環(huán)境下采用C語言編程實現(xiàn)。硬件環(huán)境為Inter Core i5-4690 CPU,主頻3.5 GHz,內(nèi)存8 GiB,操作系統(tǒng)為Windows 764 bit。實驗選取不同的公開數(shù)據(jù)集進行測試,數(shù)據(jù)集中每一對模式圖和目標圖為一個實例,將求解全部實例得到子圖同構(gòu)所有解的計算總時間作為算法性能的評價標準,并將本算法與LAD算法和VF2算法進行對比。

        1)實驗1采用M4Dr-n、Scalefree、AIDS三種數(shù)據(jù)集進行測試。其中,M4Dr-n表示正則網(wǎng)格圖,Scale-free表示無標度網(wǎng)絡(luò)圖,AIDS代表多種抗HIV活性分子的拓撲結(jié)構(gòu)圖。實驗1數(shù)據(jù)集信息如表2所示,模式圖和目標圖的頂點個數(shù)分別為np、nt,模式圖與目標圖的頂點個數(shù)比值為p。實驗1運行時間對比如表3所示,其中“-”表示在5 min內(nèi)無法求得全部解。從表3可看出,針對目標圖規(guī)模較小的AIDS數(shù)據(jù)集,VF2算法和LAD算法計算時間較少,優(yōu)于本算法,這是由于在本算法執(zhí)行過程中,構(gòu)建OBDD需要消耗一定的時間。然而,對于M4Dr-n和Scale-free數(shù)據(jù)集,本算法和LAD算法均優(yōu)于VF2算法,且本算法在目標圖規(guī)模較大的情況下優(yōu)于LAD算法。

        表2 實驗1數(shù)據(jù)集信息

        表3 實驗1運行時間對比

        2)本組實驗采用一類由圖像分割生成的中型規(guī)模的數(shù)據(jù)集Images-PR15進行測試,實驗2運行時間對比如表4所示。從表4可看出,傳統(tǒng)的VF2算法無法在規(guī)定時間內(nèi)求得子圖同構(gòu)的全部解,本算法優(yōu)于VF2算法和LAD算法。

        表4 實驗2運行時間對比

        3)本組實驗采用生物化學(xué)領(lǐng)域中規(guī)模較大的PDBSv1、PDBSv3、PPI三種數(shù)據(jù)集進行算法驗證。其中,PDBSV1、PDBSV2為稀疏圖,PPI為稠密圖,數(shù)據(jù)集中模式圖頂點數(shù)np=8。實驗3數(shù)據(jù)集信息如表5所示。本組實驗將本算法與LAD算法進行對比,實驗3運行時間對比如表6所示。從表6可看出,隨著目標圖規(guī)模的增大,本算法逐漸體現(xiàn)其良好的求解性能,尤其是稠密圖,本算法明顯優(yōu)于LAD算法。

        表5 實驗3數(shù)據(jù)集信息

        表6 實驗3運行時間對比

        由上述實驗結(jié)果可知,由于OBDD高效緊湊的特點以及符號操作可以實現(xiàn)狀態(tài)空間或變量組合的隱式表示和搜索,在對子圖同構(gòu)的CSP模型進行求解時,可以完成多條約束的并行處理,本算法能提高子圖同構(gòu)問題的求解效率,在目標圖規(guī)模相對較大的情況下,算法具有明顯優(yōu)勢。

        4 結(jié)束語

        隨著圖規(guī)模的增大,傳統(tǒng)的算法無法對子圖同構(gòu)進行求解,提出了基于OBDD的子圖同構(gòu)約束求解算法。通過分析模式圖和目標圖中頂點度數(shù)、邊、鄰域和結(jié)構(gòu)特征等信息,建立子圖同構(gòu)問題的CSP模型。采用OBDD對CSP模型進行符號化描述,并基于OBDD的操作技術(shù),結(jié)合回溯算法和弧一致性技術(shù),求得子圖同構(gòu)所有的解。實驗結(jié)果表明,在圖規(guī)模較大的情況下,本算法的求解效率優(yōu)于傳統(tǒng)的VF2算法和LAD算法。

        猜你喜歡
        實驗
        我做了一項小實驗
        記住“三個字”,寫好小實驗
        我做了一項小實驗
        我做了一項小實驗
        記一次有趣的實驗
        有趣的實驗
        小主人報(2022年4期)2022-08-09 08:52:06
        微型實驗里看“燃燒”
        做個怪怪長實驗
        NO與NO2相互轉(zhuǎn)化實驗的改進
        實踐十號上的19項實驗
        太空探索(2016年5期)2016-07-12 15:17:55
        国产精品免费看久久久8| 日产国产精品亚洲高清| 中国人在线观看免费的视频播放| 成人免费xxxxx在线观看| 国产精品女老熟女一区二区久久夜| 粉嫩小泬无遮挡久久久久久| 国产精品无码av天天爽| 日本韩国一区二区三区| 日韩熟女精品一区二区三区视频| 免费人成视频网站网址| 色偷偷噜噜噜亚洲男人| 成熟丰满熟妇高潮xxxxx| 亚洲欧洲综合有码无码| 日本免费播放一区二区| 内射夜晚在线观看| 日本老熟欧美老熟妇| 麻豆国产成人AV网| 亚洲成人精品在线一区二区| 亚洲综合图色40p| 中文字幕日本特黄aa毛片| 欧美自拍区| 亚洲素人日韩av中文字幕| 在线观看免费日韩精品| 色老板精品视频在线观看| 亚洲精品亚洲人成在线下载| 免费黄网站一区二区三区| 国产成人午夜福利在线观看| 亚洲毛片αv无线播放一区 | 好男人社区影院www| 亚洲肥老熟妇四十五十路在线| 国产不卡一区在线视频| 男女18视频免费网站| 人妻夜夜爽天天爽一区| 国产无码十八禁| 中文字幕午夜精品一区二区三区| 久久天天躁狠狠躁夜夜不卡| 久久艹影院| 大红酸枝极品老料颜色| 精品国产三级a∨在线欧美| 欧美日韩国产码高清综合人成| 综合无码一区二区三区四区五区|