ECQ網絡中嵌入哈密頓圈的高效算法研究

周東仿

(1.上海出版印刷高等?？茖W校出版傳媒研究院，上海 200093；2.蘇州大學計算機科學與技術學院，江蘇 蘇州 215006)

0 引言

互連網絡的拓撲結構一直是并行計算領域研究的熱點，受到了國內外學者的廣泛關注。迄今為止，人們陸續提出了多種互連網絡拓撲結構，如超立方體網絡(Hypercube)[1]、交叉立方體(crossed cube，CQ)網絡[2]、莫比烏斯立方體(Mobius cube，MQ)網絡[3]、扭立方體(twisted cube，TQ)網絡[4]。這幾種n-維的互連網絡的鏈路數均為n2n-1。為了既降低網絡成本開銷又保持網絡性能不受影響，同時減少網絡連接的復雜度，Loh等進一步在超立方體網絡基礎上有條理地刪除一些邊，構建了一種新的網絡——交換超立方體(exchanged hypercube，EH)網絡[5]。在維度相同的情況下，與超立方體網絡相比，EH網絡的鏈路數約為超立方體網絡鏈路數的一半，而直徑與超立方體網絡的直徑近似相等。

為了既降低網絡直徑又減少網絡構造成本，以保持良好的網絡性能，Li等[6]在CQ網絡基礎上構建了一種新的網絡，即交換交叉立方體(exchanged crossed cube，ECQ)網絡。該網絡既保持了CQ網絡的許多優越性質，又融合了EH網絡的良好性質。首先，ECQ網絡的直徑為同維EH網絡直徑的一半，與同維CQ網絡的直徑幾乎相等。其次，ECQ網絡的鏈路數約為同維CQ網絡的鏈路數的一半，與同維EH網絡的鏈路數相等。另外，ECQ網絡還具有良好的可擴展性、可分割性、同構性[6]、可嵌入性[7-8]和可診斷性[9]等。

一個互連網絡可以用一個簡單無向圖G來表示。圖G的頂點V(G)表示網絡中的處理器(或處理機)，邊E(G)表示處理器(或處理機)之間的通信鏈路。若圈C包含圖G中所有頂點一次且僅一次，則稱G具有哈密頓性質、圈C為哈密頓圈。

如果在網絡的路由算法中使用哈密頓圈，則能夠減少或避免死鎖和擁塞，提高通信效率[10]。其次，哈密頓性問題可視為不交路徑覆蓋問題的一個特例。例如一對二不交路徑覆蓋性問題本質上就是哈密頓性問題。再者，如果在互連網絡或數據中心網絡的故障診斷中使用哈密頓性質，則能降低該網絡故障診斷的次數，實現該網絡的故障檢測與快速定位，從而進一步提高該網絡故障診斷的效率。除此之外，哈密頓性質也可應用在計算機科學編碼中[10]。因此，研究網絡的哈密頓性質具有重要價值。但是，并不是所有的網絡都具有哈密頓性質，且如何判定一個網絡是否具有哈密頓性質的充分必要條件也是不存在的。哈密頓圈或哈密頓路徑的求解也是一個多項式復雜程度的非確定性多項式(non-deterministic polynomial，NP)問題[11-14]。

盡管對一般互連網絡哈密頓性質的求解問題是NP完全問題，但是對一些特定網絡中的哈密頓問題求解已經得到解決。本文研究了ECQ網絡的哈密頓性質，給出了在ECQ網絡中構造哈密頓圈的算法。具體是：給出了當s≥3并且t≥3時，從ECQ網絡中任意一個結點出發即可高效地構造出哈密頓圈;分析了當1≤s≤2并且s≤t時，從ECQ網絡中任意一個結點出發哈密頓圈的構造算法，也考慮了所有情形，確保了研究問題的完備性；通過模擬試驗，對該算法進行了驗證。

1 準備工作

定義1.1 設u=u1u0、v=v1v0，u、v均為二進制字符串。若滿足(u,v)∈{(00,00),(10,10),(01,11),(11,01)}，那么稱u與v是相關的,記為u～v[2]。

①當n為偶數時，un-2=vn-2。

X3和X4如圖1所示。

圖1 X3和X4

根據文獻[6]和ECQ網絡的基本性質，對ECQ網絡進行如下定義。

定義1.3 (s+t+1)維的ECQ網絡可表示為:ECQ(s,t)=(V,E)。其中：s≥1且t≥1；V為頂點集，V={as-1...a0bt-1...b0c|ai,bj,c∈{0,1},i∈[0,s- 1],j∈[0,t- 1]}；E為邊集，由三種邊集(E1、E2和E3)組成，且E1、E2和E3互不相交，E=E1∪E2∪E3。ECQ網絡中任意兩個頂點u與v，有u、v∈V。

邊集E1、E2和E3定義如下。

①(u,v)∈E1,有且只有u[0]≠v[0]，u⊕v=1。其中，?表示異或操作。

②(u,v)∈E2,有且只有u[t:1]=v[t:1],u[0]=v[0]=0,并且(u[s+t:t+1],v[s+t:t+1])∈E(Xs)。

③(u,v)∈E3,有且只有u[s+t:t+1]=v[s+t:t+1],u[0]=v[0]=1，并且(u[t:1],v[t:1])∈E(Xt)。

由以上的定義可知，ECQ(s,t)具有2s+t+1個頂點、(s+t+2)2s+t-1條邊，并且ECQ(s,t)和ECQ(t,s)是同構的，一個ECQ(s,t)可分成2s個Xt和2t個Xs[6]。ECQ(2,3)如圖2所示。圖2中：虛線表示E1邊；細實線表示E3邊；粗實線表示E2邊。

為了簡便，不妨假設s≤t,把“as-1...a0bt-1...b0c”簡寫成“abc”。

圖2 ECQ(2,3)

2 哈密頓圈算法設計

Chen等給出了在Xn中時間復雜度為O(n)的求解哈密頓圈的LGC算法[13]。其基本思想如下。

(1)設πn=(d1,d2,…,dn)是1,2…n的一個隨機排列，滿足:①min(dn-1,dn)為奇數； ②|dn-1-dn|=1。

(2)構造以下數列。

RLπ(1)=d1，RLπ(i)=RLπ(i-1),di,RLπ(i-1)(2≤i≤n),RLπ=RLπ(n)=(p1,p2,…,p2n-1)。

(3)對任一點u,ui=neighbor(ui-1,pi)。

(u0,u1,…,u2n-1)為Xn中的哈密頓回路。

當3≤s≤t時，首先在Xn基礎上，按照LGC算法構造Xn的哈密頓圈。方法如下。

假設(a0,a1,…an-1)、(b0,b1,…bm-1)分別為Xs和Xt中構造出的哈密頓回路(其中n=2s,m=2t)。則按照LGC算法以及ECQ(s,t)的定義，構造如下。

a0b00→a0b01→a0b11→a0b10→a1b10→a1b11→…→a1bm-10→a1bm-11→a1b01→a1b00→a2b00→a2b01→a2b11→a2b10→a3b10→a3b11…→a3bm-10→a3bm-11→a3b01→a3b00→…an-2b00→an-2b01→an-2b11→an-2b10→an-1b10→an-1b11→…→an-1bm-10→an-1bm-11→an-1b01→an-1b00→

以上即為ECQ(s,t)上的哈密頓回路。由于該構造方法是根據ECQ(s,t)的定義在常數時間內即可構造完成，所以該算法是高效的。進一步考慮了1≤s≤2的情形。當1≤s≤2且s≤t時，設計了FindHcycle算法，即考慮了所有情形。

算法:FindHcycle

輸入:ECQ(s,t)上任意一個結點，且滿足1≤s≤2，s≤t。

輸出:若存在一個哈密頓圈HC，則輸出并返回。

a←ECQ(s,t)中第一個結點；

v←a；

l←0；

s.push(v)；

flag←1；

while(stack s is not empty) do

v=s.peek();

ifl=2s+t +1-1

then ifv與a相鄰

then return HC；

elsev←s.pop()；

flag←0；

l←l-1；

end if

elsev←next(v);

ifv!=null and flag !=true

thens.push(v)；

flag =true；

l←l+1；

elsev←s.pop()；

flag←0;

l←l-1；

end if

end if

end while

3 仿真試驗

通過仿真試驗，對FindHcycle算法和證構造算法進行有效性和正確性驗證。試驗環境是內存為8 GB、CPU為Intel(R) Core(TM) i5-3320M/4核/2.60G Hz的筆記本電腦，操作系統為64位Windows 7系統。該試驗揭示了如何在ECQ(s,t)網絡上使用FindHcycle算法和構造算法快速構建出哈密頓圈。按照ECQ網絡的定義，首先模擬構造出ECQ(2,3)網絡、ECQ(3,3)網絡。當ECQ網絡的規模更大時，該構造算法也能給出相應的運行結果。因篇幅有限，更大規模的ECQ網絡結點數目較多，不再進行列舉。

對于ECQ(3,3) 網絡,運行上述構造算法相應的程序，如在其中任選取一個頂點(如0001100)為起點，得到的哈密頓圈如下。如<0001100 ,0001101,0000101,0000100>表示ECQ(3,3)中起點為0001100、終點為0000100的一條路徑。以此類推，為了節省空間，省去了“，”。下同。

<0001100 0001101 0000101 0000100

1000100 1000101 1000001 1000000 0000000

0000001 0001001 0001000 1001000 1001001

1001011 1001010 0001010 0001011 0000111

0000110

1000110 1000111 1000011 1000010 0000010

0000011 0001111 0001110 1001110 1001111

1001101 1001100 1101100 1101101 1100101

1100100 0100100 0100101 0100001 0100000

1100000 1100001 1101001 1101000 0101000

0101001 0101011 0101010 1101010 1101011

1100111 1100110 0100110 0100111 0100011

0100010 1100010 1100011 1101111 1101110

0101110 0101111 0101101 0101100 0111100

0111101 0110101 0110100 1010100 1010101

1010001 1010000 0110000 0110001 0111001

0111000 1011000 1011001 1011011 1011010

0111010 0111011 0110111 0110110 1010110

1010111 1010011 1010010 0110010 0110011

0111111 0111110 1011110 1011111 1011101

1011100 1111100 1111101 1110101 1110100

0010100 0010101 0010001 0010000 1110000

1110001 1111001 1111000 0011000 0011001

0011011 0011010 1111010 1111011 1110111

1110110 0010110 0010111 0010011 0010010

1110010 1110011 1111111 1111110 0011110

0011111 0011101 0011100 0001100>。

對于ECQ(2,3) 網絡,運行FindHcycle算法對應的程序，如在其中任選取一個結點(如101100)為起點，得到的哈密頓圈如下。

<101100 101101 100101 100100 110100

110101 110111 110110 100110 100111 100011

100010 110010 110011 110001 110000 100000

100001 101001 101000 111000 111001 111011

111010 101010 101011 101111 101110 001110

001111 001011 001010 011010 011011 011001

011000 001000 001001 000001 000000 010000

010001 010011 010010 000010 000011 000111

000110 010110 010111 010101 010100 000100

000101 001101 001100 011100 011101 011111

011110 111110 111111 111101 111100 101100>。

仿真試驗進一步驗證了本文構造算法和算法FindHcycle的有效性和正確性。

4 結論

本文給出了在ECQ網絡中求解哈密頓圈的構造算法，通過仿真試驗實現了該算法并給出了試驗結果，進一步驗證了算法的正確性和有效性，為該網絡高效地通信提供理論參考依據[15]。

由于在網絡中發生故障是不可避免的，基于當前研究成果，下一步研究將考慮ECQ網絡的容錯哈密頓性質。