[發明專利]一種新型便捷隨機生成樹組求取算法

在審

• 申請號: 202111485033.6
• 申請日: 2021-12-07
• 公開（公告）號: CN114357353A
• 公開（公告）日: 2022-04-15
• 發明（設計）人: 董張卓;羅輝;齊洋
• 申請（專利權）人: 西安石油大學
• 主分類號: G06F17/10
• 分類號: G06F17/10
• 代理公司: 西安國兆智匯知識產權代理事務所(普通合伙) 61269
• 代理人: 董江華

1.一種新型便捷隨機生成樹組求取算法，其特征在于，包括如下步驟：

步驟1：定義大規模復雜連通圖G_F＝B_F，N_F，其中B_F為支路集合，N_F為節點集合；

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

步驟2：將連通圖G_F中不涉及環路的輻射支路、節點以及直接串聯的支路進行化簡；為此給出以下概念的定義：

輻射通路：不包含在任何環路中的通路；

互斥支路：由度為2的節點連接的兩條支路；

互斥支路集：支路集合{b_i|i＝1,2…n_b}，若b_i和b_i+1互斥，且b_i+1和b_i+2互斥，i＝1,2…n_b-2，則集合為互斥支路集；

輻射通路不存在于任何環路中，所以不參與生成樹的生成過程；同時由互斥支路知，互斥支路集在求取開環圖時最多只需打開一條支路；因此，將互斥支路進行合并；給出連通圖G_F簡化規則；

步驟3：連通圖G_F經過簡化后得到的簡化圖G：

G＝B，N (1)

其中：B為簡化圖中的支路集合，B＝{b_i|i＝1,2…n_b}，b_i為簡化圖G中支路的編號，n_b為簡化圖G中支路個數，N為簡化圖G中的節點集合，N＝{n_i|i＝1,2…n_n}，n_i為簡化圖G中節點的編號，n_n為簡化圖G中節點個數；

簡化圖G的生成樹定義為含有簡化圖G所有節點連通的無環路的一個子圖，即生成樹圖G_T：

G_T＝B_T，N_T (2)

其中：B_T為生成樹圖G_T中的支路集合，B_T＝{b_Ti|i＝1,2…n_Tb}，b_Ti為生成樹圖G_T支路的編號，n_Tb為生成樹圖G_T中支路個數；N_T為生成樹圖G_T中的節點集合N_T＝{n_Ti|i＝1,2…n_Tn}，n_Ti為生成樹圖G_T節點的編號，n_Tn為生成樹圖G_T節點個數；

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

G_B＝B_B，N_B (3)

其中：B_B為過渡圖G_B中的支路集合；N_B為過渡圖G_B中的節點集合；

步驟4：將一顆隨機生成樹的計算過程分為三個部分:初始化部分、支路遷移循環部分、線索支路搜索部分；

在每次計算得到一顆新的生成樹G_B后，對簡化圖G中對應新生成樹G_B樹支的支路在生成樹組中作為樹支的次數i_{Noc_T}以及生成樹的總數i_{Tn_T}進行更新，并在下一次生成樹的計算過程中以簡化圖G支路未選中生成樹支的概率P_{n_t}為基準，采用輪盤賭的方式對當前節點的待選支路集中的支路進行選擇；

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