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