李建新

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

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

李建新1,2

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

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

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

0 引言

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

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

1 算法思想的由來(lái)

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

2 相關(guān)概念

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

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

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

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

結(jié)論2[8]任意圖G的點(diǎn)集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,任一無(wú)向圖G均可以劃分為極大完全子圖的并集,因此可以對(duì)一無(wú)向圖進(jìn)行極大完全子圖化.本算法首先按從大到小的順序產(chǎn)生出各個(gè)極大完全子圖,同時(shí)對(duì)不同的極大完全子圖的頂點(diǎn)著不同的顏色,然后返回著某種顏色最多的極大完全子圖即為最大完全子圖.為更突出表現(xiàn)算法思想,本算法采用清晰的自然語(yǔ)言進(jìn)行表達(dá),描述如下:

根據(jù)實(shí)際問(wèn)題進(jìn)行抽象,建立一無(wú)向圖G=(V,E);

for(對(duì)于每個(gè)頂點(diǎn)v)

{Full_degree=0;

Uncolor_degree=頂點(diǎn)v的度;}

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

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

{

v=Full_degree最高的未著色頂點(diǎn),

Full_degree相同情況下是Uncolor_degree最高的未著色頂點(diǎn),

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

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

fo r(與v鄰接的每個(gè)未著色頂點(diǎn)u)

{Full_degree++;

Uncolor_degree--;}

v的顏色=cj;

cj++

}

Return cj最大的完全子圖

3.2 算法運(yùn)用舉例

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

圖1 已知無(wú)向圖例圖

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

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

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

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

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

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

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

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

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

圖2 圖1精簡(jiǎn)處理后的例圖

4 實(shí)驗(yàn)驗(yàn)證

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

表2 實(shí)驗(yàn)用圖頂點(diǎn)數(shù)

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

5 結(jié)束語(yǔ)

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

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

[2] 郭 平,康艷榮,史曉晨.基于最大code碼的極大完全子圖算法[J].計(jì)算機(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].沈陽(yáng):東北大學(xué)出版社2004:103.

[8] 王世昌,蘭紹玉.極大完全子圖在管理決策中的應(yīng)用[J].計(jì)算機(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í)驗(yàn)師,在讀碩士,研究方向:算法設(shè)計(jì)、SOC測(cè)試方法.

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

2009-11-07