一種提高遺傳算法子圖挖掘效率的數(shù)據(jù)結(jié)構(gòu).pdf

1、目前復(fù)雜網(wǎng)絡(luò)上的數(shù)據(jù)挖掘大多結(jié)合子圖挖掘的算法進(jìn)行分析。為了適應(yīng)復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)量大、結(jié)構(gòu)復(fù)雜等特點(diǎn)，使用具有隨機(jī)性質(zhì)的多目標(biāo)遺傳算法進(jìn)行子圖挖掘是一個比較理想的策略。然而，使用多目標(biāo)遺傳算法進(jìn)行復(fù)雜網(wǎng)絡(luò)的子圖挖掘存在著一個不可忽視的問題:數(shù)據(jù)量巨大導(dǎo)致運(yùn)行速度慢，硬件資源利用效率低。過往的改進(jìn)方案多數(shù)集中在算法本身，但對于不同的類型的復(fù)雜網(wǎng)絡(luò)，則很難有同樣的改進(jìn)效果。
　　針對以上問題，本文從數(shù)據(jù)結(jié)構(gòu)作為切入點(diǎn)，提出一種新型圖數(shù)據(jù)結(jié)

2、構(gòu):鄰接樹。鄰接樹是在鄰接表的基礎(chǔ)上改進(jìn)而來的圖數(shù)據(jù)結(jié)構(gòu)，即把鄰接表的所有頭結(jié)點(diǎn)和所有表結(jié)點(diǎn)都改用AVL樹的方式組織，從而加快數(shù)據(jù)操作的效率?；舅枷肟扇缦潞喪?
　　1、頭結(jié)點(diǎn)用AVL樹組織后，稱為樹頭結(jié)點(diǎn);表結(jié)點(diǎn)則稱為樹尾結(jié)點(diǎn)。
　　2、每一個樹頭結(jié)點(diǎn)都有一個指針，指向相應(yīng)樹尾結(jié)點(diǎn)組成的樹的根結(jié)點(diǎn)。
　　3、樹頭結(jié)點(diǎn)和樹尾結(jié)點(diǎn)都有對應(yīng)圖中頂點(diǎn)的相關(guān)信息，而邊權(quán)信息存放在樹尾結(jié)點(diǎn)。
　　4、每當(dāng)有增加或刪除數(shù)據(jù)

3、的操作時，鄰接樹都進(jìn)行平衡維護(hù)。
　　本文將對鄰接樹的可行性進(jìn)行分析，并證明其相對于經(jīng)典的圖數(shù)據(jù)結(jié)構(gòu):鄰接矩陣、鄰接表、十字鏈表，在時間和空間上的綜合效率都有明顯提高。其中時間復(fù)雜度為O(log(n2))，空間復(fù)雜度為O(n)。本文設(shè)計兩類實(shí)驗(yàn)，一是隨機(jī)圖的增加、刪除、查找、修改四種操作實(shí)驗(yàn);二是針對用于子圖挖掘的多目標(biāo)遺傳算法實(shí)驗(yàn)。兩類實(shí)驗(yàn)的結(jié)果數(shù)據(jù)和相關(guān)分析可驗(yàn)證鄰接樹具有更優(yōu)的綜合效率。最后，本文總結(jié)鄰接樹的優(yōu)勢所在，并提出