• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      一種新的生成樹組隨機求取算法

      2022-10-08 11:07:08董張卓
      關(guān)鍵詞:支路定義節(jié)點

      董張卓,羅 輝,齊 洋

      (1.西安石油大學(xué) 電子工程學(xué)院,陜西 西安 710065; 2.西安科技大學(xué) 電氣與控制工程學(xué)院,陜西 西安 710054)

      引 言

      在電力[1-2]、通信、管網(wǎng)、公路網(wǎng)、醫(yī)療[3-4]等實際問題以及優(yōu)化設(shè)計中,通過一定方法將問題等效成一個平面圖,用不包括環(huán)路能達到每一個節(jié)點的連通圖,即對圖的生成樹的求解[5],得到工程問題的可行解是一個典型的方法。

      此類問題均可歸為針對無向圖和有向圖求生成樹的問題,求解該類問題目前有數(shù)種方法。第一種方法是BST算法[6],用子樹集的概念從空集出發(fā),按節(jié)點的編號順序,逐一向集合中添加至少在有向圖G的一顆以r為根的生成樹上的支路,直至得到該圖的某個生成樹為止。第二種方法是在G-M算法[7]的基礎(chǔ)上,從根出發(fā),找到以r為根的圖G的每棵生成樹中都存在的支路e,確定搜索時間和搜索空間后,采用基于深度優(yōu)先搜索方法[8]得到生成樹,提高方法的運行效率。第三種方法是給有向圖賦權(quán)后以權(quán)值為參考生成最小生成樹[1]。

      以上算法僅適用于求解節(jié)點數(shù)和支路數(shù)較少的圖的生成樹,且隨著圖的規(guī)模增大,求解效率逐漸變低,同時,這些算法一般應(yīng)用于求解一棵生成樹,并不適合于求解一組生成樹。為此,本文提出一種基于簡化圖的生成樹算法。為了減小問題的規(guī)模,首先定義簡化規(guī)則將圖進行簡化,在簡化圖的基礎(chǔ)上,提出一種隨機生成樹組求解算法得到生成樹的集合,即建立一種通過對原圖和對應(yīng)的樹圖通過輪盤賭的方式隨機選擇支路進行遷移的算法,生成連通圖。通過多次應(yīng)用生成樹計算方法,生成不同的樹,得到生成樹組。

      1 生成樹計算模型

      定義1 大規(guī)模復(fù)雜連通圖GF∷=,其中BF為支路集合,NF為節(jié)點集合。

      計算連通圖GF的生成樹組時,為了減小生成樹的計算量,首先對不涉及到生成樹的支路圖部分進行簡化得到簡化圖,針對簡化圖G計算得到的生成樹組加上簡化的部分即為原連通圖的樹組。不失一般性,在圖的簡化過程中,只給出簡化方法;計算過程中,只針對簡化圖進行計算。

      1.1 復(fù)雜連通圖的簡化

      為了減小復(fù)雜圖的規(guī)模,對其進行簡化得到簡化圖。將圖中不涉及環(huán)路的輻射支路、節(jié)點以及直接串聯(lián)的支路進行化簡。為此給出以下概念的定義:

      定義2 輻射通路,不包含在任何環(huán)路中的通路稱為輻射通路;

      定義3 互斥支路,由度為2的節(jié)點連接的兩條支路稱為互斥支路。

      定義4 互斥支路集,集合{bi|i=1,2,…,nb},若bi和bi+1互斥,且bi+1和bi+2互斥,i=1,2,…,nb-2,稱集合為互斥支路集

      輻射通路不存在于任何環(huán)路中,所以不參與生成樹的生成過程。同時由定義3知,互斥支路集在求取開環(huán)圖時最多只需打開一條支路。因此,將互斥支路進行合并。故根據(jù)圖論的相關(guān)概念和上述定義,給出復(fù)雜圖的簡化規(guī)則:①刪除復(fù)雜圖中所有輻射通路;②將復(fù)雜圖中的互斥支路集等效為一條支路。

      1.2 簡化圖生成樹算法

      1.2.1 過渡圖的定義

      定義5 簡化圖,圖G為圖GF經(jīng)過簡化后得到的圖:

      G∷=。

      (1)

      其中:B為圖中的支路集合,B={bi|i=1,2,…,nb},bi為圖中支路的編號,nb為圖中支路個數(shù),N為圖中的節(jié)點集合,N={ni|i=1,2,…,nn},ni為圖中節(jié)點的編號,nn為圖中節(jié)點個數(shù)。

      定義6 生成樹圖GT,圖G的生成樹定義為含有圖G所有節(jié)點連通的無環(huán)路的一個子圖:

      GT∷=

      (2)

      其中:BT為圖中的支路集合,BT={bTi|i=1,2,…,nTb},bTi為支路的編號,nTb為生成樹中支路個數(shù);NT為圖中的節(jié)點集合NT={nTi|i=1,2,…,nTn},nTi為節(jié)點的編號,nTn為生成樹節(jié)點個數(shù)。

      定義7 過渡圖GB,生成樹圖過程中的一個臨時圖,初始時由簡化圖G生成,完全等值于簡化圖G,按照算法生成樹的過程中,逐漸遷出一些支路,完成生成樹計算后,圖GB中為圖G的連支,

      GB∷=。

      (3)

      其中:BB為圖中的支路集合;NB為圖中的節(jié)點集合。

      1.2.2 生成樹組樹支未選中概率

      為保證生成樹組計算過程中樹的多樣性,以及考慮生成樹組在后期計算過程中效率降低問題,在第一次計算完成得到第一個生成樹后,對化簡圖G以及過渡圖GB的支路加入選中作為樹支的計數(shù)值iNoc_T,即某一支路在一棵生成樹中出現(xiàn)一次,該支路的計數(shù)值iNoc_T+1,當(dāng)計算完成的樹的總數(shù)為iTn_T時,某條支路作為樹支的概率為

      (4)

      則支路未選中作為樹支的概率

      Pn_t=1-Pt。

      (5)

      1.2.3 隨機生成樹計算原理

      一顆隨機生成樹的計算過程分為3個部分,初始化部分,支路遷移循環(huán)部分、線索支路搜索部分。

      初始化部分:過渡圖GB的生成、生成樹圖GT初始化以及在生成樹計算過程中記錄當(dāng)前支路和當(dāng)前處理節(jié)點的變量的定義。過渡圖GB初始化為原圖G,生成樹圖GT的支路集合和節(jié)點集合為空集。在圖GB中用輪盤賭算法隨機選擇的一條支路bk,取支路bk關(guān)聯(lián)的節(jié)點j。在圖GB中移除bk,圖GT中添加支路bk及支路兩端的節(jié)點i,j,即圖GT的BT={bk},NT={i,j},當(dāng)前節(jié)點C_n=j。

      支路遷移循環(huán)部分:在圖GB以當(dāng)前節(jié)點C_n為線索,得到其關(guān)聯(lián)的支路集Bsel={bj|j=1,2,…,nb},用輪盤賭算法隨機從支路集Bsel中選中一條支路bk,得到其對端節(jié)點j,如果j?NT,C_b=bk,C_n=j,圖GB中移除C_b=bk,圖GT中添加支路C_b、節(jié)點C_j,重開始支路遷移部分;否則,轉(zhuǎn)執(zhí)行線索支路搜索。

      線索支路搜索部分:遍歷GB中支路,取支路bk的對應(yīng)節(jié)點i,j,如果i?NT∨j?NT成立,得到C_b=bk,C_n=i?NTi:j,轉(zhuǎn)支路遷移循環(huán),否則,計算完成。

      在每次計算得到新的生成樹后,更新圖G中支路計數(shù)值iNoc_T以及生成樹數(shù)目iTn_T,并在下一次生成樹的計算過程中以Pn_t為基準(zhǔn)采用輪盤賭的方式對當(dāng)前節(jié)點的待選支路集中的支路進行選擇。

      1.2.4 隨機生成樹組的形成

      為了得到一組完全的生成樹,需多次應(yīng)用上述隨機生成樹算法形成生成樹組。將得到的生成樹存入生成樹組時,將支路按序號從小到大排序,逐一對已有生成樹方案中的支路進行對比,判別該生成樹是否與已有的方案相同,若相同,移除該方案并重新生成新的生成樹;若不同,則存入生成樹組。

      2 隨機生成樹算法實現(xiàn)

      以圖1為例,包含28個節(jié)點和32條支路,對隨機生成樹計算過程進行說明,給出隨機生成樹的計算方法。

      圖1 復(fù)雜無向連通圖Fig.1 Complex undirected connected graph

      2.1 簡化過程

      按照上述簡化規(guī)則對該圖進行簡化得對應(yīng)的簡化圖圖2。

      圖2 復(fù)雜圖對應(yīng)的簡化圖Fig.2 Simplified graph corresponding to complex graph

      2.2 隨機生成樹計算過程

      以圖2所示化簡圖為例,進行生成樹的計算過程說明,過程如圖3所示。

      圖3 生成樹生成過程圖Fig.3 Generation process of spanning tree

      2.3 算法過程中節(jié)點與支路的數(shù)據(jù)表示

      根據(jù)圖的特點,使用關(guān)系表的形式描述節(jié)點和支路的連接關(guān)系,見表1。

      表1 節(jié)點與支路的連接關(guān)系表Tab.1 Connection relationship between nodes and branches

      數(shù)組A分3個域:A1域為節(jié)點編號,A2域、A3域分別為節(jié)點度和節(jié)點連接的支路的編號序列。

      將等效后的支路與等效前的支路進行對應(yīng),對應(yīng)關(guān)系見表2。

      表2 支路與互斥支路集的對應(yīng)關(guān)系表Tab.2 Correspondence between branch and mutually exclusive branch set

      B的元素分2個域:B1域為簡化圖中支路編號,B2域為復(fù)雜圖中對應(yīng)的互斥支路組中的支路編號。表3即為復(fù)雜圖1中互斥支路集與簡化圖2中支路的對應(yīng)關(guān)系表。

      表3 支路與互斥支路組對應(yīng)表Tab.3 Correspondence between branches and mutually exclusive branch sets

      在圖GB中的支路屬性中,加入一個選中為樹支的計數(shù)器,用來記錄支路選中為樹支的次數(shù)。生成樹組的存貯采用結(jié)構(gòu)見表4。

      表4 生成樹的支路對應(yīng)關(guān)系表Tab.4 Correspondence among branches of spanning tree

      數(shù)組C分3個域:C1域為樹的編號,C2域、C3域分別為支路的編號和樹支的編號序列。

      2.4 隨機生成樹組計算過程

      隨機生成樹組計算步驟及流程如圖4所示。

      步驟1:初始化圖G中各支路的未選中計數(shù)值iNoc_T=0,樹個數(shù)iTn_T=0。

      步驟2:初始化建立GT

      (1)建立支路和節(jié)點集合BT={},NT={};建立當(dāng)前支路變量C_b,以及當(dāng)前節(jié)點變量C_n。

      (2)隨機選取圖GB中支路BB中的一條支路bk,得到支路兩端的節(jié)點i,j,圖GT中添加支路bk,及支路兩端的節(jié)點,即圖GT的BT={bk},NT={i,j}。

      (3)從GB中將支路bk移除,BB=BB-{bk}。

      (4)C_b=bk,C_n=j。

      步驟3:對當(dāng)前節(jié)點、以及當(dāng)前支路的處理。

      (1)從圖GB中,得到當(dāng)前節(jié)點C_n連接的支

      路集合Bsel,如果Bsel=?,轉(zhuǎn)(6)。

      (2)基于Pn_t采用輪盤賭的方式從Bsel中選擇一條支路bk,(a)得到bk對應(yīng)另一側(cè)節(jié)點j,判斷節(jié)點j?NT,即不為GT的節(jié)點,轉(zhuǎn)(3)。否則Bsel=Bsel-{bk}并隨機選取一支路bk,為空轉(zhuǎn)(6),否則轉(zhuǎn)(a)。

      (3)C_b=bk,C_n=j。

      (4)GT中加入bk,即BT=BT+bk},NT=NT+j}。

      (5)GB中移除支路bk,即BB=B-{bk},轉(zhuǎn)(1)。

      (6)遍歷GB中支路,取支路bk節(jié)點i,j,如果i?NT∨j?NT成立,得到C_b=bk,C_n=i?NTi:j,轉(zhuǎn)(1),否則,轉(zhuǎn)步驟3。

      步驟4:輸出GB,GT中支路集合BB、BT。

      圖4 隨機生成樹算法流程圖Fig.4 Flow chart of random spanning tree algorithm

      步驟5:判別新生成的生成樹GT成與生成樹組中已有的生成樹是否相同,相同轉(zhuǎn)步驟1,不相同則存入生成樹組,同時圖G更新支路計數(shù)值iNoc_T++;樹個數(shù)iTn_T++。

      步驟6:判斷是否達到設(shè)定循環(huán)次數(shù),即生成樹的個數(shù)iTn_T是否達到設(shè)定的值,若達到則退出運行,否則,轉(zhuǎn)步驟2。

      3 算 例

      在VS2015平臺下用VC++編制了提出的生成樹算法,分別用圖1中的復(fù)雜圖和圖7中的PG & E69節(jié)點電力系統(tǒng)圖為例對提出的算法進行了驗證。

      3.1 算例1

      對圖1中的復(fù)雜圖簡化后得簡化圖2,對簡化圖2中的節(jié)點和支路進行分類并處理,使用文中提出的方法共生成291個簡化圖對應(yīng)生成樹圖,表5為圖的生成樹連支組(僅列出10組);生成2 227個圖1對應(yīng)生成樹,表6為復(fù)雜圖的生成樹連支組(僅列出10組)。

      表5 簡化圖生成樹對應(yīng)連支組Tab.5 Connected branch group corresponding to spanning tree of simplified graph

      從表5結(jié)果可以看出,本文中方法可以生成簡化圖對應(yīng)的生成樹圖,方法正確有效。圖5為簡化圖2斷開支路集{2,4,7,8,9}得到的一個生成樹圖。

      圖5 簡化圖2對應(yīng)的一種生成樹圖Fig.5 A spanning tree graph corresponding to simplified graph in Fig.2

      針對圖5中的生成樹圖逆用簡化規(guī)則,將簡化圖中斷開的支路對應(yīng)的互斥支路集任一支路打開,并將刪除得輻射式支路重新添加即可得復(fù)雜圖對應(yīng)的生成樹圖。圖6為圖1中復(fù)雜圖斷開支路集{4,12,25,23,27}得到的一個生成樹圖,表6為復(fù)雜圖1對應(yīng)生成樹的結(jié)果。

      圖6 復(fù)雜圖1對應(yīng)的一種生成樹圖Fig.6 A spanning tree graph corresponding to complex graph in Fig.1

      表6 復(fù)雜圖1的生成樹對應(yīng)連支組Tab.6 Connected branch group corresponding to spanning tree of complex graph in Fig.1

      從表6中結(jié)果和圖6可以看出,本文中方法可以生成復(fù)雜圖對應(yīng)的生成樹,方法正確有效。

      3.2 算例2

      圖7為PG & E69節(jié)點電力系統(tǒng)圖,包含支路73條,節(jié)點69個。

      對圖7中的圖簡化后進行生成樹組的計算,共生成6 296組對應(yīng)的生成樹圖。圖7的生成樹連支組見表7(僅列出10組)。如圖8所示,列出圖7對應(yīng)的一種生成樹圖。

      表7 69節(jié)點系統(tǒng)生成樹對應(yīng)連支組Tab.7 Connected branch groups corresponding to 69 node system spanning tree

      圖8 PG & E69節(jié)點系統(tǒng)圖對應(yīng)生成樹圖Fig.8 Spanning tree graph corresponding to PG & E69 node system diagram

      從表7中結(jié)果和圖8可以看出,本文中方法可以正確有效地生成重構(gòu)可行解圖。

      3.3 方法性能對比

      在相同的連通性判斷方法下,分別采用本文中方法和文獻[2]的BST算法對圖1和圖7生成500棵生成樹。平均生成一棵生成樹計算時間見表8。

      表8 同一算例下不同方法平均計算時間對比Tab.8 Average calculation time of the same example using different methods

      從表8可知:針對包含28個節(jié)點和32條支路的圖1,本文方法的平均計算時間為0.57 ms,文獻[2]中的BST算法平均計算時間為8.43 ms,本文方法計算效率為BST算法的14.79倍。針對包含支路73條,節(jié)點69個的PG & E69節(jié)點電力系統(tǒng)圖,本文方法的平均計算時間為1.46 ms,文獻[2]中的BST算法平均計算時間為34.90 ms,本文方法計算效率為BST算法的23.90倍。且隨著圖的規(guī)模增加,優(yōu)勢愈發(fā)明顯。

      4 結(jié) 論

      本文對復(fù)雜連通圖中得到生成樹的算法進行了研究。將復(fù)雜圖按照簡化規(guī)則簡化后得到簡化圖。在簡化圖的基礎(chǔ)上,利用提出的生成樹算法得到對應(yīng)的生成樹圖,進而生成復(fù)雜圖對應(yīng)的生成樹圖。算例表明,方法具有以下特點:

      (1)該方法可正確生成復(fù)雜連通圖對應(yīng)的簡化圖。

      (2)該方法針對簡化單圖后可正確地、快速地求其所有的對應(yīng)生成樹圖。

      (3)針對簡化圖對應(yīng)生成樹圖,可逆向使用簡化規(guī)則得到復(fù)雜圖對應(yīng)的所有生成樹圖。

      (4)該方法相比其他方法,能大幅度提高復(fù)雜圖對應(yīng)生成樹搜尋過程中的速度,且隨著連通圖規(guī)模的增大,該優(yōu)勢越發(fā)明顯。

      猜你喜歡
      支路定義節(jié)點
      CM節(jié)點控制在船舶上的應(yīng)用
      Analysis of the characteristics of electronic equipment usage distance for common users
      基于限流可行方案邊界集的最優(yōu)支路投切
      能源工程(2020年6期)2021-01-26 00:55:22
      基于AutoCAD的門窗節(jié)點圖快速構(gòu)建
      多支路兩跳PF協(xié)作系統(tǒng)的誤碼性能
      利用支路參數(shù)的狀態(tài)估計法辨識拓?fù)溴e誤
      成功的定義
      山東青年(2016年1期)2016-02-28 14:25:25
      抓住人才培養(yǎng)的關(guān)鍵節(jié)點
      多并聯(lián)支路型可控電抗器短路電抗對支路電抗和電流的影響
      修辭學(xué)的重大定義
      高邑县| 沛县| 伊川县| 祥云县| 凤翔县| 台江县| 广南县| 民乐县| 博野县| 巴楚县| 靖边县| 卢龙县| 剑河县| 东乌珠穆沁旗| 灌阳县| 临泽县| 桃园县| 竹北市| 海盐县| 扎囊县| 色达县| 同心县| 安达市| 南城县| 奉节县| 临西县| 富民县| 石家庄市| 仪征市| 东源县| 汉阴县| 文水县| 濉溪县| 烟台市| 县级市| 酒泉市| 渝北区| 顺昌县| 汶上县| 云南省| 莲花县|