[發明專利]基于時態圖代價最小生成樹的增量方法及系統在審
| 申請號： | 201911314540.6 | 申請日： | 2019-12-19 |
| 公開（公告）號： | CN111061964A | 公開（公告）日： | 2020-04-24 |
| 發明（設計）人： | 李文浩;葛又銘;劉玉葆 | 申請（專利權）人： | 中山大學 |
| 主分類號： | G06F16/9536 | 分類號： | G06F16/9536;G06Q50/00 |
| 代理公司： | 北京中濟緯天專利代理有限公司 11429 | 代理人： | 黃啟文 |
| 地址： | 510275 廣東*** | 國省代碼： | 廣東;44 |
| 權利要求書： | 查看更多 | 說明書： | 查看更多 |
| 摘要： | |||
| 搜索關鍵詞： | 基于 時態 代價 最小 生成 增量 方法 系統 | ||
1.基于時態圖代價最小生成樹的增量方法，其特征在于：包括以下內容：
設時態圖G＝(V，E)其受影響后的變化量為ΔG，其中V表示時態圖的節點集，E表示時態圖的邊集；
將節點集V劃分為受ΔG影響的終端節點集Xa和未受ΔG影響的終端節點集Xu；
對于終端節點集Xa，將G+ΔG轉換為靜態圖，在該靜態圖下，找尋從根節點r到Xa中所有節點的路徑，得到受影響子圖Gs；對受影響子圖Gs進行預處理，得到受影響子圖Gs的閉包；通過受影響子圖Gs的閉包計算覆蓋Xa的有向斯坦納樹Ta；
對于終端節點集Xu，從初始的有向斯坦納樹T中提取從根節點到終端節點集Xu中各個節點的路徑，組成未受影響終端節點的有向斯坦納樹Tu；
將Ta和Tu合并，得到覆蓋整個V集合的有向斯坦納樹new-T；
對合并得到的有向斯坦納樹new-T進行后處理操作，將其轉化為對應的代價最小生成樹MSTw。
2.根據權利要求1所述的基于時態圖代價最小生成樹的增量方法，其特征在于：所述受ΔG影響的終端節點集Xa的劃分方式如下：通過掃描ΔG，ΔG中所有邊的到達節點及其子孫節點組成的集合即為Xa。
3.一種時態圖代價最小生成樹的增量系統，其特征在于：包括終端節點集劃分模塊、有向斯坦納樹Ta計算模塊、有向斯坦納樹Tu計算模塊、有向斯坦納樹合并模塊和代價最小生成樹轉換模塊；
其中終端節點集劃分模塊用于將節點集V劃分為受ΔG影響的終端節點集Xa和未受ΔG影響的終端節點集Xu；
有向斯坦納樹Ta計算模塊用于將G+ΔG轉換為靜態圖，在該靜態圖下，找尋從根節點r到Xa中所有節點的路徑，得到受影響子圖Gs；對受影響子圖Gs進行預處理，得到受影響子圖Gs的閉包；通過受影響子圖Gs的閉包計算覆蓋Xa的有向斯坦納樹Ta；
有向斯坦納樹Tu計算模塊用于從初始的有向斯坦納樹T中提取從根節點到終端節點集Xu中各個節點的路徑，組成未受影響終端節點的有向斯坦納樹Tu；
有向斯坦納樹合并模塊用于將Ta和Tu合并，得到覆蓋整個V集合的有向斯坦納樹new-T；
代價最小生成樹轉換模塊用于對合并得到的有向斯坦納樹new-T進行后處理操作，將其轉化為對應的代價最小生成樹MSTw。
該專利技術資料僅供研究查看技術是否侵權等信息，商用須獲得專利權人授權。該專利全部權利屬于中山大學，未經中山大學許可，擅自商用是侵權行為。如果您想購買此專利、獲得商業授權和技術合作，請聯系【客服】
本文鏈接：http://www.szxzyx.cn/pat/books/201911314540.6/1.html，轉載請聲明來源鉆瓜專利網。
