侯愛民 郝志峰 陳小莉 沈丹華

(1.華南理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,廣東廣州 510006;2.廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院,廣東廣州 510090;3.東莞理工學(xué)院計(jì)算機(jī)學(xué)院,廣東東莞 523808)

無(wú)向哈密頓圈的判定問題是一個(gè) NP完全問題.到目前為止,任何一個(gè) NP完全問題都還沒有找到一個(gè)多項(xiàng)式時(shí)間復(fù)雜度的判定算法.因此,文中試圖尋找效率更佳的近似算法,用于判定哈密頓圈問題.

在經(jīng)典的無(wú)向哈密頓圈的判定算法中,回溯算法存在路徑選擇的全排列組合[1],其最壞時(shí)間復(fù)雜度為指數(shù)階.路徑集算法使用剪枝技術(shù),進(jìn)行不帶回溯操作的深度優(yōu)先搜索[2].剪枝技術(shù)能否保證算法收斂,有待于進(jìn)一步證明.通路矩陣算法的矩陣乘法運(yùn)算是多項(xiàng)式時(shí)間復(fù)雜度的[3],但通路矩陣的元素(路徑集合)是n!數(shù)量級(jí)的(n為頂點(diǎn)個(gè)數(shù)).逐點(diǎn)循環(huán)遞歸算法使用帶回溯操作的深度優(yōu)先搜索法來(lái)求解所有哈密頓圈[4],其最壞時(shí)間復(fù)雜度為指數(shù)階.

近年來(lái)出現(xiàn)的一些智能算法,可對(duì)路徑選擇的全排列組合進(jìn)行一定的篩選.如遺傳算法使用繼承法從n個(gè)頂點(diǎn)的完全圖 Kn的所有哈密頓圈遞歸推出Kn+1的所有哈密頓圈,使用選擇法從Kn+1的所有哈密頓圈中刪除實(shí)際上不存在的哈密頓圈[5],但 n個(gè)頂點(diǎn)的完全圖Kn共有(n-1)!/2個(gè)哈密頓圈. DNA算法使用堿基(T、C、A、G)對(duì)圖的頂點(diǎn)和邊進(jìn)行 DNA分子編碼[6],每條邊甚至?xí)?3×1013個(gè)副本,DNA溶液用量是圖的規(guī)模(頂點(diǎn)和邊的數(shù)目)和所要解決問題的指數(shù)函數(shù),因此,該方法用于解決較大規(guī)模(如具有40個(gè)頂點(diǎn))的哈密頓圈問題是不現(xiàn)實(shí)的.Hopfield神經(jīng)網(wǎng)絡(luò)算法使用邊賦權(quán)的圓內(nèi)接正n邊形將哈密頓圈問題轉(zhuǎn)換成旅行商問題,定義最小偏差率,采用動(dòng)態(tài)消元法降低實(shí)際偏差率,但運(yùn)行狀態(tài)與最大迭代次數(shù)、運(yùn)行次數(shù)、種子數(shù)密切相關(guān),僅對(duì) 30個(gè)頂點(diǎn)以內(nèi)的簡(jiǎn)單圖進(jìn)行了實(shí)驗(yàn)[7].

文獻(xiàn)[8-9]中對(duì)簡(jiǎn)單連通無(wú)向圖 G使用充分條件“連通度κ(G)≥獨(dú)立數(shù)α(G)”來(lái)求解哈密頓圈,雖然基本圈擴(kuò)展操作是多項(xiàng)式時(shí)間復(fù)雜度的,但對(duì)于不滿足充分條件的哈密頓圖,該算法有可能找不到哈密頓圈,即存在路徑選擇的不確定性.如果想對(duì)所有的不滿足充分條件的哈密頓圖都有效,則必須進(jìn)行回溯操作.文獻(xiàn)[10]中使用路徑擴(kuò)展法求解隨機(jī)圖的哈密頓圈.在此基礎(chǔ)上,文獻(xiàn)[11-12]中對(duì)旋轉(zhuǎn)操作進(jìn)行了改進(jìn),時(shí)間復(fù)雜度分別為 O(n4+ε)和O(n3lgn),ε＞0.但這些算法存在如下不足:隨機(jī)圖的判定算法都是概率上的“幾乎總是”的“好”算法,但總有一些具體圖,使得這類算法失效.對(duì)于邊數(shù)超過(guò)3nlgn的最大非哈密頓圖的判定,這類算法往往失效.對(duì)于最小頂點(diǎn)度數(shù)為 k的最大非哈密頓圖共有條邊.由于旋轉(zhuǎn)操作的次數(shù)有一個(gè)閾值,當(dāng)超過(guò)該閾值而強(qiáng)行停止算法時(shí),有可能還沒有得到正確的結(jié)果.如果不設(shè)置閾值,則退化成完全回溯法.特殊圖的哈密頓圈算法存在多項(xiàng)式時(shí)間復(fù)雜度[13-15],但不能處理一般圖,甚至不能處理平面圖.隨機(jī)圖的哈密頓圈算法和特殊圖的哈密頓圈算法都是采用擴(kuò)展和旋轉(zhuǎn)技術(shù),對(duì)路徑選擇/基本圈選擇的全排列組合進(jìn)行啟發(fā)式篩選.

受文獻(xiàn)[8,16]中無(wú)向哈密頓圖的必要條件的啟發(fā),文中將“面”的視角換成原子圈的視角,對(duì)哈密頓圖的特征進(jìn)行研究,在提出基本圈的分解、合并、連通,以及原子圈(即不可分解的基本圈)和公共邊連通等概念的基礎(chǔ)上,提出了一個(gè)新的無(wú)向哈密頓圖的充分必要條件.根據(jù)這個(gè)充分必要條件,使用基本圈作為染色體,設(shè)計(jì)了一個(gè)具有自適應(yīng)特征的、融合了哈密頓圈領(lǐng)域知識(shí)的混合遺傳算法.自適應(yīng)主要表現(xiàn)在染色體是一種可拼接和可分解的編碼方案.混合方式是在繁殖(交叉、變異)算子構(gòu)造中融入了哈密頓圈是由一些具有單條公共邊連通特性的原子圈進(jìn)行合并而成的專門領(lǐng)域知識(shí).文中算法在搜索哈密頓圈的過(guò)程中,會(huì)朝著生成哈密頓圈或最大長(zhǎng)度基本圈的方向前進(jìn).對(duì)于哈密頓圖,經(jīng)過(guò)若干代進(jìn)化后,收斂于某一個(gè)哈密頓圈上;對(duì)于非哈密頓圖,經(jīng)過(guò)若干代進(jìn)化后,遺傳操作無(wú)法再繼續(xù)執(zhí)行,進(jìn)化現(xiàn)象不再發(fā)生,收斂于某一個(gè)最大長(zhǎng)度的基本圈.最后通過(guò)實(shí)例測(cè)試了文中算法的效果.

1 無(wú)向哈密頓圖的充分必要條件

定義1 給定簡(jiǎn)單連通無(wú)向圖G=(V,E),V為圖G的頂點(diǎn)集合,E為圖G的邊集合.基本圈C的一個(gè)分解是指圖G中一條邊e=(u,v)將長(zhǎng)度為r的基本圈C分割成長(zhǎng)度為s和t的兩個(gè)基本圈C1和C2.其中r+2=s+t,u,v∈V(C),V(C)=V(C1)∪V(C2),E(C)∪e=E(C1)∪E(C2).

定義2 給定簡(jiǎn)單連通無(wú)向圖G=(V,E),V為圖G的頂點(diǎn)集合,E為圖G的邊集合.兩個(gè)基本圈C1和 C2的一個(gè)合并是指由 C1和 C2的所有頂點(diǎn)構(gòu)成圖G中的一個(gè)基本圈C.其中V(C)=V(C1)∪V(C2),E(C)=E(C1)E(C2)=E(C1)∪E(C2)-E(C1)∩E(C2).

定義3 給定簡(jiǎn)單連通無(wú)向圖G=(V,E),V為圖G的頂點(diǎn)集合,E為圖G的邊集合.如果對(duì)任意的u∈V(C1)和v∈V(C2),都存在一條從u到v的路徑,則兩個(gè)基本圈C1和C2是連通的.

定義4 給定簡(jiǎn)單連通無(wú)向圖G=(V,E),V為圖G的頂點(diǎn)集合,E為圖G的邊集合.對(duì)于兩個(gè)基本圈C1和C2,如果存在一條邊e∈E(G),使得e∈E(C1)且e∈(E(C2),則稱邊e是基本圈C1和C2的公共邊,C1和C2以公共邊e連通.

定義5 給定簡(jiǎn)單連通無(wú)向圖G=(V,E),V為圖G的頂點(diǎn)集合,E為圖G的邊集合.不能分解成更小長(zhǎng)度基本圈的基本圈,稱為原子圈.

定理1 在簡(jiǎn)單連通無(wú)向圖中,一個(gè)基本圈要么是原子圈,要么總是可以分解成若干個(gè)原子圈,這些原子圈按照某種次序以單條公共邊連通.

定理2 在簡(jiǎn)單連通無(wú)向圖中,一個(gè)基本圈要么是原子圈,要么總是可以由若干個(gè)原子圈合并而成,這些原子圈按照某種次序以單條公共邊連通.

推論1 給定簡(jiǎn)單連通無(wú)向圖G=(V,E),V為圖G的頂點(diǎn)集合,E為圖G的邊集合為圖G的頂點(diǎn)個(gè)數(shù)),δ(G)≥2(δ(G)為圖G的最小頂點(diǎn)度數(shù)).圖G是哈密頓圖,當(dāng)且僅當(dāng)哈密頓圈要么是一個(gè)包含所有頂點(diǎn)的原子圈,要么總是可以分解成若干個(gè)原子圈,或者說(shuō),總是可以由若干個(gè)原子圈進(jìn)行合并而成,這些原子圈按照某種次序以單條公共邊連通.

2 自適應(yīng)遺傳算法

基于無(wú)向哈密頓圖的充分必要條件,文中提出一種自適應(yīng)遺傳算法,用于求解無(wú)向哈密頓圈問題.由于染色體是原子圈或基本圈,任意選擇的兩個(gè)染色體不一定能結(jié)合成新的染色體.只有符合交叉/變異運(yùn)算的前提條件的兩個(gè)染色體才能結(jié)合成新的染色體.所以,染色體編碼就具有可拼接、可分解的特點(diǎn),算法具有自適應(yīng)、利用專門領(lǐng)域知識(shí)的特點(diǎn).

2.1 可拼接/可分解的染色體編碼

定義6[17]如果A=a1a2…aL是一個(gè)L碼,B= b1b2…bM是一個(gè)M碼,則A∨B=a1a2…aLb1b2…bM稱為A與B的一個(gè)拼接.對(duì)應(yīng)地,A、B稱為D(D= A∨B)的一個(gè)分解.

定義 7[17]一個(gè)編碼 d稱為可拼接的,如果任意L碼A和M碼B的拼接A∨B仍是滿足相同特性的L+M碼.一個(gè)編碼d稱為可分解的,如果任何N碼D可分解表示為D=A∨B,其中A為L(zhǎng)碼,B為M碼,L和M是滿足L+M=N的任何正整數(shù),且D的解碼在下述意義下是可分解的:存在常數(shù)a、b、c,使得

其中d-1(*)表示*的解碼.

文獻(xiàn)[17]的研究結(jié)果表明,一個(gè)可拼接/可分解的編碼通常構(gòu)成遺傳算法自適應(yīng)實(shí)現(xiàn)的基礎(chǔ).它為用“小算法”求解“大問題”提供框架.

2.2 自適應(yīng)遺傳算法的設(shè)計(jì)

選擇基本圈作為染色體的編碼.染色體中基因座的碼值取自頂點(diǎn)編號(hào).基本圈的頂點(diǎn)個(gè)數(shù)作為該染色體的適應(yīng)度度量.初始種群由原子圈構(gòu)成,第一代及之后的種群由原子圈和基本圈混合構(gòu)成.根據(jù)適應(yīng)度比例選擇任意兩個(gè)染色體進(jìn)行配對(duì),按交叉概率執(zhí)行交叉操作.為保證交叉運(yùn)算后獲得的染色體仍是一個(gè)基本圈,要求參加交叉運(yùn)算的兩個(gè)染色體滿足以單條公共邊連通的條件.具體的交叉運(yùn)算就是將兩個(gè)染色體拼接成一個(gè)更大的染色體.如果兩個(gè)染色體僅有兩個(gè)頂點(diǎn)編號(hào)相同,且這兩個(gè)編號(hào)在一個(gè)染色體中是相鄰的,在另一個(gè)染色體中是不相鄰的,那么,通過(guò)對(duì)不相鄰的那個(gè)染色體重新排列頂點(diǎn)編號(hào),有可能使變異后的染色體與原來(lái)相鄰的染色體組成一個(gè)滿足以單條公共邊連通的染色體對(duì).當(dāng)然,重排頂點(diǎn)編號(hào)后,要保證染色體仍是一個(gè)基本圈.具體的變異運(yùn)算就是將一個(gè)染色體的頂點(diǎn)編號(hào)重新排列.終止進(jìn)化準(zhǔn)則如下:若存在一個(gè)長(zhǎng)度為n的染色體,則終止進(jìn)化;若不再有更長(zhǎng)的新染色體產(chǎn)生,則終止進(jìn)化;若不再有新染色體產(chǎn)生,則終止進(jìn)化.

2.3 初始種群的生成

初始種群的生成步驟如下:

(1)從某個(gè)頂點(diǎn)出發(fā),采用不帶回溯操作的深度優(yōu)先遍歷方法,在其遍歷路徑上尋找所有基本圈.

(2)依次以其它頂點(diǎn)為出發(fā)點(diǎn),重復(fù)第(1)步的過(guò)程.

(3)如果不存在任何基本圈,則該圖是樹或森林,算法停止;如果存在長(zhǎng)度為n的基本圈,則該圈就是一個(gè)哈密頓圈,算法停止;如果以每個(gè)頂點(diǎn)作為出發(fā)點(diǎn)的遍歷路徑上訪問的頂點(diǎn)個(gè)數(shù)不為 n,則該圖是不連通圖,算法停止.

(4)在已經(jīng)找到的基本圈集合中,最小長(zhǎng)度的基本圈是原子圈.依次用已知的原子圈過(guò)濾其它基本圈,剩下來(lái)的基本圈都是原子圈.

3 自適應(yīng)遺傳算法的性能分析

3.1 種群序列{X(t)}的收斂性

文獻(xiàn)[17]中使用概率分析法,討論了遺傳算法的收斂性.對(duì)于哈密頓圖,根據(jù)推論 1,必有一個(gè)哈密頓圈存在,所以由哈密頓圈作為元素組成的最優(yōu)解集合F*滿足F*≠ .隨著進(jìn)化代數(shù)的增加(即t→∞),必然有種群X(t)中包含哈密頓圈,即X(t)∩ F*≠ ,所以成立,即種群序列{X(t)}依概率弱收斂到F*.

3.2 初始種群的有效性

文中采用不完全法,即不帶回溯的深度優(yōu)先遍歷方法尋找基本圈和過(guò)濾基本圈方法生成原子圈,來(lái)生成初始種群,因此不能生成所有的原子圈,自適應(yīng)遺傳算法的收斂性取決于生成的初始種群的有效性.通過(guò)對(duì)原子圈包含的每條邊的分布規(guī)律進(jìn)行分析,不難發(fā)現(xiàn):每條邊至少在 3個(gè)不同的原子圈中出現(xiàn),每個(gè)頂點(diǎn)至少在 3個(gè)不同的原子圈中出現(xiàn);原子圈包含邊的分布規(guī)律較為隨機(jī)、均勻,原子圈包含頂點(diǎn)的分布規(guī)律也較為隨機(jī)、均勻;最小長(zhǎng)度的原子圈及其它長(zhǎng)度較小的原子圈,數(shù)量眾多,被遺漏的較少,且它們覆蓋了所有的頂點(diǎn);基于初始種群進(jìn)化生成的新種群有很大的變化,且包含的邊的分布規(guī)律較為隨機(jī)、均勻.因此,采用不完全法生成初始種群,仍然有很大機(jī)會(huì)概率保證初始種群的有效性,從而保證自適應(yīng)遺傳算法的收斂性.

4 實(shí)驗(yàn)及結(jié)果分析

使用C語(yǔ)言編程實(shí)現(xiàn)文中所提出的自適應(yīng)遺傳算法,對(duì)一些典型圖形以及樹、不連通圖、頂點(diǎn)數(shù)為 100以內(nèi)的隨機(jī)生成圖進(jìn)行程序判定.所有實(shí)驗(yàn)均在AMD Athlon(tm)64×2 Dual Core Processor 3600Hz/1GB內(nèi)存的計(jì)算機(jī)上進(jìn)行,結(jié)果見表1、2.

文獻(xiàn)[7]中提供了使用Hopfield神經(jīng)網(wǎng)絡(luò)求解10個(gè)城市的旅行商問題的運(yùn)算結(jié)果,實(shí)際迭代次數(shù)取決于圖的形狀和環(huán)境參數(shù)的初始狀態(tài),其變化范圍為 16～505.其中設(shè)定的運(yùn)行次數(shù)m=200,函數(shù)srand的種子數(shù)seed=8.

從表 1中可知,文中算法的時(shí)間開銷與初始種群的大小及圖形拓?fù)浣Y(jié)構(gòu)密切相關(guān),對(duì)于邊數(shù)或面數(shù)比較多的圖形(如Tutte圖、Grinberg圖),時(shí)間開銷增長(zhǎng)過(guò)快.根據(jù)表 2,跟蹤每一代的進(jìn)化結(jié)果,可以發(fā)現(xiàn)Tutte圖在第7代時(shí)就已經(jīng)找到最大圈,實(shí)驗(yàn)中發(fā)現(xiàn)Grinberg圖也存在類似現(xiàn)象.因此,文中算法的進(jìn)化代數(shù)還可以進(jìn)一步減少.和Hopfield神經(jīng)網(wǎng)絡(luò)方法[7],以及染色體編碼采用固定長(zhǎng)度為 n、由全部頂點(diǎn)編號(hào)組成一個(gè)字符串的遺傳算法等相比,文中算法的進(jìn)化代數(shù)明顯減少,遺傳算法的自適應(yīng)性能得到充分體現(xiàn).

表1 在幾種典型實(shí)例上自適應(yīng)遺傳算法的總體性能Table 1 General properties of adaptive genetic algorithm running on some typical cases

表2 在幾種典型實(shí)例上自適應(yīng)遺傳算法的進(jìn)化性能Table 2 Evolutionary properties of adaptive genetic algorithm running on some special cases

5 結(jié)語(yǔ)

無(wú)向哈密頓圈的判定問題至今還沒有找到一個(gè)多項(xiàng)式時(shí)間復(fù)雜度的判定算法.為此,文中提出一種效率更佳的近似算法,用于判定哈密頓圈問題.算法由初始種群生成算法和特殊染色體編碼的遺傳算法組成.由于染色體是一種可拼接和可分解的編碼方案,只有符合交叉/變異運(yùn)算的前提條件的兩個(gè)染色體才能結(jié)合成新的染色體,故遺傳算法具有自適應(yīng)的特點(diǎn).適應(yīng)度度量采用基本圈的頂點(diǎn)個(gè)數(shù),從而引導(dǎo)遺傳算法朝著最大基本圈的方向前進(jìn).實(shí)驗(yàn)結(jié)果表明,文中算法具有良好的求解性能.

[1] 王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析 [M].北京:電子工業(yè)出版社,2001:185-189.

[2] 姜新文.求解哈密頓圖判定問題的一個(gè)新算法 [J].計(jì)算技術(shù)與自動(dòng)化,1997,16(1):1-3.

Jiang Xin-wen.A new algorithm for solving the Hamiltonian graph p roblem[J].Computing Technology and Automation,1997,16(1):1-3.

[3] 郭俊杰,伊崇信,畢雙艷,等.哈密頓回路存在性判定及輸出算法[J].吉林大學(xué)自然科學(xué)學(xué)報(bào),1998(2): 5-8.

Guo Jun-jie,YiChong-xin,BiShuang-yan,et al.Existence judgement and output algorithm of the Ham iltonian circuit [J].Acta Scientiarum Naturalium Universitatis Jilinensis, 1982(2):5-8.

[4] 王彥棋.逐點(diǎn)循環(huán)遞歸法求哈密頓回路 [J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),2004,36(1):115-117,121.

Wang Yan-qi.Algorithm of cycle and recursion by every vertex for getting Hamilton cycle[J].Journal of Harbin Institute of Technology,2004,36(1):115-117,121.

[5] 王彥棋.用“遺傳”算法求任意圖的所有哈密頓回路[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),2004,36(12):1690-1692.

Wang Yan-qi.A genetic algorithm for getting all Hamilton cycles of any graph[J].Journal of Harbin Institute of Technology,2004,36(12):1690-1692.

[6] 洪龍,朱梧賈.Hamilton圈問題的DNA算法[J].南京航空航天大學(xué)學(xué)報(bào),2006,38(2):222-226.

Hong Long,Zhu Wu-jia.DNA algorithm for solution to Ham ilton cycle problem[J].Journal of Nanjing University of Aeronautics and Astronautics,2006,38(2):222-226.

[7] 陸生勛.用Hop field神經(jīng)網(wǎng)絡(luò)解哈密頓回路問題[J].浙江大學(xué)學(xué)報(bào):理學(xué)版,2010,37(2):180-184.

Lu Sheng-xun.Solving Hamilton cycle prob lem by using Hop field neural network[J].Journal of Zhejiang University:Science Edition,2010,37(2):180-184.

[8] West Douglas B.圖論導(dǎo)引[M].李建中,駱吉洲,譯.北京:機(jī)械工業(yè)出版社,2006:229-235.

[9] Chvátal V,Erd?s Paul.A note on Ham iltonian circuits [J].Discrete Mathematics,1972,2(2):111-113.

[10] Pósa Louis.Hamiltonian circuits in random graphs[J]. Discrete Mathematics,1976,14(4):359-364.

[11] Bollobás B,Fenner T I,Frieze Alan M.An algorithm for finding Hamilton cycles in random graphs[C]∥Proceedings of ACM Symposium on Theory of Computing. New York:ACM,1985:430-439.

[12] Frieze Alan M.Finding Hamilton cycles in sparse random graphs[J].Journal of Combinatorial Theory:Series B,1988,44(2):230-250.

[13] Johnson JRobert.Long cycles in themiddle two layers of the discrete cube[J].Journal of Combinatorial Theory: Series A,2004,105(2):255-271.

[14] Shields Ian,Shields Brendan J,Savage Carla D.An update on them idd le levels problem[J].Discrete Mathematics,2009,309(17):5271-5277.

[15] Shields Ian,Savage Carla D.A note on Ham ilton cycles in Kneser graphs[J].Bu lletin of the Institute for Combinatorics and Its App lications,2004,40:13-22.

[16] Grinberg E J.Plane homogeneous graphs of degree three without Ham iltonian circuits[J].Latvian Mathematics Yearbook,1968,5:51-58.

[17] 徐宗本,張講社,鄭亞林.計(jì)算智能中的仿生學(xué):理論與算法[M].北京:科學(xué)出版社,2004:13-14,67-69.