王 宇，劉燕麗，2*，陳?ài)课?/p>

（1.武漢科技大學(xué)理學(xué)院，武漢 430081；2.冶金工業(yè)過(guò)程系統(tǒng)科學(xué)湖北省重點(diǎn)實(shí)驗(yàn)室（武漢科技大學(xué)），武漢 430081）

（?通信作者電子郵箱yanlil2008@163.com）

0 引言

圖被廣泛應(yīng)用于描述事物的結(jié)構(gòu)或事物之間的復(fù)雜關(guān)系，如互聯(lián)網(wǎng)、社交網(wǎng)絡(luò)、蛋白質(zhì)交互網(wǎng)絡(luò)、化學(xué)分子結(jié)構(gòu)、電力網(wǎng)、公路網(wǎng)、圖像處理中的屬性圖等［1］。給定模式圖和目標(biāo)圖，子圖同構(gòu)問(wèn)題是判斷在目標(biāo)圖中是否存在與模式圖完全同構(gòu)的子圖。最大公共子圖（Maximum Common induced Subgraph，MCS）問(wèn)題是子圖同構(gòu)問(wèn)題的優(yōu)化形式，即在模式圖和目標(biāo)圖中找到滿(mǎn)足同構(gòu)條件的最大子圖。

圖匹配問(wèn)題廣泛應(yīng)用于圖像處理［2-3］、生物化學(xué)［4］、信息檢索［5］、模式識(shí)別［6］、社交網(wǎng)絡(luò)［7］等領(lǐng)域。圖匹配問(wèn)題可以識(shí)別數(shù)據(jù)集成中元數(shù)據(jù)或模型的對(duì)應(yīng)關(guān)系。在生物學(xué)和生物化學(xué)領(lǐng)域，基因序列中每個(gè)基因可以表示為圖的頂點(diǎn)，若染色體上兩個(gè)基因相鄰，則圖中對(duì)應(yīng)的頂點(diǎn)之間存在邊。利用圖匹配可以發(fā)現(xiàn)基因組中是否含有相同的基因。在模式識(shí)別中，圖匹配可以提取多個(gè)圖像中相似的對(duì)象。在Facebook等社交網(wǎng)絡(luò)中，頂點(diǎn)表示每個(gè)用戶(hù)，有向邊表示用戶(hù)之間的好友關(guān)系。利用已有的社交關(guān)系，為用戶(hù)推薦好友，也是圖匹配問(wèn)題的應(yīng)用之一。

文獻(xiàn)［8］提出了基于約束規(guī)劃（Constraint Programming，CP）模型的樹(shù)搜索算法。對(duì)于給定的模式圖P和目標(biāo)圖T，每次選擇一個(gè)〈v，w〉（v∈VP，w∈VT）頂點(diǎn)匹配對(duì)作為空間搜索樹(shù)的分支點(diǎn)；界函數(shù)計(jì)算子樹(shù)含有的頂點(diǎn)的最大待匹配對(duì)個(gè)數(shù)，作為剪枝操作的上界。提高CP 類(lèi)算法效率的關(guān)鍵工作是分支順序和定界函數(shù)的設(shè)計(jì)。文獻(xiàn)［9］提出了尋找給定子圖大小的帶有回溯的樹(shù)搜索算法-。文獻(xiàn)［10］提出了帶有回溯的樹(shù)搜索和頂點(diǎn)覆蓋相結(jié)合的技術(shù)。文獻(xiàn)［11］提出了一種基于標(biāo)簽類(lèi)的快速劃分算法McSplit（Maximum common induced subgraph Split），利用標(biāo)簽類(lèi)的劃分，快速實(shí)現(xiàn)了全局邊約束條件。相較傳統(tǒng)的存儲(chǔ)模式圖中每個(gè)頂點(diǎn)的值域以及值域過(guò)濾的方法，McSplit 算法大幅度降低了內(nèi)存消耗，將MCS 算法的求解速度提高了若干數(shù)量級(jí)。

啟發(fā)式策略是提高基于CP 模型的MCS 算法效率的關(guān)鍵步驟。本文研究圍繞頂點(diǎn)沖突關(guān)系，解決了確定沖突頂點(diǎn)范圍、量化頂點(diǎn)沖突關(guān)系等關(guān)鍵問(wèn)題，設(shè)計(jì)了基于頂點(diǎn)沖突的頂點(diǎn)匹配順序。實(shí)驗(yàn)結(jié)果表明，基于頂點(diǎn)沖突的新匹配順序可以更有效地解決大規(guī)模稀疏圖的MCS問(wèn)題。

1 最大公共子圖問(wèn)題

本章介紹最大公共子圖問(wèn)題相關(guān)的術(shù)語(yǔ)和基于分支定界的約束模型算法框架［12］。

1.1 相關(guān)術(shù)語(yǔ)

定義1圖G是由頂點(diǎn)的有窮非空集合和邊集合組成的，記為G=〈V，E〉。V是圖G的頂點(diǎn)集合，E是圖G的邊集合，（a，b）∈E，（a，b）表示頂點(diǎn)a和b之間存在連接邊。|V|表示頂點(diǎn)數(shù)，|E|表示邊數(shù)。

定義2給定模式圖Gp=〈Vp，Ep〉和目標(biāo)圖Gt=〈Vt，Et〉，頂點(diǎn)匹配對(duì)〈v，w〉是頂點(diǎn)的笛卡兒積，v∈Vp，w∈Vt，且v和w具有相同的標(biāo)簽屬性。

定義3給定模式圖Gp=〈Vp，Ep〉和目標(biāo)圖Gt=〈Vt，Et〉，最大公共子圖問(wèn)題是找到含有最多頂點(diǎn)匹配對(duì)的子圖Gs=〈Vs，Es〉，即任意匹配對(duì)〈v，w〉和〈k，j〉∈Vs，滿(mǎn)足（〈v，w〉，〈k，j〉）∈Es，當(dāng)且僅當(dāng)（v，k）∈Ep，（w，j）∈Et。該約束條件也被稱(chēng)之為邊約束。

定義4頂點(diǎn)v的鄰域是與頂點(diǎn)v有邊相連的頂點(diǎn)的集合，記為N（v）。|N（v）|表示頂點(diǎn)v的鄰居個(gè)數(shù)。

定義5頂點(diǎn)域是由模式圖和目標(biāo)圖中具有相同標(biāo)簽屬性的頂點(diǎn)構(gòu)成的集合，記為domain。由若干頂點(diǎn)域構(gòu)成的集合稱(chēng)之為域集，記為Domains。

1.2 基于分支定界的MCS算法

基于分支定界的MCS 算法是帶回溯的深度遍歷搜索樹(shù)空間的算法。算法1描述了MCS算法流程［11］。

算法1 MCS（Gp，Gt，Domains）。

輸入 模式圖Gp、目標(biāo)圖Gt和初始域集Domains。

輸出Gp和Gt的最大公共子圖。

算法1 的初始域集Domains是根據(jù)頂點(diǎn)的標(biāo)簽屬性劃分的頂點(diǎn)域集合。若輸入的Gp和Gt是無(wú)向非標(biāo)定圖，那么Domains只有1個(gè)頂點(diǎn)域，即包含所有的模式圖頂點(diǎn)和目標(biāo)圖頂點(diǎn)。若Gp和Gt是標(biāo)簽圖，那么根據(jù)不同的標(biāo)簽屬性，頂點(diǎn)被劃分到不同的頂點(diǎn)域中。curSolution記錄搜索過(guò)程中的當(dāng)前解，初始為空；maxSolution是目前為止得到的最優(yōu)解，初始為空；bound（）返回在搜索樹(shù)當(dāng)前分支點(diǎn)，所有頂點(diǎn)域可提供的最大匹配數(shù)之和，而每個(gè)頂點(diǎn)域的最大匹配數(shù)是該域中模式圖的頂點(diǎn)數(shù)和目標(biāo)圖的頂點(diǎn)數(shù)兩者之中的較小值。ChooseDomain（）依據(jù)啟發(fā)式策略，從當(dāng)前域集Domains中選出某個(gè)頂點(diǎn)域domain；ChooseV（）則返回依據(jù)啟發(fā)式策略，從domain中選擇的模式圖頂點(diǎn)v。filterDomains（）將搜索樹(shù)當(dāng)前層的域集，依據(jù)與分支點(diǎn)的鄰接關(guān)系，劃分產(chǎn)生新的頂點(diǎn)域newDomains。

MCS 的求解過(guò)程是:首先根據(jù)模式圖Gp和目標(biāo)圖Gt的標(biāo)簽信息，建立初始域集Domains，如例1 中的D0。如果當(dāng)前解大于目前的最優(yōu)解，那么更新最優(yōu)解為當(dāng)前解（第1）～3）行）；否則，計(jì)算當(dāng)前分支層的上界（第4）行）。上界是從樹(shù)根到當(dāng)前分支點(diǎn)路徑上的匹配對(duì)數(shù)，與當(dāng)前域集的最大可匹配對(duì)之和。如果上界小于等于目前的最優(yōu)解，表明該路徑不能提供比目前的最優(yōu)解更好的解，程序進(jìn)入回溯，搜索樹(shù)剪枝（第5）～7）行）。

若不滿(mǎn)足剪枝條件，算法1 依據(jù)分支策略，從當(dāng)前域集中選擇某個(gè)頂點(diǎn)域domain，然后再選取模式圖中某個(gè)頂點(diǎn)v，與目標(biāo)圖中的可匹配頂點(diǎn)w逐一匹配，當(dāng)前解增加匹配對(duì)〈v，w〉，滿(mǎn)足邊約束條件下，對(duì)剩余的頂點(diǎn)域進(jìn)行劃分，并遞歸調(diào)用MCS 函數(shù)搜索新分支（第11）～13）行）。遍歷完v的所有匹配可能性后，移除v（第16）行）；若當(dāng)前頂點(diǎn)域不再包含任何模式圖頂點(diǎn)，表明該域的所有匹配可能性已被遍歷，從域集中移除當(dāng)前頂點(diǎn)域（第17）～19）行）；然后同樣方式遍歷其余的頂點(diǎn)域（第20）～22）行）。當(dāng)算法遍歷完搜索空間，全局變量maxSolution記錄了最終的最優(yōu)解。

例1 說(shuō)明了在搜索過(guò)程中，bound（）的計(jì)算方法和filterDomains（）產(chǎn)生新域集的過(guò)程。輸入的模式圖和目標(biāo)圖均為無(wú)向圖。

例1 如圖1 所示，模式圖Gp的頂點(diǎn)集Vp=｛1，2，3，4，5｝，邊集Ep=｛（1，2）（1，3）（1，4）（2，3）（2，5）｝；目標(biāo)圖Gt的頂點(diǎn)集Vt=｛a，b，c，d，e，f｝，邊集Et=｛（a，b）（a，c）（a，e）（b，d）（b，e）（c，d）（c，f）｝。

圖1 頂點(diǎn)域的圖例Fig.1 Instance of vertex domain

因?yàn)槟Ｊ綀D和目標(biāo)圖是無(wú)向圖，頂點(diǎn)標(biāo)簽屬性相同，所以Gp的每個(gè)頂點(diǎn)均可與Gt的頂點(diǎn)匹配，初始域集只包含1 個(gè)頂點(diǎn)域D0=｛1，2，3，4，5，a，b，c，d，e，f｝。顯然，D0可提供的最多匹配對(duì)是5（bound函數(shù)的返回值）。依據(jù)頂點(diǎn)度的降序策略，首先選擇〈1，a〉作為搜索樹(shù)第一個(gè)分支點(diǎn)。根據(jù)邊約束，產(chǎn)生與分支點(diǎn)〈1，a〉相鄰的頂點(diǎn)域D11=｛2，3，4，b，c，e｝，不相鄰的頂點(diǎn)域D12=｛5，d，f｝，所以filterDomains返回的新域集是｛D11，D12｝，該域集的bound函數(shù)返回值是3+1=4。

2 匹配沖突的學(xué)習(xí)

絕大多數(shù)傳統(tǒng)的MCS 算法選擇圖的靜態(tài)屬性作為分支策略的依據(jù)，如頂點(diǎn)鄰接性、頂點(diǎn)度、頂點(diǎn)或邊的標(biāo)定值，而基于沖突學(xué)習(xí)的頂點(diǎn)匹配策略以強(qiáng)化學(xué)習(xí)的思想為核心，優(yōu)先選擇沖突高的頂點(diǎn)，以加速最優(yōu)解的計(jì)算。

2.1 強(qiáng)化學(xué)習(xí)

強(qiáng)化學(xué)習(xí)是智能體與環(huán)境交互，從環(huán)境中獲取學(xué)習(xí)的反饋信號(hào)；通過(guò)不斷的試錯(cuò)，獲得行為的強(qiáng)化信號(hào)，最終達(dá)到累計(jì)獎(jiǎng)勵(lì)最大化的目標(biāo)［13-15］。強(qiáng)化學(xué)習(xí)中的要素:智能體、動(dòng)作、環(huán)境、獎(jiǎng)勵(lì)和目標(biāo)。對(duì)于搜索樹(shù)空間，MCS 算法作為智能體，每次分支動(dòng)作是在不斷地試錯(cuò)，以達(dá)到快速找到最優(yōu)解的目標(biāo)。如何定義搜索中，分支動(dòng)作每次獲得的獎(jiǎng)勵(lì)？如何獲得累計(jì)獎(jiǎng)勵(lì)是需要解決的關(guān)鍵問(wèn)題。

2.2 匹配的沖突

一旦匹配對(duì)造成搜索分支提供的最大可匹配對(duì)減少，則稱(chēng)之為匹配沖突。匹配沖突代表了匹配動(dòng)作對(duì)搜索環(huán)境的影響。例1 中，域集Dold=｛D11，D12｝的最大可匹配對(duì)是4。選擇〈5，d〉作為第二個(gè)分支點(diǎn)，滿(mǎn)足邊約束條件，D11被劃分為D21=｛2，b，c｝和D22=｛3，4，e｝；對(duì)D12劃分，沒(méi)有滿(mǎn)足邊約束條件的新頂點(diǎn)域產(chǎn)生。最終，形成新域集Dnew=｛D21，D22｝，且最大匹配對(duì)是1+1=2。Dold-Dnew=4-(2+1)=1，最大可匹配對(duì)減少1，其中等式左邊的1 代表分支點(diǎn)。同樣方法分析，若選擇〈2，d〉作為第二個(gè)分支點(diǎn)，產(chǎn)生新域集｛｛3，e｝｛4，c｝｛5，d｝｝，4-(3+1)=0，最大可匹配對(duì)未減少。

匹配的沖突說(shuō)明分支頂點(diǎn)的匹配動(dòng)作對(duì)搜索子樹(shù)的大小具有不同的影響。生成的子樹(shù)越小，bound函數(shù)獲得質(zhì)量更好的上界，算法1 更快達(dá)到搜索的葉節(jié)點(diǎn)。同時(shí)，分析沖突的原因，搜索路徑上的每個(gè)分支點(diǎn)對(duì)當(dāng)前子圖的產(chǎn)生均有作用。從子圖的角度分析，搜索樹(shù)空間相當(dāng)于是待映射頂點(diǎn)構(gòu)成的子圖。圖2 是去除分支點(diǎn)〈1，a〉和〈5，d〉的子圖，直觀地顯示了如果優(yōu)先選擇對(duì)環(huán)境影響大的頂點(diǎn)進(jìn)行匹配，那么算法將獲得滿(mǎn)足邊約束條件、更加簡(jiǎn)單的子空間。

圖2 去除分支點(diǎn)的子圖Fig.2 Subgraphs excluding branching nodes

3 基于沖突學(xué)習(xí)的頂點(diǎn)匹配策略

本章基于對(duì)匹配沖突的學(xué)習(xí)，設(shè)計(jì)獎(jiǎng)勵(lì)函數(shù)，使得算法（智能體）獲得最大的獎(jiǎng)勵(lì)。

3.1 獎(jiǎng)勵(lì)函數(shù)

對(duì)于?v∈Vp(?w∈Vt)，本文定義頂點(diǎn)的獎(jiǎng)勵(lì)函數(shù)來(lái)計(jì)算頂點(diǎn)每次從環(huán)境中獲得的獎(jiǎng)勵(lì)，記為Rp(v)(Rt(w))。價(jià)值函數(shù)用于統(tǒng)計(jì)頂點(diǎn)累計(jì)獲得的獎(jiǎng)勵(lì)，記為Sp(v)(St(w))，且初始化為0。具體地，頂點(diǎn)的累計(jì)獎(jiǎng)勵(lì)包括兩個(gè)部分:

1）頂點(diǎn)v和w的獎(jiǎng)勵(lì)是在完成〈v，w〉匹配后，上界的減少:

其中:Dold表示選擇分支之前的域集；Dnew表示頂點(diǎn)v和w匹配后，Dold被劃分產(chǎn)生的新域集；bound（）返回分支前、后的最大可匹配數(shù)，1 表示匹配對(duì)〈v，w〉。獲得分支頂點(diǎn)的獎(jiǎng)勵(lì)后，更新頂點(diǎn)的累計(jì)獎(jiǎng)勵(lì)。

該獎(jiǎng)勵(lì)主要考慮分支動(dòng)作對(duì)搜索環(huán)境的影響，上界的差值體現(xiàn)了分支動(dòng)作造成的影響大小。

2）算法1執(zhí)行第1）～3）行時(shí)，找到了比之前部分搜索獲得的解更優(yōu)的公共子圖，而這是由于當(dāng)前搜索路徑上的匹配動(dòng)作造成的。因此，出現(xiàn)在搜索路徑上的頂點(diǎn)獲得獎(jiǎng)勵(lì)。對(duì)匹配對(duì)∈curSolution，v∈Vp，w∈Vt，更新頂點(diǎn)的累計(jì)獎(jiǎng)勵(lì):

從約束條件進(jìn)一步分析，依據(jù)與分支點(diǎn)〈1，a〉、〈5，d〉的相鄰性，圖2 中頂點(diǎn)2 與頂點(diǎn)c、b 可以匹配。對(duì)于待匹配的頂點(diǎn)，分支點(diǎn)限制了它們是否可以進(jìn)行匹配，因此，匹配沖突往往是由多個(gè)分支點(diǎn)累計(jì)造成的。

3.2 新分支策略

引入頂點(diǎn)沖突學(xué)習(xí)后，采用新分支策略的MCS 算法流程如圖3所示。

圖3 采用新分支策略的MCS算法流程Fig.3 FLow chart of MCS algorithm with new branching strategy

新的分支策略分為兩步:首先確定頂點(diǎn)域；其次從該頂點(diǎn)域中分別選擇一個(gè)模式圖頂點(diǎn)和目標(biāo)圖頂點(diǎn)進(jìn)行匹配。

設(shè)域集DS=｛D0，D1，…，Dm｝，分別計(jì)算頂點(diǎn)域Di（i=0，1，…，m）中包括的模式圖頂點(diǎn)數(shù)和目標(biāo)圖頂點(diǎn)數(shù)，i=0，1，…，m｝返回匹配操作復(fù)雜度較小的頂點(diǎn)域。max 函數(shù)返回每個(gè)頂點(diǎn)域的模式圖頂點(diǎn)數(shù)和目標(biāo)圖頂點(diǎn)數(shù)兩者中較大值，min函數(shù)則再取max函數(shù)值域中的最小值（算法1中的ChooseDomain函數(shù)）。該頂點(diǎn)域的選擇策略糅合了最小頂點(diǎn)域策略和鄰域策略的優(yōu)點(diǎn)，既考慮了頂點(diǎn)域中每個(gè)頂點(diǎn)需匹配的最大次數(shù)，又考慮了最小頂點(diǎn)域。

從被選中的頂點(diǎn)域中，分別選擇模式圖頂點(diǎn)v和目標(biāo)圖頂點(diǎn)w進(jìn)行匹配。具體地，優(yōu)先選擇分?jǐn)?shù)最高的頂點(diǎn)v（w），一旦出現(xiàn)平局，則選擇頂點(diǎn)度最大的作為分支點(diǎn)。

與傳統(tǒng)的分支策略不同，新分支策略不再依賴(lài)于圖的靜態(tài)屬性頂點(diǎn)度，而是對(duì)頂點(diǎn)在歷史搜索中產(chǎn)生的影響力進(jìn)行學(xué)習(xí)，指導(dǎo)后續(xù)的搜索方向。

4 新分支策略的評(píng)估

實(shí)驗(yàn)平臺(tái)是Intel Xeon CPUs E5-2680V4@2.40 GHz，內(nèi)存4 GB，Linux 系統(tǒng)（Ubuntu 14.04）。每個(gè)算例的計(jì)算限制時(shí)間是1 800 s。

4.1 對(duì)比算法

實(shí)驗(yàn)對(duì)比選擇了3種算法:

1）McSplit 算法［11］:McCreesh 等［11］于2017 年提出的求解最大公共子圖算法，采用了緊湊鄰域方法存儲(chǔ)每個(gè)模式圖頂點(diǎn)v的值域，并提出了基于劃分產(chǎn)生新的頂點(diǎn)域方法。該算法是目前處于先進(jìn)水平的MCS算法。

2）McSplitSBS（McSplit Solution-Biased Search）算法［16］:是McSplit的改進(jìn)版，采用偏好值順序和記錄非優(yōu)策略。

3）McSplitRLR（McSplit Reinforcement Learning and Routing）算法:本文在McSplit的基礎(chǔ)上，采用了基于頂點(diǎn)沖突學(xué)習(xí)的新分支策略。

4.2 算例集

算例集包含21 543個(gè)算例，來(lái)自生物化學(xué)、圖像、地勢(shì)、無(wú)線(xiàn)網(wǎng)格網(wǎng)絡(luò)等7 種工業(yè)問(wèn)題（算例集下載地址http://liris.cnrs.fr/csolnon/SIP.html）。依據(jù)算例是否為有向圖，劃分為以下兩個(gè)子集:

1）生物化學(xué)（簡(jiǎn)記為Bio）:來(lái)自biomodels.net，有136個(gè)有向、無(wú)標(biāo)簽圖，是描述生物化學(xué)反應(yīng)的網(wǎng)絡(luò)圖。頂點(diǎn)數(shù)的范圍是9～386。

2）大規(guī)模子圖同構(gòu)和最大公共子圖算例:包括由隨機(jī)模型生成或由實(shí)際問(wèn)題轉(zhuǎn)換而來(lái)的稀疏圖。模式圖的頂點(diǎn)數(shù)范圍是4～900，目標(biāo)圖的頂點(diǎn)數(shù)范圍是10～6 671，共計(jì)12 227 個(gè)算例。依據(jù)實(shí)際問(wèn)題的來(lái)源不同，含有6 278 個(gè)Images 算例，1 225 個(gè)LV 算例，3 430 個(gè)largerLV 算例，24 個(gè)PR15 算例，100個(gè)Scalefree算例，1 170個(gè)Si算例。

4.3 算法對(duì)比

表1 給出了3 個(gè)算法求解實(shí)際問(wèn)題或隨機(jī)圖的求解個(gè)數(shù)和平均求解時(shí)間對(duì)比。第3、5、7 列的數(shù)據(jù)分別是在限定時(shí)間1 800 s 內(nèi)對(duì)比算法求出最優(yōu)解的算例數(shù)，第4、6、8 列則是平均求解時(shí)間（單位為s）。平時(shí)求解時(shí)間=所有被解決算例的CPU時(shí)間之和/被解決的算例數(shù)。

如表1所示，相較于McSplit、McSplitSBS算法，McSplitrRLR在相同機(jī)器和求解限制時(shí)間條件下，多解決了109、33 個(gè)算例。對(duì)于不同類(lèi)型的算例，對(duì)比算法的平均求解時(shí)間差異很小，這表明頂點(diǎn)獎(jiǎng)勵(lì)的計(jì)算代價(jià)較小。McSplitRLR 和McSplit僅分支策略不同，實(shí)驗(yàn)驗(yàn)證了新分支策略的有效性。

表1 不同算法解決算例數(shù)和平均求解時(shí)間的對(duì)比Tab.1 Comparison of number of instances solved and average solving time of different algorithms

表1 中有7 396 個(gè)簡(jiǎn)單算例均被McSplitrRLR、McSplit 和McSplitSBS 三個(gè)算法在10 s 之內(nèi)解決，平均求解時(shí)間依次是0.48 s、0.45 s、0.57 s。這表明三種算法在簡(jiǎn)單算例上求解效率是同一數(shù)量級(jí)，沖突學(xué)習(xí)并未降低求解簡(jiǎn)單算例的效率。同時(shí)，圖4 給出了三個(gè)對(duì)比算法在困難算例求解上的效率，McSplitRLR 比McSplit、McSplitSBS 多解決了5.6%、1.6%的困難算例（算法解決的算例個(gè)數(shù)-7396），驗(yàn)證了沖突學(xué)習(xí)策略有效地改進(jìn)了困難算例的求解。

圖4 三個(gè)算法解決的困難算例數(shù)的對(duì)比Fig.4 Number comparison of hard instances solved by three algorithms

4.4 結(jié)果分析

影響分支定界算法的關(guān)鍵因素是上界和下界的確定。算法1 中第5）行表示當(dāng)上界小等于下界（maxSolution）時(shí)，進(jìn)行剪枝。如果算法更快地找到最優(yōu)解則獲得高質(zhì)量的上界UB，在回溯過(guò)程中，更有利于滿(mǎn)足剪枝條件，提高剪枝率。

圖5 顯示了對(duì)于求解時(shí)間大于10 s 的困難算例，在相同的時(shí)間內(nèi)，McSplitRLR 算法相較McSplit 和McSplitSBS 找到了更多算例的最優(yōu)解。

圖5 三種算法第一次找到最優(yōu)解的算例數(shù)對(duì)比Fig.5 Number comparison of instances of optimal solution first found by three algorithms

進(jìn)一步地分析，圖6顯示頂點(diǎn)的多樣性選擇有利于算法1更快地找到最優(yōu)解，并進(jìn)行有效的剪枝。圖6 中每個(gè)實(shí)心點(diǎn)對(duì)應(yīng)Images 算例集的一個(gè)算例，該算例均被McSplit 和McSplitRLR 算法在時(shí)間t（10 s≤t≤1 800 s）內(nèi)解決。實(shí)心點(diǎn)的坐標(biāo)x（y）表示在McSplit（McSplitRLR）算法中頂點(diǎn)被選作分支次數(shù)的標(biāo)準(zhǔn)差，即:

圖6 模式圖頂點(diǎn)被選作分支點(diǎn)的次數(shù)的標(biāo)準(zhǔn)差對(duì)比Fig.6 Comparison of standard deviation of number of vertices in pattern graph selected as branch nodes

其中:n是在時(shí)間t內(nèi)被McSplit 和McSplitRLR 找到最優(yōu)解的算例數(shù)；bvi表示模式圖的頂點(diǎn)vi作為分支點(diǎn)的次數(shù)是頂點(diǎn)作為分支點(diǎn)的平均次數(shù)

McSplit和McSplitRLR 算法僅分支策略不同，前者每次選擇度最大的頂點(diǎn)，而后者每次優(yōu)先選擇累計(jì)獎(jiǎng)勵(lì)最大的頂點(diǎn)。在圖6中，更多的點(diǎn)出現(xiàn)在副對(duì)角線(xiàn)的下方，表明McSplitRLR算法的頂點(diǎn)標(biāo)準(zhǔn)差較小，即在搜索過(guò)程中，更多的頂點(diǎn)參與了分支過(guò)程，換句話(huà)說(shuō)，基于頂點(diǎn)沖突學(xué)習(xí)的分支策略給度小的頂點(diǎn)更多的機(jī)會(huì)。

5 結(jié)語(yǔ)

最大公共子圖問(wèn)題是解決眾多工業(yè)問(wèn)題的基礎(chǔ)子問(wèn)題，也是經(jīng)典的NP-難度問(wèn)題之一。不同頂點(diǎn)匹配動(dòng)作對(duì)于搜索空間有不同的影響程度。本文所提出的基于頂點(diǎn)沖突學(xué)習(xí)的新分支策略解決了如何衡量匹配動(dòng)作影響力、計(jì)算動(dòng)作獎(jiǎng)勵(lì)以及使用動(dòng)作獎(jiǎng)勵(lì)等問(wèn)題。相較于傳統(tǒng)的、基于圖的靜態(tài)屬性的分支策略，新分支策略提供了一種新的學(xué)習(xí)方式和改進(jìn)基于分支定界MCS 算法效率的途徑。學(xué)習(xí)歷史搜索經(jīng)驗(yàn)和開(kāi)辟新搜索空間兩者之間的關(guān)系本質(zhì)上是探索和利用的平衡。后續(xù)將對(duì)搜索中出現(xiàn)的局部最優(yōu)解做進(jìn)一步的研究。