• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    大規(guī)模圖頂點(diǎn)覆蓋的增量算法研究

    2020-11-19 07:24:14陳德剛
    關(guān)鍵詞:鄰接矩陣原點(diǎn)增量

    喬 龍,陳德剛

    (華北電力大學(xué) 數(shù)理學(xué)院,北京 102206)

    0 引言

    頂點(diǎn)覆蓋問(wèn)題[1]在圖論中是一個(gè)著名的NP完全問(wèn)題,在現(xiàn)實(shí)生活中應(yīng)用非常廣泛。例如,博物館展覽柜設(shè)計(jì)、大型網(wǎng)絡(luò)監(jiān)控節(jié)點(diǎn)的布置、大型交通運(yùn)輸線(xiàn)路網(wǎng)絡(luò)設(shè)計(jì)、集成電路設(shè)計(jì)等等。在人工智能大數(shù)據(jù)時(shí)代背景下,在實(shí)際問(wèn)題中涉及的往往是動(dòng)態(tài)圖,針對(duì)于這種具有增量變化的動(dòng)態(tài)圖設(shè)計(jì)出一種智能化的求解頂點(diǎn)覆蓋算法無(wú)疑具有重要的應(yīng)用價(jià)值。

    近年來(lái),國(guó)內(nèi)外學(xué)者設(shè)計(jì)出了一系列求解極小頂點(diǎn)覆蓋集合的算法,但就其增量問(wèn)題的相關(guān)研究卻很少。求解圖的極小頂點(diǎn)覆蓋集合,其傳統(tǒng)的思想是利用布爾變量的運(yùn)算[1-2],這是最基本的求解方法。但是其運(yùn)算復(fù)雜度,尤其是面對(duì)大規(guī)模的圖結(jié)構(gòu)模型問(wèn)題時(shí),達(dá)不到高效性的要求。吳春等[3]基于頂點(diǎn)覆蓋問(wèn)題的理論研究,發(fā)現(xiàn)最小點(diǎn)覆蓋問(wèn)題、最大獨(dú)立集問(wèn)題與最大團(tuán)問(wèn)題三者事實(shí)上是等價(jià)的。對(duì)于網(wǎng)絡(luò)監(jiān)測(cè)點(diǎn)部署,陶星宇[4]針對(duì)原有網(wǎng)絡(luò)中布置的監(jiān)測(cè)點(diǎn)不易變動(dòng)的問(wèn)題,提出了一種增量網(wǎng)絡(luò)監(jiān)測(cè)點(diǎn)的增量選取算法。丁三軍等[5]和Zhou T等[6]基于貪婪算法的思想研究了極小頂點(diǎn)覆蓋的求解與更新問(wèn)題。占善華等[7]提出了一種更新最小頂點(diǎn)覆蓋的增量式屬性約簡(jiǎn)算法。苗董晶等[8]研究了沖突圖中的極小頂點(diǎn)覆蓋算法。Wang L等[9]設(shè)計(jì)出的分支定界算法解決了大量圖的極小權(quán)重覆蓋問(wèn)題。對(duì)于加權(quán)頂點(diǎn)覆蓋,F(xiàn)ukunaga T等[10]求解出了加權(quán)的無(wú)向圖的最小權(quán)重的Steiner樹(shù)。Tang C等[11]利用博弈論的思想把加權(quán)頂點(diǎn)覆蓋問(wèn)題建模為不對(duì)稱(chēng)的博弈??芾诘萚12]基于Dijkstra 算法,以最短路長(zhǎng)的最大值為標(biāo)準(zhǔn),按照一定原則篩選出點(diǎn)覆蓋集合的頂點(diǎn)。王麗麗等[13]利用線(xiàn)性規(guī)劃松弛的方法實(shí)現(xiàn)對(duì)計(jì)算復(fù)雜度進(jìn)行預(yù)測(cè),在求一個(gè)圖論模型的點(diǎn)覆蓋集合上取得了不錯(cuò)的效果。聶曉燕等[14]和高琳等[15]研究了DNA計(jì)算標(biāo)簽的最小頂點(diǎn)覆蓋問(wèn)題。鄭少萍[16]和袁啟杰等[17]研究了Petersen圖的極小頂點(diǎn)覆蓋集合的求解問(wèn)題。這些研究進(jìn)一步豐富了極小頂點(diǎn)覆蓋的理論。

    在上述研究中,這些算法所面對(duì)的大部分是靜態(tài)圖。在面對(duì)動(dòng)態(tài)圖的時(shí)候沒(méi)有包含快速的更新頂點(diǎn)覆蓋的理論機(jī)制,因而在圖的規(guī)模擴(kuò)張時(shí)需要重新計(jì)算頂點(diǎn)覆蓋,會(huì)占用大量的計(jì)算和存儲(chǔ)資源。本文旨在針對(duì)大規(guī)模圖的增量變化問(wèn)題,找到可以高效更新頂點(diǎn)覆蓋的增量算法。為了研究出一種智能化更新極小頂點(diǎn)覆蓋的算法,并且就其時(shí)間復(fù)雜度而言滿(mǎn)足其高效性,我們從圖的極小頂點(diǎn)覆蓋集合的定義出發(fā),對(duì)大規(guī)模圖頂點(diǎn)數(shù)目增加、邊數(shù)目增加和頂點(diǎn)與邊數(shù)目均增加3種動(dòng)態(tài)過(guò)程分析了頂點(diǎn)覆蓋的增量機(jī)理。在此基礎(chǔ)上通過(guò)對(duì)圖的存儲(chǔ)矩陣、鄰接矩陣和關(guān)聯(lián)矩陣進(jìn)行更新,設(shè)計(jì)頂點(diǎn)覆蓋的更新迭代算法,使得更新后的極小頂點(diǎn)覆蓋集合能夠覆蓋到更新后圖中的所有的邊,并且能夠剔除圖中的冗余頂點(diǎn),能夠較快地得出較優(yōu)的解。

    1 圖的預(yù)備知識(shí)

    圖G由一個(gè)有序的二元組G=組成,其中V為圖G的點(diǎn)集,E為圖G的邊集。對(duì)于?v∈V,e∈E,用V(v)表示頂點(diǎn)v所鄰接的頂點(diǎn),用V(e)表示邊e連接的一組頂點(diǎn)。對(duì)于圖G中的邊集E={ei|ei∈E,i=1,2,…}中的ei一般可以分為有向邊和無(wú)向邊?;诖颂卣靼褕D分為兩類(lèi):其邊沒(méi)有方向的圖稱(chēng)為無(wú)向圖,否則稱(chēng)為有向圖。本文僅考慮無(wú)向圖的增量問(wèn)題。對(duì)于一個(gè)傳統(tǒng)的圖,它的邊集滿(mǎn)足E?V×V,否則該圖就被定義為超圖。對(duì)于圖中的2個(gè)頂點(diǎn)vp、vq,如果存在一條邊同時(shí)與vp、vq相連,那么稱(chēng)頂點(diǎn)vp、vq是相鄰接的,若2條邊ep、eq同時(shí)關(guān)聯(lián)于同一個(gè)頂點(diǎn),稱(chēng)此2條邊ep、eq是相鄰的。沒(méi)有邊關(guān)聯(lián)的頂點(diǎn)被稱(chēng)為孤立點(diǎn)。若一條邊關(guān)聯(lián)的2個(gè)頂點(diǎn)是相同的,那稱(chēng)此邊為環(huán)。

    為了把一個(gè)圖結(jié)構(gòu)存儲(chǔ)于計(jì)算機(jī)中,其所具有的特性一般會(huì)通過(guò)圖的鄰接矩陣和關(guān)聯(lián)矩陣的形式來(lái)進(jìn)行計(jì)算機(jī)操作與處理。這兩種表示方法在表示相同圖時(shí)具有唯一性,并且同一個(gè)圖的鄰接矩陣與關(guān)聯(lián)矩陣之間可以進(jìn)行轉(zhuǎn)化。

    設(shè)G=是簡(jiǎn)單無(wú)向圖,S為一個(gè)集合,S?V且S≠φ,若E中的每條邊都和S中的某個(gè)頂點(diǎn)相關(guān)聯(lián),則S是G的頂點(diǎn)覆蓋集。對(duì)于上述的點(diǎn)覆蓋集合S,若對(duì)?vi∈S?V,有S-{vi}都不是點(diǎn)覆蓋集合,那么S就是G的極小頂點(diǎn)覆蓋集合。

    對(duì)于求解頂點(diǎn)覆蓋問(wèn)題需要引出獨(dú)立集這個(gè)概念:集合I是V的非空子集,若I中任意兩個(gè)頂點(diǎn)都不相鄰,則I是圖G的獨(dú)立集。

    2 極小頂點(diǎn)覆蓋問(wèn)題的增量算法

    2.1 頂點(diǎn)覆蓋的增量問(wèn)題

    當(dāng)給定圖的頂點(diǎn)或者邊數(shù)目發(fā)生增量變化時(shí),原圖的極小頂點(diǎn)覆蓋集合是新圖點(diǎn)覆蓋集合的一個(gè)局部最優(yōu)解,因而需要將這個(gè)局部最優(yōu)解擴(kuò)展成為全圖的一個(gè)全局最優(yōu)解??紤]到以下兩種情況:1)頂點(diǎn)的增加:當(dāng)新增加的頂點(diǎn)只與原頂點(diǎn)覆蓋集合中的頂點(diǎn)相連時(shí),則更新后的頂點(diǎn)覆蓋集合保持不變;當(dāng)新增加的頂點(diǎn)只與非原點(diǎn)覆蓋集合中的頂點(diǎn)相連時(shí),那么此時(shí)頂點(diǎn)覆蓋集合也要隨之發(fā)生變化,此時(shí)便需要在原點(diǎn)覆蓋集合的基礎(chǔ)上增加或者刪除若干個(gè)頂點(diǎn);當(dāng)新增加的頂點(diǎn)既與原點(diǎn)覆蓋集合中的元素又與非原點(diǎn)覆蓋集合中的元素相連,那么可以不考慮新增加的點(diǎn)與原點(diǎn)覆蓋集中的點(diǎn)相連的邊。2)邊的增加:當(dāng)邊新加到原始圖中時(shí),可以分為兩種情況,其一是該邊與原點(diǎn)覆蓋集合中的點(diǎn)相連,這種情況易知新圖的點(diǎn)覆蓋集合保持不變;其二是該邊只與非原點(diǎn)覆蓋集合中的點(diǎn)相連,這種情況下,則更新后的點(diǎn)覆蓋集合便需要考慮增加必要的頂點(diǎn)和刪除冗余的頂點(diǎn),冗余的頂點(diǎn)即為不必要的頂點(diǎn)。

    定理1設(shè)圖G=,頂點(diǎn)集為V={v1,v2,…,vi},邊集為E,極小頂點(diǎn)覆蓋集合為N0,新加入頂點(diǎn)vi+1,若對(duì)?em∈E(vi+1),都存在vm∈N0,使得em與vm相關(guān)聯(lián),則N0不發(fā)生變化。

    證明由題意可知,加入頂點(diǎn)vi+1,對(duì)?em∈E(vi+1),都存在vm∈N0,使得em與vm相關(guān)聯(lián),那么則有:當(dāng)m=1時(shí),e1與頂點(diǎn)vi+1相關(guān)聯(lián),即為新加入的邊,因?yàn)榇嬖趘1∈N0,使得e1與v1相關(guān)聯(lián)。根據(jù)頂點(diǎn)覆蓋的定義可知,邊e1已經(jīng)被頂點(diǎn)v1所覆蓋,而v1是N0中的頂點(diǎn),那么可得N0已經(jīng)覆蓋了與vi+1關(guān)聯(lián)的一條邊e1。同理當(dāng)m=2時(shí),可證N0已經(jīng)覆蓋了與vi+1關(guān)聯(lián)的一條邊e2。假設(shè)當(dāng)m=1,2,…,m時(shí),N0已經(jīng)覆蓋了與vi+1關(guān)聯(lián)的一條邊em,下證當(dāng)m=m+1時(shí)成立。當(dāng)m=m+1時(shí),em+1和頂點(diǎn)vi+1相關(guān)聯(lián),em+1仍為新加入的邊,因?yàn)榇嬖趘m+1∈N0,使得em+1與頂點(diǎn)vm+1相關(guān)聯(lián),且vm+1∈N0,那么可得N0已經(jīng)覆蓋了與vi+1關(guān)聯(lián)的邊em+1。綜上所述,加入頂點(diǎn)vi+1而導(dǎo)致增加的邊em此時(shí)均被原極小頂點(diǎn)覆蓋集合N0所覆蓋,所以更新后的圖結(jié)構(gòu)模型極小頂點(diǎn)覆蓋集合不發(fā)生變化。定理得證。

    例1如圖1所示,已知圖G=,且它的其中一個(gè)極小頂點(diǎn)覆蓋集合為N0={v1,v4,v5},如果新加入頂點(diǎn)為vi+1,利用上述定理求解更新后的極小頂點(diǎn)覆蓋集合Nnew。

    由圖可以看出,新加入的頂點(diǎn)vi+1與非頂點(diǎn)覆蓋集合N0中的元素v2、v5相鄰接,求解步驟如下:

    第一步先在原點(diǎn)覆蓋集合N0中分別加入頂點(diǎn)v2、v5;

    第二步分別判斷與v2、v5相連的原N0中的頂點(diǎn)中是否存在冗余的頂點(diǎn)。對(duì)于和v2相鄰接的頂點(diǎn)有v1、v3,在比較過(guò)程中優(yōu)先刪去N0中度數(shù)較少的頂點(diǎn)。對(duì)于v1,與v1相連的所有的頂點(diǎn)是v2、v3,它們都屬于N0中的頂點(diǎn),根據(jù)定理2,此時(shí)v1可以刪去。對(duì)于v3,與v3相連的所有的頂點(diǎn)為v1、v2、v4、v5,它們都屬于N0中的頂點(diǎn),而刪去v1后,v3便不能再被刪去。對(duì)于v4,與v4相連的所有的頂點(diǎn)為v3、v5,它們都屬于N0中的頂點(diǎn),因此根據(jù)定理2可以刪去頂點(diǎn)v4。則有Nnew1=N0+{v2}-{v1}+{v5}-{v4}={v2,v3,v5};

    第三步求得頂點(diǎn)覆蓋集合Nnew2=N0+{vi+1}={v1,v3,v4,vi+1};

    第四步計(jì)算并比較Nnew1與Nnew2集合中元素的個(gè)數(shù),選取元素個(gè)數(shù)較少的集合為更新后的Nnew,更新后的極小頂點(diǎn)覆蓋集合為:Nnew=Nnew1={v2,v3,v5}。

    定理3設(shè)圖G=,頂點(diǎn)集是V,邊集為E={e1,e2,…,ei},極小頂點(diǎn)覆蓋集合是N0,新加入邊為ei+m,若對(duì)?ei+m都有?vm∈N0,使得ei+m與vm相關(guān)聯(lián),則原極小頂點(diǎn)覆蓋集合N0不變化。

    證明由題意知,當(dāng)加入邊ei+m時(shí),都有?vm∈N0,使得ei+m與vm是相關(guān)聯(lián)的,那么則有:當(dāng)m=1時(shí),ei+1作為新加入的邊與v1相關(guān)聯(lián),而v1∈N0,根據(jù)頂點(diǎn)覆蓋的定義可知,邊ei+1已經(jīng)被頂點(diǎn)v1所覆蓋,而v1是N0中的頂點(diǎn),那么可得N0已經(jīng)覆蓋了邊ei+1。同理當(dāng)m=2時(shí),可證N0已經(jīng)覆蓋了邊ei+2。假設(shè)當(dāng)m=1,2,…,m時(shí),N0已經(jīng)覆蓋了邊ei+m,下證當(dāng)m=m+1時(shí)成立。當(dāng)m=m+1時(shí),邊ei+m+1仍為新加入的邊,已經(jīng)被頂點(diǎn)vm+1所覆蓋,且vm+1∈N0,因此原頂點(diǎn)覆蓋集合N0已經(jīng)覆蓋了圖G中新加入的邊ei+m+1。綜上所述,新加入的邊ei+m均已被原頂點(diǎn)覆蓋集合N0所覆蓋,即更新后的圖結(jié)構(gòu)模型的極小頂點(diǎn)覆蓋集合N0不發(fā)生變化。定理得證。

    定理4設(shè)圖G=,頂點(diǎn)集是V,邊集為E={e1,e2,…,ei},極小頂點(diǎn)覆蓋集合是N0,新加入邊為ei+1,若?vp,vq∈V-N0,使得ei+1與vp、vq同時(shí)相關(guān)聯(lián),令V(ei+1)={vp,vq},則有如下結(jié)論:

    例2如圖2所示,G=,而且利用屬性約簡(jiǎn)的方法求出它的其中一個(gè)點(diǎn)覆蓋集合為N0={v1,v4,v5},新加入邊ei+1,與頂點(diǎn)v3、v6相關(guān)聯(lián),利用定理4求解更新后的頂點(diǎn)覆蓋集合Nnew。

    由圖可以看出,新增加的點(diǎn)ei+1與頂點(diǎn)v3、v6建立了新的鄰接關(guān)系,求解步驟如下:

    第一步依據(jù)定理4,把v3或者v6分別添加到點(diǎn)覆蓋集合N0中,然后分別考察與v3和v6相連的頂點(diǎn);

    第二步如果考慮把v3加入到點(diǎn)覆蓋集合中,那么與v3相連的頂點(diǎn)是v1、v4。對(duì)于v1,與v1關(guān)聯(lián)的所有頂點(diǎn)為v2、v3,其中v2是非N0中的元素,根據(jù)定理4,v1不能刪去。對(duì)于v4,與v4關(guān)聯(lián)的所有的頂點(diǎn)為v1、v2、v5、v6,其中v2、v6為非N0中的元素,因此v4不能刪去,可得Nnew1=N0+{v3}={v1,v3,v4,v5};

    第三步如果考慮把v6加入到點(diǎn)覆蓋集合中,那么與v3相連的頂點(diǎn)是v4、v5。對(duì)于v4,具上所述v4是不能刪去的。對(duì)于v5,與v5關(guān)聯(lián)的所有的頂點(diǎn)為v4、v6,均是原N0中的元素,因此v5可以刪去,可得Nnew2=N0+{v6}-{v5}={v1,v4,v6};

    第四步比較Nnew1與Nnew2集合中元素的個(gè)數(shù),選取元素個(gè)數(shù)較少的集合為更新后的Nnew,更新后的頂點(diǎn)覆蓋集合為:Nnew=Nnew2=N0+{v6}-{v5}={v1,v4,v6}。

    2.2 求解增量式頂點(diǎn)覆蓋的算法

    在這一部分,我們?cè)O(shè)計(jì)了一種新型的求解增量式頂點(diǎn)覆蓋的算法。給定一個(gè)圖G=,它的鄰接矩陣A(G)是一個(gè)|V|×|V|的實(shí)對(duì)稱(chēng)矩陣,由鄰接矩陣相應(yīng)的能求出圖的關(guān)聯(lián)矩陣。它的極小頂點(diǎn)覆蓋集合是N0,從關(guān)聯(lián)矩陣中可以發(fā)現(xiàn)N0中的所有頂點(diǎn)已經(jīng)覆蓋了E中的所有元素。當(dāng)圖結(jié)構(gòu)發(fā)生增量變化時(shí),它的極小頂點(diǎn)覆蓋集合變化情況分為以下3種情況:原頂點(diǎn)覆蓋集合不發(fā)生變化;原頂點(diǎn)覆蓋集合加入若干個(gè)必要的頂點(diǎn);原頂點(diǎn)覆蓋集合添加若干個(gè)必要的頂點(diǎn)同時(shí)刪除屬于原頂點(diǎn)覆蓋集合中冗余的頂點(diǎn)。

    算法1求解頂點(diǎn)增量變化極小頂點(diǎn)覆蓋集合

    輸入:圖G=,極小頂點(diǎn)覆蓋集合為N0,其鄰接矩陣為A(G);

    輸出:新的圖結(jié)構(gòu)的極小頂點(diǎn)覆蓋集合Nnew。

    對(duì)于j=1,2,…,m,新加頂點(diǎn)vi+j,令Vj={vi+j|j=1,2,…,m};

    步驟1判斷vi+j是否與N0中的頂點(diǎn)鄰接。如果與N0中的頂點(diǎn)鄰接或者沒(méi)有頂點(diǎn)與vi+j相鄰接,則Nnew1=N0。否則轉(zhuǎn)步驟2;

    步驟3取Nnew=min{Nnew1,Nnew2,Nnew3,Nnew4|點(diǎn)覆蓋數(shù)最小}。

    算法2求解邊的增量變化極小頂點(diǎn)覆蓋集合

    輸入:圖G=,極小頂點(diǎn)覆蓋集合為N0,其鄰接矩陣為A(G);

    輸出:新的圖結(jié)構(gòu)的極小頂點(diǎn)覆蓋集合Nnew。

    對(duì)于j=1,2,…,n,新加邊為ei+j;令Ej={ei+j|j=1,2,…,n};

    步驟1判斷ei+j是否與N0中的頂點(diǎn)關(guān)聯(lián)。若?vm∈N0,使得ei+1與vm是相關(guān)聯(lián)的,則Nnew1=N0;

    步驟4取Nnew=min{Nnew1,Nnew2,Nnew3|點(diǎn)覆蓋數(shù)最小}。

    上述兩個(gè)算法分別展示了與頂點(diǎn)的增量變化和邊的增量變化相對(duì)應(yīng)的算法。當(dāng)圖發(fā)生增量變化時(shí),要明確區(qū)分是頂點(diǎn)的還是邊的增量變化或者兩者均有,以便調(diào)用相對(duì)應(yīng)的算法。算法1適用于圖結(jié)構(gòu)模型中頂點(diǎn)發(fā)生增量變化時(shí)的情況,算法2適用于圖結(jié)構(gòu)模型中邊發(fā)生增量變化時(shí)的情況。當(dāng)同時(shí)發(fā)生頂點(diǎn)和邊的增量變化時(shí),把兩種情況拆分開(kāi)來(lái),先考慮頂點(diǎn)的增量變化,調(diào)用算法1,再考慮邊的增量變化,調(diào)用算法2。本文算法1的時(shí)間復(fù)雜度為o(|Vj|),算法2的時(shí)間復(fù)雜度為o(|Ej|),算法的運(yùn)行時(shí)間的變化取決于新加入頂點(diǎn)與邊的數(shù)目,且隨頂點(diǎn)與邊的數(shù)目的增長(zhǎng)呈線(xiàn)性增長(zhǎng)。

    3 實(shí)驗(yàn)對(duì)比

    算法的仿真分析過(guò)程在Windows 10系統(tǒng)下進(jìn)行。計(jì)算機(jī)硬件配置是Radeon R52.40 GHz,4GRAM,用到的計(jì)算機(jī)處理程序是Matlab 2018a與python3.0。數(shù)據(jù)來(lái)源為計(jì)算機(jī)編碼生成的隨機(jī)無(wú)向圖。實(shí)驗(yàn)比對(duì)結(jié)果如表1、表2所示。

    表1 圖的增量實(shí)驗(yàn)比對(duì)

    表2 算法時(shí)間復(fù)雜度實(shí)驗(yàn)比對(duì)

    表1中數(shù)據(jù)類(lèi)型分為增量前的極小頂點(diǎn)覆蓋數(shù)和增量后的極小頂點(diǎn)覆蓋數(shù),算法運(yùn)行時(shí)間是在對(duì)各個(gè)數(shù)據(jù)運(yùn)行10次后取的平均運(yùn)行時(shí)間。利用python運(yùn)行算法時(shí),第一次運(yùn)行會(huì)出現(xiàn)運(yùn)行時(shí)間較長(zhǎng),故第一次運(yùn)行時(shí)間不取值,之后的運(yùn)行時(shí)間兩者差值基本上在0.5 ms內(nèi)。這里的準(zhǔn)確率代表算法運(yùn)行后所得到的極小頂點(diǎn)覆蓋集合是否有意義,如果所得到的極小頂點(diǎn)覆蓋集合能滿(mǎn)足其定義,可以覆蓋更新后圖結(jié)構(gòu)中的所有的邊,那么所得到的極小頂點(diǎn)覆蓋集合是準(zhǔn)確的。

    另外我們通過(guò)實(shí)驗(yàn)數(shù)據(jù)檢驗(yàn)該算法相比非增量的算法是否更具有高效性,實(shí)驗(yàn)結(jié)果如表2所示。對(duì)其算法的時(shí)間復(fù)雜度分析發(fā)現(xiàn),文獻(xiàn)[3]算法運(yùn)行時(shí)間在頂點(diǎn)數(shù)較少時(shí)會(huì)出現(xiàn)運(yùn)行時(shí)間為0的情況,但是隨著頂點(diǎn)數(shù)目的增加,算法運(yùn)行時(shí)間是明顯增加的,而本文算法運(yùn)行時(shí)間增加的速度更慢,因此本文算法相比文獻(xiàn)[3]算法更具有高效性。

    算法首次模擬是對(duì)文章中例子的模擬,然后對(duì)頂點(diǎn)數(shù)和邊數(shù)進(jìn)行遞增實(shí)驗(yàn),在表1中第3、4、5條數(shù)據(jù)集中采用了控制變量的方法,分別對(duì)只增加頂點(diǎn)、只增加邊、頂點(diǎn)和邊同時(shí)增加的情況進(jìn)行了研究。得到:只增加頂點(diǎn)而邊集不發(fā)生變化對(duì)極小頂點(diǎn)覆蓋集合沒(méi)有影響,只增加邊直接調(diào)用算法2進(jìn)行求解,頂點(diǎn)和邊同時(shí)增加需要調(diào)用算法1和算法2。本節(jié)的實(shí)驗(yàn)驗(yàn)證了本文算法的準(zhǔn)確性是較高的,算法求出的極小頂點(diǎn)覆蓋集合能夠滿(mǎn)足大規(guī)模圖發(fā)生增量變化時(shí)快速求解極小頂點(diǎn)覆蓋集合的需求。

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

    本文針對(duì)于極小頂點(diǎn)覆蓋問(wèn)題的增量情況,從極小頂點(diǎn)覆蓋集合的定義出發(fā),設(shè)計(jì)了求解頂點(diǎn)增量變化極小頂點(diǎn)覆蓋集合的算法以及求解邊的增量變化極小頂點(diǎn)覆蓋集合的算法。有效地解決了對(duì)于圖結(jié)構(gòu)發(fā)生增量變化的極小頂點(diǎn)覆蓋集合的更新問(wèn)題。隨著大數(shù)據(jù)時(shí)代的到來(lái),數(shù)據(jù)的存儲(chǔ)量將是大規(guī)模的,該算法對(duì)于大型網(wǎng)絡(luò)監(jiān)控節(jié)點(diǎn)的動(dòng)態(tài)布置與重新確定圖結(jié)構(gòu)來(lái)求解出點(diǎn)覆蓋集合相比更具有高效性。

    猜你喜歡
    鄰接矩陣原點(diǎn)增量
    輪圖的平衡性
    提質(zhì)和增量之間的“辯證”
    “價(jià)增量減”型應(yīng)用題點(diǎn)撥
    Book Pilot 飛行選書(shū)師,讓書(shū)重新回到原點(diǎn)
    重返歷史“原點(diǎn)”的旅程
    在原點(diǎn)震蕩的擾動(dòng)Schr?dinger-Poisson系統(tǒng)的無(wú)窮多個(gè)解
    基于均衡增量近鄰查詢(xún)的位置隱私保護(hù)方法
    基于鄰接矩陣變型的K分網(wǎng)絡(luò)社團(tuán)算法
    關(guān)于原點(diǎn)對(duì)稱(chēng)的不規(guī)則Gabor框架的構(gòu)造
    一種判定的無(wú)向圖連通性的快速Warshall算法
    黄色a级毛片大全视频| 国产成人影院久久av| 老鸭窝网址在线观看| 天天躁夜夜躁狠狠久久av| 成人手机av| 亚洲免费av在线视频| 成人三级做爰电影| 丰满迷人的少妇在线观看| 色视频在线一区二区三区| 99国产精品99久久久久| 老司机影院成人| 色视频在线一区二区三区| 18禁裸乳无遮挡动漫免费视频| 国产精品成人在线| 国产黄频视频在线观看| 国产有黄有色有爽视频| 免费观看av网站的网址| 天堂中文最新版在线下载| 黄频高清免费视频| 天堂中文最新版在线下载| 十八禁人妻一区二区| 在线观看免费午夜福利视频| 99精品久久久久人妻精品| 日本av免费视频播放| 多毛熟女@视频| 女性被躁到高潮视频| 欧美av亚洲av综合av国产av| 交换朋友夫妻互换小说| 欧美少妇被猛烈插入视频| 亚洲精品日本国产第一区| 午夜影院在线不卡| 久久久亚洲精品成人影院| 国产男女内射视频| 国产精品国产三级国产专区5o| 久久毛片免费看一区二区三区| 国产精品 国内视频| 亚洲精品国产一区二区精华液| 99国产精品一区二区三区| 97在线人人人人妻| 国产免费福利视频在线观看| 亚洲国产中文字幕在线视频| 建设人人有责人人尽责人人享有的| 考比视频在线观看| 亚洲国产欧美一区二区综合| √禁漫天堂资源中文www| 一边摸一边抽搐一进一出视频| 少妇精品久久久久久久| 天天躁夜夜躁狠狠久久av| 黑人猛操日本美女一级片| 国产黄色视频一区二区在线观看| 国产不卡av网站在线观看| 亚洲一区二区三区欧美精品| 啦啦啦中文免费视频观看日本| 超碰97精品在线观看| 久久毛片免费看一区二区三区| 人人妻人人澡人人爽人人夜夜| 日韩,欧美,国产一区二区三区| 国产精品九九99| 美女高潮到喷水免费观看| 亚洲,欧美,日韩| 欧美老熟妇乱子伦牲交| 免费人妻精品一区二区三区视频| 制服人妻中文乱码| 欧美日韩亚洲高清精品| 99精国产麻豆久久婷婷| 免费久久久久久久精品成人欧美视频| 天堂俺去俺来也www色官网| 免费在线观看完整版高清| 嫁个100分男人电影在线观看 | 中文精品一卡2卡3卡4更新| 精品人妻在线不人妻| 国产精品香港三级国产av潘金莲 | 国产成人a∨麻豆精品| 夜夜骑夜夜射夜夜干| 欧美乱码精品一区二区三区| 亚洲一区中文字幕在线| 久久天堂一区二区三区四区| 一区在线观看完整版| 啦啦啦视频在线资源免费观看| 午夜精品国产一区二区电影| 国产不卡av网站在线观看| 精品人妻熟女毛片av久久网站| 午夜福利免费观看在线| 男女床上黄色一级片免费看| 亚洲精品久久成人aⅴ小说| 午夜福利乱码中文字幕| 国产一卡二卡三卡精品| 最近最新中文字幕大全免费视频 | 国产精品99久久99久久久不卡| 99国产综合亚洲精品| 最近中文字幕2019免费版| 免费在线观看完整版高清| 欧美激情极品国产一区二区三区| 精品免费久久久久久久清纯 | 亚洲精品国产av蜜桃| 91字幕亚洲| 女人高潮潮喷娇喘18禁视频| 宅男免费午夜| 看十八女毛片水多多多| 日韩大片免费观看网站| 久热爱精品视频在线9| 久久天堂一区二区三区四区| 精品国产一区二区久久| 亚洲欧美一区二区三区久久| 欧美乱码精品一区二区三区| 国产免费福利视频在线观看| 免费看十八禁软件| 首页视频小说图片口味搜索 | 日本欧美视频一区| 香蕉国产在线看| 国产成人免费无遮挡视频| 老熟女久久久| 一级片免费观看大全| 中国国产av一级| 久久久久网色| 一区二区三区激情视频| 日韩制服丝袜自拍偷拍| 午夜福利乱码中文字幕| 五月开心婷婷网| 久久精品亚洲av国产电影网| 免费一级毛片在线播放高清视频 | 黄色a级毛片大全视频| 老汉色∧v一级毛片| 国产欧美亚洲国产| 午夜激情久久久久久久| 秋霞在线观看毛片| 成在线人永久免费视频| 搡老乐熟女国产| 丝袜在线中文字幕| 成人亚洲欧美一区二区av| 色综合欧美亚洲国产小说| 国产精品免费视频内射| 国产亚洲欧美在线一区二区| av网站在线播放免费| a级毛片黄视频| 丁香六月天网| 日韩欧美一区视频在线观看| videos熟女内射| 日韩电影二区| 一二三四社区在线视频社区8| 黄频高清免费视频| 91国产中文字幕| 久久ye,这里只有精品| 免费看av在线观看网站| 免费观看av网站的网址| 久久99热这里只频精品6学生| 人人妻,人人澡人人爽秒播 | 男人爽女人下面视频在线观看| kizo精华| 18禁裸乳无遮挡动漫免费视频| 一级a爱视频在线免费观看| 亚洲男人天堂网一区| 又大又黄又爽视频免费| 欧美精品亚洲一区二区| 欧美日韩综合久久久久久| 亚洲国产欧美在线一区| 老司机靠b影院| 黑丝袜美女国产一区| 大片电影免费在线观看免费| 午夜视频精品福利| 精品福利永久在线观看| 丁香六月欧美| 精品人妻在线不人妻| 中文字幕人妻熟女乱码| 婷婷色综合www| 蜜桃在线观看..| 国产欧美日韩综合在线一区二区| 丝袜脚勾引网站| 国产欧美日韩精品亚洲av| 久久精品亚洲av国产电影网| 大码成人一级视频| 国产成人免费无遮挡视频| 国产精品国产三级国产专区5o| 日韩制服丝袜自拍偷拍| 国产精品二区激情视频| 看十八女毛片水多多多| 欧美日韩成人在线一区二区| 免费在线观看黄色视频的| 欧美日韩视频高清一区二区三区二| 精品高清国产在线一区| 水蜜桃什么品种好| 97在线人人人人妻| 欧美日本中文国产一区发布| 人成视频在线观看免费观看| 亚洲一卡2卡3卡4卡5卡精品中文| 国产男人的电影天堂91| 欧美久久黑人一区二区| 亚洲欧美精品综合一区二区三区| 国产深夜福利视频在线观看| 亚洲av美国av| 天天添夜夜摸| 亚洲欧美一区二区三区黑人| 操出白浆在线播放| 美女扒开内裤让男人捅视频| 一本综合久久免费| 国产片特级美女逼逼视频| 一二三四社区在线视频社区8| 狂野欧美激情性xxxx| 午夜两性在线视频| av有码第一页| 天天操日日干夜夜撸| 午夜两性在线视频| 女人被躁到高潮嗷嗷叫费观| avwww免费| 午夜福利,免费看| 欧美日本中文国产一区发布| 国产福利在线免费观看视频| 精品国产乱码久久久久久小说| 2021少妇久久久久久久久久久| a级片在线免费高清观看视频| 美女大奶头黄色视频| 久久av网站| 国产精品久久久人人做人人爽| 午夜福利在线免费观看网站| 香蕉国产在线看| 色综合欧美亚洲国产小说| 亚洲国产最新在线播放| 亚洲伊人色综图| 男的添女的下面高潮视频| 美女福利国产在线| 十八禁网站网址无遮挡| 久久午夜综合久久蜜桃| 亚洲国产看品久久| 首页视频小说图片口味搜索 | 日韩av在线免费看完整版不卡| 精品少妇内射三级| 国产91精品成人一区二区三区 | 日韩 欧美 亚洲 中文字幕| 日韩 欧美 亚洲 中文字幕| 亚洲一码二码三码区别大吗| av网站在线播放免费| a 毛片基地| 欧美老熟妇乱子伦牲交| 大型av网站在线播放| 视频区图区小说| 午夜激情久久久久久久| 日日夜夜操网爽| a级毛片黄视频| 日韩制服丝袜自拍偷拍| 天天添夜夜摸| 美女扒开内裤让男人捅视频| 国产亚洲一区二区精品| 99精国产麻豆久久婷婷| www.熟女人妻精品国产| 丝袜脚勾引网站| 看免费成人av毛片| 国产精品人妻久久久影院| 一二三四在线观看免费中文在| 男女午夜视频在线观看| 久热这里只有精品99| 成人手机av| 一本综合久久免费| 人人妻,人人澡人人爽秒播 | 性少妇av在线| 2021少妇久久久久久久久久久| 亚洲视频免费观看视频| 国产成人一区二区三区免费视频网站 | 91精品伊人久久大香线蕉| 亚洲图色成人| 香蕉丝袜av| 国产精品免费大片| 欧美av亚洲av综合av国产av| 色婷婷av一区二区三区视频| 亚洲专区中文字幕在线| 国产色视频综合| 热99国产精品久久久久久7| 国产精品.久久久| 国产高清videossex| 丁香六月天网| 在线观看免费午夜福利视频| 国产成人欧美| 国产黄色免费在线视频| 狂野欧美激情性bbbbbb| av网站免费在线观看视频| 午夜日韩欧美国产| 女人久久www免费人成看片| 男女高潮啪啪啪动态图| 精品一品国产午夜福利视频| 成人三级做爰电影| 国产xxxxx性猛交| 黄色片一级片一级黄色片| 亚洲精品第二区| 男女免费视频国产| 亚洲欧美清纯卡通| 久久人妻福利社区极品人妻图片 | 天堂中文最新版在线下载| 91精品国产国语对白视频| 久久亚洲国产成人精品v| 一边亲一边摸免费视频| 国产真人三级小视频在线观看| bbb黄色大片| 妹子高潮喷水视频| 亚洲一区二区三区欧美精品| 狂野欧美激情性bbbbbb| 久久免费观看电影| 欧美精品亚洲一区二区| 久久久久久久久久久久大奶| 成年人午夜在线观看视频| 国产男女超爽视频在线观看| 男男h啪啪无遮挡| www.999成人在线观看| 久久久久精品国产欧美久久久 | www.999成人在线观看| 男女国产视频网站| 一区福利在线观看| 久久久国产一区二区| 亚洲国产精品国产精品| 亚洲国产av影院在线观看| 亚洲五月色婷婷综合| 国产亚洲欧美在线一区二区| 国产成人免费观看mmmm| 99久久99久久久精品蜜桃| 丝袜喷水一区| 天天操日日干夜夜撸| 精品高清国产在线一区| 美女中出高潮动态图| 国产色视频综合| 亚洲情色 制服丝袜| 亚洲欧美日韩另类电影网站| 免费在线观看完整版高清| 日本av免费视频播放| 高潮久久久久久久久久久不卡| 亚洲三区欧美一区| 老汉色av国产亚洲站长工具| 校园人妻丝袜中文字幕| 亚洲国产日韩一区二区| 久久 成人 亚洲| 99re6热这里在线精品视频| 激情五月婷婷亚洲| 免费看不卡的av| 欧美中文综合在线视频| 赤兔流量卡办理| 国产精品三级大全| 另类亚洲欧美激情| 丰满迷人的少妇在线观看| 亚洲视频免费观看视频| 男女高潮啪啪啪动态图| 国产91精品成人一区二区三区 | 日韩中文字幕视频在线看片| 无遮挡黄片免费观看| 这个男人来自地球电影免费观看| 午夜久久久在线观看| 午夜老司机福利片| 亚洲精品久久午夜乱码| 久久精品国产a三级三级三级| 欧美激情极品国产一区二区三区| 日韩制服骚丝袜av| 9191精品国产免费久久| 欧美av亚洲av综合av国产av| 女性生殖器流出的白浆| 成人黄色视频免费在线看| 天天躁日日躁夜夜躁夜夜| 热99久久久久精品小说推荐| 国产一区二区 视频在线| 午夜福利一区二区在线看| √禁漫天堂资源中文www| 精品一品国产午夜福利视频| 亚洲精品国产色婷婷电影| 久久毛片免费看一区二区三区| 欧美少妇被猛烈插入视频| 久久久精品免费免费高清| 多毛熟女@视频| 考比视频在线观看| 两个人看的免费小视频| 日韩,欧美,国产一区二区三区| 看免费av毛片| 成人亚洲精品一区在线观看| 午夜日韩欧美国产| 免费女性裸体啪啪无遮挡网站| 91九色精品人成在线观看| 叶爱在线成人免费视频播放| 色播在线永久视频| 久久久精品免费免费高清| 免费不卡黄色视频| 亚洲熟女毛片儿| 黄频高清免费视频| 脱女人内裤的视频| 欧美av亚洲av综合av国产av| 日韩大码丰满熟妇| 久久精品亚洲熟妇少妇任你| 欧美激情 高清一区二区三区| 国产麻豆69| 激情视频va一区二区三区| 久久av网站| 国产成人av教育| 女人爽到高潮嗷嗷叫在线视频| 国产真人三级小视频在线观看| 亚洲色图 男人天堂 中文字幕| 欧美人与性动交α欧美软件| 欧美精品一区二区大全| 午夜两性在线视频| 欧美成狂野欧美在线观看| 亚洲精品国产区一区二| 中文字幕人妻熟女乱码| 亚洲国产精品国产精品| 国产一区亚洲一区在线观看| 国产主播在线观看一区二区 | 亚洲第一av免费看| 欧美少妇被猛烈插入视频| 蜜桃在线观看..| 国产精品一区二区免费欧美 | 亚洲人成电影免费在线| 精品人妻一区二区三区麻豆| 中文精品一卡2卡3卡4更新| 一区福利在线观看| 黑人欧美特级aaaaaa片| 成人免费观看视频高清| 国产精品久久久久成人av| 99国产精品一区二区蜜桃av | 中文字幕最新亚洲高清| 亚洲精品美女久久av网站| 午夜福利视频精品| 天堂中文最新版在线下载| 亚洲欧美中文字幕日韩二区| 久久99精品国语久久久| 天天躁夜夜躁狠狠躁躁| 一本—道久久a久久精品蜜桃钙片| 在线观看一区二区三区激情| 久久久精品94久久精品| 亚洲精品美女久久久久99蜜臀 | av网站免费在线观看视频| 久热爱精品视频在线9| 91国产中文字幕| 中文字幕亚洲精品专区| 一本—道久久a久久精品蜜桃钙片| 男女无遮挡免费网站观看| 国产片内射在线| 黄片小视频在线播放| 亚洲色图综合在线观看| 女人久久www免费人成看片| 欧美乱码精品一区二区三区| 欧美精品人与动牲交sv欧美| 婷婷色av中文字幕| 极品人妻少妇av视频| 天天影视国产精品| 国产高清国产精品国产三级| 久久久久精品人妻al黑| 一级毛片我不卡| 男女下面插进去视频免费观看| 亚洲欧美一区二区三区国产| 免费观看a级毛片全部| 久久精品国产a三级三级三级| 少妇的丰满在线观看| 日本欧美视频一区| 久久热在线av| 夫妻性生交免费视频一级片| 亚洲欧美中文字幕日韩二区| 后天国语完整版免费观看| 欧美黑人精品巨大| 久久久久久久久免费视频了| 午夜福利在线免费观看网站| 丝袜脚勾引网站| 成人手机av| 久久人人97超碰香蕉20202| 成人国产av品久久久| 一级黄片播放器| 久9热在线精品视频| 亚洲少妇的诱惑av| 一级毛片电影观看| 美女高潮到喷水免费观看| 中文字幕精品免费在线观看视频| 久久天躁狠狠躁夜夜2o2o | 少妇的丰满在线观看| av视频免费观看在线观看| 校园人妻丝袜中文字幕| 中文字幕另类日韩欧美亚洲嫩草| 精品少妇一区二区三区视频日本电影| 久久精品久久久久久噜噜老黄| 欧美精品高潮呻吟av久久| 精品一区在线观看国产| 女性生殖器流出的白浆| 美女国产高潮福利片在线看| 一区二区三区精品91| 日韩制服丝袜自拍偷拍| 免费久久久久久久精品成人欧美视频| 91精品三级在线观看| 咕卡用的链子| 又大又爽又粗| 黑人巨大精品欧美一区二区蜜桃| 国产精品免费大片| 国产欧美亚洲国产| av不卡在线播放| 欧美日韩成人在线一区二区| 人人妻,人人澡人人爽秒播 | 欧美在线黄色| 午夜免费鲁丝| 久久国产精品大桥未久av| 中文乱码字字幕精品一区二区三区| 国产精品偷伦视频观看了| 亚洲av在线观看美女高潮| www.精华液| 国产一区二区三区综合在线观看| 一区二区三区乱码不卡18| 久久天躁狠狠躁夜夜2o2o | 欧美日韩亚洲国产一区二区在线观看 | 在线天堂中文资源库| 国产成人啪精品午夜网站| 亚洲国产看品久久| 亚洲精品国产一区二区精华液| 日韩视频在线欧美| xxx大片免费视频| 男人添女人高潮全过程视频| 国产亚洲午夜精品一区二区久久| 久久久国产欧美日韩av| 首页视频小说图片口味搜索 | 可以免费在线观看a视频的电影网站| 十八禁高潮呻吟视频| 亚洲精品乱久久久久久| 精品国产一区二区三区四区第35| 久久久久久亚洲精品国产蜜桃av| 成年av动漫网址| 精品久久久久久电影网| 丝瓜视频免费看黄片| 久久久精品国产亚洲av高清涩受| 国产一级毛片在线| 嫁个100分男人电影在线观看 | 超色免费av| 久久人人爽人人片av| 汤姆久久久久久久影院中文字幕| 国产视频一区二区在线看| 十八禁人妻一区二区| 亚洲五月色婷婷综合| 岛国毛片在线播放| 麻豆av在线久日| 丝袜脚勾引网站| 亚洲av欧美aⅴ国产| 亚洲午夜精品一区,二区,三区| 成年美女黄网站色视频大全免费| 精品久久久精品久久久| 欧美激情高清一区二区三区| 一区二区三区乱码不卡18| 狠狠婷婷综合久久久久久88av| 夜夜骑夜夜射夜夜干| 久久中文字幕一级| 国产精品熟女久久久久浪| 超碰97精品在线观看| 亚洲av欧美aⅴ国产| 国产老妇伦熟女老妇高清| 国产福利在线免费观看视频| 97人妻天天添夜夜摸| 视频在线观看一区二区三区| 韩国高清视频一区二区三区| 香蕉国产在线看| 久久久久久久大尺度免费视频| 国产极品粉嫩免费观看在线| 亚洲av成人不卡在线观看播放网 | 18禁黄网站禁片午夜丰满| 精品国产一区二区三区四区第35| 日日夜夜操网爽| 伊人亚洲综合成人网| 韩国精品一区二区三区| 各种免费的搞黄视频| 免费少妇av软件| av网站在线播放免费| 一区福利在线观看| 国产高清videossex| 男女无遮挡免费网站观看| 男女高潮啪啪啪动态图| 亚洲国产精品999| 黄色怎么调成土黄色| 久久精品人人爽人人爽视色| 天天躁日日躁夜夜躁夜夜| 国产福利在线免费观看视频| 亚洲精品一卡2卡三卡4卡5卡 | 人人妻人人澡人人爽人人夜夜| 国产免费视频播放在线视频| 国产熟女欧美一区二区| 亚洲专区国产一区二区| 国产成人免费观看mmmm| 久久精品国产亚洲av涩爱| 国产精品久久久久久精品电影小说| 国产成人av教育| 宅男免费午夜| 免费日韩欧美在线观看| 视频区图区小说| 宅男免费午夜| 老司机影院成人| 又大又黄又爽视频免费| 国产一卡二卡三卡精品| 欧美国产精品va在线观看不卡| 在线观看免费午夜福利视频| 免费看不卡的av| 老司机深夜福利视频在线观看 | 国产成人a∨麻豆精品| 国产伦人伦偷精品视频| 97人妻天天添夜夜摸| 两性夫妻黄色片| 伊人久久大香线蕉亚洲五| 国产一区亚洲一区在线观看| 赤兔流量卡办理| 亚洲精品久久午夜乱码| 亚洲av电影在线进入| 99国产精品一区二区三区| 日本午夜av视频| 另类亚洲欧美激情| av不卡在线播放| 亚洲欧美成人综合另类久久久| 亚洲国产精品999| 男人爽女人下面视频在线观看| 日韩制服骚丝袜av| 亚洲成av片中文字幕在线观看| 久久久久网色| av在线app专区| 亚洲色图综合在线观看| 婷婷色麻豆天堂久久| 免费少妇av软件| 色播在线永久视频| 国产一区二区三区av在线| 80岁老熟妇乱子伦牲交| 亚洲精品国产av成人精品| 操出白浆在线播放| 亚洲第一青青草原| 国产精品久久久久久精品电影小说| 操美女的视频在线观看| 看免费成人av毛片|