[發明專利]一種基于商空間覆蓋模型的最短路徑搜索方法

無效

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

技術領域

本發明屬于網絡拓撲技術領域，具體涉及一種無向無權網絡最短路徑搜索方法，特別是基于商空間覆蓋模型的路徑搜索方法。?

背景技術

對于求解網絡拓撲的最短路徑問題，典型的算法是迪杰斯特拉(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頁)中的相容關系，也只是定義了相容關系和覆蓋，闡述了相容關系和完全覆蓋的一一對應關系，但沒有將相容關系、完全覆蓋應用到最短路徑的搜索問題上，其中相容關系中的完全覆蓋即為網絡拓撲中的極大完全子圖。?

至今對于大規模復雜網絡的最短路徑搜索方法還是經典的Dijkstra算法和Floyd算法，未見將商空間理論和粒度計算應用到網絡最短路徑搜索問題上。

發明內容

本發明目的是提出一種基于商空間覆蓋模型的最短路徑搜索方法，以解決無向無權網絡中最短路徑的快速搜索問題。?

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