求最大完全子圖的啟發(fā)式著色算法

李建新

(1.宿州學(xué)院計算機科學(xué)與技術(shù)系,人工智能與數(shù)據(jù)挖掘研究室,安徽宿州234000; 2.合肥工業(yè)大學(xué)計算機與信息學(xué)院,安徽合肥230009)

求最大完全子圖的啟發(fā)式著色算法

李建新1,2

(1.宿州學(xué)院計算機科學(xué)與技術(shù)系,人工智能與數(shù)據(jù)挖掘研究室,安徽宿州234000; 2.合肥工業(yè)大學(xué)計算機與信息學(xué)院,安徽合肥230009)

本文提出了一種求最大完全子圖的啟發(fā)式著色算法.該算法通過為頂點著色將已知無向圖劃分為極大完全子圖的并集,再根據(jù)各極大完全子圖中頂點的多少選取最大完全子圖.隨后為提高算法執(zhí)行效率,又對該算法提出了一種精簡措施.最后將該算法運用于一集成電路測試數(shù)據(jù)編碼壓縮實驗中,證明了該算法對求解最大完全子圖的有效性.

最大完全子圖;極大完全子圖;啟發(fā)式算法;著色算法

0 引言

最大完全子圖(maximum comp leted sub-graph)問題是圖論中的一個經(jīng)典組合優(yōu)化問題,也是一類NP完全問題,對它的研究具有很大的理論和實用價值,該問題在實踐中被廣泛應(yīng)用于市場分析、方案選擇、管理決策、故障診斷、數(shù)據(jù)壓縮等不同領(lǐng)域.目前國內(nèi)外對最大完全子圖問題的求解有廣泛的研究,大致可分為確定性算法(exact algorithm)[1]和啟發(fā)式(heuristic algo rithm)[2-6]算法兩大類.確定性算法在求解頂點數(shù)相對較少、密度相對較低的圖時尚為有效,隨著研究的深入,遇到的問題復(fù)雜度越來越高(頂點增多和邊密度變大),確定性算法逐漸不能有效解決.針對該情況,一些學(xué)者提出了啟發(fā)式算法求解最大完全子圖問題,當(dāng)前的啟發(fā)式算法都基于以下幾類:順序貪婪啟發(fā)式算法[2]、遺傳算法[3]、神經(jīng)網(wǎng)絡(luò)[4]、模擬退火和禁忌搜索[5]、基于連續(xù)的啟發(fā)式算法[6]等,取得了令人滿意的效果.

著色算法是圖論中的一種經(jīng)典算法,它通過對圖的頂點著色或邊著色的途徑在方案選擇及地圖學(xué)等各個領(lǐng)域有著廣泛的運用.但通過文獻查詢,目前還沒有發(fā)現(xiàn)運用著色手段求解最大完全子圖的成熟算法,經(jīng)研究,本文推出一種對無環(huán)的簡單無向連通圖求解最大完全子圖的著色算法,該算法也是一種啟發(fā)式算法.

1 算法思想的由來

該算法思想來源于本人對集成電路的測試向量相容壓縮的研究.在對集成電路進行測試時,需要通過自動測試設(shè)備A TE(automatic test equipment)向測試芯片傳輸大量的測試數(shù)據(jù),為減少測試時間,降低測試成本,需要對測試數(shù)據(jù)進行壓縮,由于測試數(shù)據(jù)中含有大量無關(guān)位,向量間的相容性較好,因此可對測試向量采取相容壓縮的方法.相容是指兩測試向量對應(yīng)位相同或其中一位為無關(guān)位,相容壓縮是將測試集中相容的測試向量合并為一個向量.為追求最大壓縮率,需尋求測試集中的極大相容類,這個問題可映射為圖論中的極大完全子圖問題,并且可通過為頂點著色分類的方法劃分各個極大相容類,進一步研究可將該方法演化為求極大完全子圖(great completed subgraph)的一般算法,進而也就得到了求最大完全子圖的算法.

2 相關(guān)概念

定義1[7]通常把二元序組(V,E),稱為圖.記為:G( V,E),或G=(V,E).其中:V表示頂點集,V(G)={圖G中頂點的集合};E表示邊集,E(G)={圖G中邊的集合};

定義2[2]設(shè)H=(V’、E’),V’?V,E’?E.如果?x、y∈V’,H中都有連接x與y的邊,則稱H是G的完全子圖.如果不存在G的完全子圖M,使得V(H)?V(M),E (H)?E(M),則稱H為G的極大完全子圖.|V(H)|值最大的極大完全子圖稱為最大完全子圖.

引理[8]設(shè)R是集合A上的關(guān)系,P1、P2……是A中的所有等價類,于是A=P1∪P2∪P3……且Pi∩Pj=Φ(i≠j)

結(jié)論1[8]極大完全子圖的點集在兩兩相鄰的關(guān)系下是一等價類.

結(jié)論2[8]任意圖G的點集P(G)可劃分為所有極大完全子圖的并集,即P(G)=P(G1)∪P(G2)∪…∪P(Gk)∪…,且P(Gi)∩P(Gj)=φ,i≠j.Gi(i=1,2,…)是G的極大完全子圖.

3 求最大完全子圖的著色算法

3.1 算法描述

由上述結(jié)論2,任一無向圖G均可以劃分為極大完全子圖的并集,因此可以對一無向圖進行極大完全子圖化.本算法首先按從大到小的順序產(chǎn)生出各個極大完全子圖,同時對不同的極大完全子圖的頂點著不同的顏色,然后返回著某種顏色最多的極大完全子圖即為最大完全子圖.為更突出表現(xiàn)算法思想,本算法采用清晰的自然語言進行表達,描述如下:

根據(jù)實際問題進行抽象,建立一無向圖G=(V,E);

for(對于每個頂點v)

{Full_degree=0;

Uncolor_degree=頂點v的度;}

按照一定的順序放置顏色c1,c2,…,ck;初始化各顏色數(shù)值c1=c2=…=ck=0

w hile(G中所有頂點未完全著色)

{

v=Full_degree最高的未著色頂點,

Full_degree相同情況下是Uncolor_degree最高的未著色頂點,

兩者都相同情況下是索引較小的未著色頂點;

j=某種顏色的索引,這種顏色若已出現(xiàn)過,則著該顏色的全部頂點都要落在v的已著色的鄰接頂點范圍內(nèi),若沒有任何一種顏色的全部出現(xiàn)在v的已著色的鄰接頂點中,則j為從未出現(xiàn)過的顏色的最小索引;

fo r(與v鄰接的每個未著色頂點u)

{Full_degree++;

Uncolor_degree--;}

v的顏色=cj;

cj++

}

Return cj最大的完全子圖

3.2 算法運用舉例

為便于理解上述算法,現(xiàn)舉例說明,建立一簡單無向圖如圖1所示,對該圖運用上述啟發(fā)式算法進行著色的過程以及算法中關(guān)鍵變量的變化過程如表1所示,其中頂點序號vi是指圖1中的各個頂點;si是第指第i步,即stepi,其中s0是指初始狀態(tài);指針指向第i步所考察的需著色的頂點,每一步考察一個頂點及其與鄰接頂點的關(guān)系,并對它進行著色;Cj是顏色序號;Full_degree和Uncolo r_degree是控制各頂點著色情況的兩個變量;“無”是指初始時各頂點均無顏色;“-”是指保持前邊的值不變.

圖1 已知無向圖例圖

最終實現(xiàn)極大完全子圖的劃分結(jié)果如下:

著C1顏色的頂點集V(G1)={v1、v3、v7}

著C2顏色的頂點集V(G2)={v4、v6}

著C3顏色的頂點集V(G3)={v2、v8}

著C4顏色的頂點集V(G4)={v5}

經(jīng)比較知,由頂點集V(G1)構(gòu)成的完全子圖即為最大完全子圖.

表1 頂點著色過程及算法中關(guān)鍵量的變化過程

3.3 算法運用的精簡預(yù)處理

在實際問題中,經(jīng)常會遇到不必求解出所有的極大完全子圖,而只需要求出幾個相對較大的完全子圖的情況,在這種情況下,可以先對已知圖進行適當(dāng)?shù)木喬幚?再運用上述啟發(fā)式算法求解,將會大大提高算法執(zhí)行效率.經(jīng)過大量實例研究表明,一個圖的較大完全子圖往往存在于度數(shù)較高的一定數(shù)量的頂點之間,因此,對復(fù)雜圖精簡處理時可采取適度刪除低度數(shù)頂點及其邊的措施來降低圖的復(fù)雜性,進而降低算法執(zhí)行的時間和空間復(fù)雜度.比如在上述圖1中,如果先刪除掉度數(shù)為1的頂點V2、V5、V6及其由它們發(fā)出的邊,圖1將變?yōu)槿鐖D2所示,這時再運用著色算法求解最大完全子圖(由頂點V1、V3、V7組成),算法執(zhí)行效率會更高.

圖2 圖1精簡處理后的例圖

4 實驗驗證

本算法在集成電路測試數(shù)據(jù)某相容壓縮實驗中得以運用,順利地完成了實驗任務(wù),使實驗達到了預(yù)期的結(jié)果,同時驗證了本算法的有效性.實驗中以ISCAS-89基準電路的幾個規(guī)模較大的時序電路的M intest測試向量集的測試向量作為實驗對象,整個實驗在VC++環(huán)境中實現(xiàn).為了提高向量間的相關(guān)性,對集成電路S5378f、S9234f、S13207f、S15850f、S38417f、S35854f的各個測試集均采取了分組相容的措施,首先將測試集按列分組,根據(jù)每組測試分量間的相關(guān)性建立相關(guān)性無向圖(以鄰接表存儲),圖的頂點表示測試分量字段,邊表示測試分量間具有相關(guān)性,然后運用上述算法劃分極大完全子圖,每一個極大完全子圖內(nèi)的測試分量是兩兩相關(guān)的,可以合并為一個測試分量,達到壓縮的目的.因此隨著分組方法的不同,構(gòu)建的相關(guān)性無向圖邊數(shù)是大不相同的,邊數(shù)統(tǒng)計不具有確定性,但頂點數(shù)目是固定的,各測試集構(gòu)成的無向圖的頂點數(shù)規(guī)模如表2所列.

表2 實驗用圖頂點數(shù)

由表2可看出由各測試集的測試分量構(gòu)成的圖的頂點規(guī)模是較大的,由此也可以窺見圖的復(fù)雜性,并且分組越多,測試分量間的相關(guān)性越好,圖的邊密度越大.本算法在此實驗中發(fā)揮了巨大的作用,同時也顯示了它在求解多頂點高密度圖最大完全子圖問題中的有效性.

5 結(jié)束語

本文從理論到實踐闡釋了一種用于求解最大完全子圖的啟發(fā)式著色算法,該算法思路清晰,通過實驗證明該算法在處理多頂點高密度無向圖時較為有效.但作為一種啟發(fā)式算法,還有可能存在找不到最優(yōu)解,而只有近優(yōu)解的情況,因此本算法還有必要繼續(xù)優(yōu)化.實踐證明,在上述算法演進一節(jié)中所述的降低圖的復(fù)雜性的精簡處理措施除了可提高算法的執(zhí)行效率外,還有利于增加極大完全子圖的確定性,遴選出最大完全子圖,找到近優(yōu)解.因此算法的優(yōu)化除對算法本身進行改進外,還可考慮在不同需要的情況下對圖采取適當(dāng)?shù)木喆胧?另外,還可在圖的存儲結(jié)構(gòu)等方面進行研究.

[1] ADLEMAN L M.Molecular computation of solutions to combinatorial p roblems[J].Science,1994,226(11):1021 -1024.

[2] 郭 平,康艷榮,史曉晨.基于最大code碼的極大完全子圖算法[J].計算機科學(xué),2006,33(2):188-190.

[3] CARTER B,PARK K.How good are genetic algorithms at finding large cliques:an experimental study,Technical Report Bu-CS-93-015[R].Boston:Computer Science Dept.,Boston University,1993.

[4] BALLARD D H,GARDNER P C,SR IN IVASM A.Graph p roblemsand connectionist architectures,Technical Report TR 167[R].New Yo rk:Dep t Computer Science,University of Rochester,1987.

[5] AARTS E,KORST J.Simulated annealing and boltzmann machines,astochastic app roach to combinational op tim ization and neural computing[M].New York:Wiley,1989.

[6] PARDALOS PM,PH ILL IPSA T.Aglobal op timization app roach forsolving the maximum clique p roblem[J].International Jou rna l o f comp uter Mathema tic s,1990,33:209 -216.

[7] 孫 晶,張東林.離散數(shù)學(xué)[M].沈陽:東北大學(xué)出版社2004:103.

[8] 王世昌,蘭紹玉.極大完全子圖在管理決策中的應(yīng)用[J].計算機應(yīng)用,1995,15(4):29-31.

Heuristic Coloring Algorithm for a Maximum Complete Sub-graph

L IJianxin
(1.Department of Computer Science and Technology,Suzhou College,Suzhou 234000,China; 2.School of Computer and Info rmation,Hefei University of Tchnology,Hefei 230009,China)

A heuristic coloring algorithm for amaximum comp lete sub-graph wasput forward.According to the algorithm,a know n undirected graph wasmade into a union of great comp lete sub-graphs by coloring the vertices,and then amaximum comp lete sub-graph was selected according to the number of vertices in each great comp lete sub-graph.Subsequently,in order to imp rove the execution efficiency of the algo rithm,it w as simp lified.It w as finally put into use in an experiment of test data coding comp ression of an integrated circuit,w hich p roved that it w as effective in determ ining a maximum comp lete sub-graph.

maximum comp lete sub-graph;great comp lete sub-graph;heuristic algorithm;coloring algo rithm

book=1994,ebook=16

O157.6

A

1673-1794(2010)02-0009-03

李建新(1971-),男,實驗師,在讀碩士,研究方向:算法設(shè)計、SOC測試方法.

安徽省自然科學(xué)研究重點項目(KJ2010A 352),安徽省自然科學(xué)研究一般項目(KJ2010B224),宿州學(xué)院碩士科研啟動基金項目(2009YSS12)

2009-11-07