基于局部有限搜索的無(wú)向圖近似最大團(tuán)快速求解算法

摘要：無(wú)向圖最大團(tuán)求解是一個(gè)著名的NP-完全問(wèn)題,解決該問(wèn)題的經(jīng)典算法基本上都采用完全精確搜索策略。鑒于NP-完全問(wèn)題本身所固有的復(fù)雜性,這些算法或許僅適用于某些特殊的小規(guī)模圖,對(duì)于具有大規(guī)模頂點(diǎn)和邊的復(fù)雜圖還是顯得無(wú)力,難以適用。針對(duì)完全精確搜索策略下的無(wú)向圖最大團(tuán)求解算法的大部分時(shí)間都用于對(duì)圖進(jìn)行額外而無(wú)效的查找的問(wèn)題,采用分劃遞歸技術(shù)將圖劃分為鄰接子圖和懸掛子圖,然后對(duì)鄰接子圖進(jìn)行遞歸求解,而對(duì)懸掛子圖則通過(guò)設(shè)置搜索范圍控制函數(shù)進(jìn)行局部有限搜索。在DIMACS數(shù)據(jù)集上將所提算法與當(dāng)前主要的最大團(tuán)求解算法進(jìn)行對(duì)比實(shí)驗(yàn),結(jié)果表明,文中提出的局部有限搜索求解策略能在75%的基準(zhǔn)數(shù)據(jù)上獲得最大團(tuán),剩下不能得到最大團(tuán)的數(shù)據(jù)實(shí)際上也可以獲得接近于最大團(tuán)的近似最大團(tuán),但算法的平均求解時(shí)間僅為目前最大團(tuán)精確求解算法的20%左右。因此,在很多最大團(tuán)非精確要求的場(chǎng)景中,所提算法具有極高的應(yīng)用價(jià)值。