無向圖最大團(tuán)求解是一個(gè)著名的NP-完全問題,解決該問題的經(jīng)典算法基本上都采用完全精確搜索策略。鑒于NP-完全問題本身所固有的復(fù)雜性,這些算法或許僅適用于某些特殊的小規(guī)模圖,對于具有大規(guī)模頂點(diǎn)和邊的復(fù)雜圖還是顯得無力,難以適用。針對完全精確搜索策略下的無向圖最大團(tuán)求解算法的大部分時(shí)間都用于對圖進(jìn)行額外而無效的查找的問題,采用分劃遞歸技術(shù)將圖劃分為鄰接子圖和懸掛子圖,然后對鄰接子圖進(jìn)行遞歸求解,而對懸掛子圖則通過設(shè)置搜索范圍控制函數(shù)進(jìn)行局部有限搜索。在DIMACS數(shù)據(jù)集上將所提算法與當(dāng)前主要的最大團(tuán)求解算法進(jìn)行對比實(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)非精確要求的場景中,所提算法具有極高的應(yīng)用價(jià)值。 

【文章頁數(shù)】：7 頁

【文章目錄】：
1 引言
2 相關(guān)工作
3 定義與定理
4 算法設(shè)計(jì)
    4.1 基本思想
    4.2 基于局部有限搜索的近似最大團(tuán)求解算法
5 實(shí)驗(yàn)及結(jié)果


【參考文獻(xiàn)】：
期刊論文
[1]求解最大團(tuán)問題的并行多層圖劃分方法[J]. 顧軍華,霍士杰,武君艷,尹君,張素琪.  計(jì)算機(jī)應(yīng)用. 2018(12)
[2]大規(guī)模稀疏圖的極大團(tuán)枚舉算法[J]. 何琨,鄒晟昊,周建榮.  華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版). 2017(12)
[3]基于蟻群優(yōu)化算法求解最大團(tuán)問題的研究[J]. 尹皓,宋晗.  南華大學(xué)學(xué)報(bào)(自然科學(xué)版). 2017(03)
[4]頂點(diǎn)加權(quán)最大團(tuán)問題的加權(quán)分治算法[J]. 黃飛,寧愛兵,劉志民,何詠梅,王永斐,張惠珍.  數(shù)學(xué)理論與應(yīng)用. 2017(02)
[5]關(guān)于最大團(tuán)問題的一種新算法[J]. 賈曉峰,郭廷花,續(xù)曉欣.  中北大學(xué)學(xué)報(bào)(自然科學(xué)版). 2006(02)
[6]求解圖的最大團(tuán)的一種算法[J]. 仲盛,謝立.  軟件學(xué)報(bào). 1999(03)



本文編號：3686602