[發明專利]一種求網絡最短路徑的商空間覆蓋模型及其構建方法

無效

• 申請號: 200810021101.1
• 申請日: 2008-07-24
• 公開（公告）號: CN101330417A
• 公開（公告）日: 2008-12-24
• 發明（設計）人: 張鈴;張燕平;何富貴;趙姝
• 申請（專利權）人: 安徽大學
• 主分類號: H04L12/28
• 分類號: H04L12/28;H04L12/56;G06F17/50
• 代理公司: 安徽省合肥新安專利代理有限責任公司
• 代理人: 汪祥虬

技術領域

本發明屬于網絡拓撲技術領域，具體涉及一種無向無權網絡的商空間覆蓋模型和采用商空間粒度計算分類和分層遞階構建網絡拓撲商空間覆蓋模型的方法，該模型可用于網絡最短路徑的求解。

背景技術

對于求解網絡拓撲的最短路徑問題，其典型的算法是迪杰斯特拉(Dijkstra)算法和弗洛伊德(Floyd)算法，Dijkstra算法適合于求解單源點最短路徑問題，Floyd算法在求解所有點之間的最短路徑效果比較好，但這兩種方法，對于最短路徑搜索問題都屬于試探型搜索算法，其搜索過程沒有給定搜索目標和方向。

在互聯(Internet)網技術中，網絡路由器的選擇問題上目前還是以Dijkstra算法來選擇最短路徑。在交通網絡中，特別是數字化交通地圖中為了使用戶能在任意的起點和終點中找出最短線路，其系統的功能實現上最主要的是最短路徑算法的設計，目前還是以Dijkstra算法為主。在電力網絡中為了快速故障路徑檢測和路徑選擇中至今還是運用試探型搜索算法來求解最短路徑的思想來解決問題。對于大型的網絡來說，這些試探型搜索算法計算量大的算法影響在實際環境下的應用效果。

據《問題求解理論及應用-商空間粒度計算理論及應用》(第2版)(清華大學出版社，張鈴、張鈸著，2007年3月第2版，第1-6，12-14，27-36，38-39，90-105頁)介紹，商空間理論的粒度思想，模仿了人類采用概略地、由粗到細、不斷求精的多粒度分析法。對于最短路徑搜索問題的粒度分析法還只是數學領域上的一般形式，尚未涉及具體的分類算法。

專利申請號為20071013393.x的《一種復雜網絡商空間模型的構建方法》就可抽象為無向加權網絡的實際對象，根據網絡中邊上權值的不同利用等價關系對節點粒度分類，形成一系列不同權值上的網絡，把這些不同粒度上的網絡看成是初始網絡的商空間網絡，按照邊上權值由大到小排序商空間網絡形成一個遞階商空間鏈。這種復雜網絡商空間模型挖掘出了網絡中隱藏的信息，為復雜對象的最佳路徑問題求解提供了方便。專利申請號為20071013394.4的《一種基于復雜網絡商空間模型的路徑搜索方法》根據復雜網絡商空間模型提出了一種快速最佳路徑搜索方法。但這兩個發明申請是就可抽象為無向加權網絡的實際對象的最佳路徑問題來討論的，而可抽象為無向無權網絡的實際對象，因為其結構特點是相容關系的特征，無法根據等價關系來構建模型。

據《離散數學》(第2版)(國防工業出版社，于筑國編著，2007年11月，第115-117頁)中的相容關系，也只是定義了相容關系和覆蓋，闡述了相容關系和完全覆蓋的一一對應關系，但沒有將相容關系、完全覆蓋應用到最短路徑的搜索問題上，其中相容關系中的完全覆蓋即為網絡拓撲中的所有極大完全子圖集合。

發明內容

本發明目的是提出一種無向無權網絡的商空間覆蓋模型及其構建方法，以解決無向無權網絡中的最短路徑快速搜索問題，找出網絡中任意兩節點的最短路徑。

本發明的商空間覆蓋模型的構建方法，根據無向無權網絡中網絡拓撲結構的網絡中極大完全子圖，對節點粒度分類建立層次網絡模型；其特征在于：對于無向無權連通網絡從作為粒度最細、第0級商空間覆蓋網絡的初始網絡開始，搜索網絡中所有的極大完全子圖，以極大完全子圖為節點，兩極大完全子圖的節點間有公共節點或邊，定義兩節點相連，得到粒度較粗的商空間覆蓋，為初始網絡的一級商空間覆蓋網絡；然后再求初始網絡的一級商空間覆蓋網絡的所有極大完全子圖，并記錄極大完全子圖對應于初始網絡中的節點信息，以該級的極大完全子圖為節點，兩極大完全子圖的節點間有公共節點或邊，定義兩節點相連，得到粒度較粗的商空間覆蓋，構成初始網絡的二級商空間覆蓋網絡，求初始網絡的二級商空間覆蓋網絡的所有極大完全子圖，并記錄該級的極大完全子圖對應于初始網絡中的節點信息；繼續依此操作直至在商空間覆蓋網絡的極大完全子圖對應于初始網絡的節點信息中初始網絡的任意兩節點對都在同一個極大完全子圖中；各商空間覆蓋網絡按構成先后順序排列形成一個遞階商空間覆蓋網絡鏈；按遞階商空間覆蓋網絡鏈的順序，記錄各個商空間覆蓋網絡的所有極大完全子圖和各個極大完全子圖對應于初始網絡的節點信息為商空間覆蓋模型；對于無向無權的不連通網絡，先求出各個連通分支，對于每個連通分支，用無向無權連通網絡的方式來求解連通分支的商空間覆蓋模型。

本發明的商空間覆蓋模型的構建可具體操作如下：

先針對具體網絡拓撲依據商空間理論給出具體組成元素的表達形式：