商空間理論在網絡路徑分析中研究.pdf

1、粒計算理論之一——商空間理論，是張鈴、張鈸教授模擬人類智能解決問題思路而提出的人工智能求解問題的計算模型。商空間理論通過論域、屬性和結構三元組(x，f，T)來描述問題，通過取不同粒，從而建立不同粒度的商空間，形成的一套問題求解的數(shù)學模型。其特色是用結構將論域中元素間的聯(lián)系進行了清晰描述，將論域中的復雜問題轉化到不同粒度世界上進行分析，在不同粒度世界之間進行求解，對不同粒度上的解進行合成得到原問題的解，以達到降低問題復雜度的效果。商空間理

2、論作為粒計算的理論方法主要討論的問題：(1)如何選擇合適的粒——投影問題？(2)如何在不同的粒上進行問題求解——推理問題？(3)如何實現(xiàn)不同粒度空間上的解轉化到原問題的解——粒度合成問題？
　　 商空間理論給出了兩個標志性的原理：保假原理和保真原理，保障了問題(2)和(3)，對于問題(1)只能在實際應用中具體問題需要具體對待。對于網絡路徑問題，是圖論、人工智能領域的經典問題，其網絡的規(guī)模決定了其問題的復雜度，也是路徑算法的“瓶頸

3、”，近年不少學者通過不同方式分解網絡規(guī)模來降低計算復雜度，實現(xiàn)網絡路徑搜索。本文針對網絡路徑問題應用商空間理論，應用粒度分解方法將網絡路徑問題分解到不同粒度商空間中，從不同粒度空間形成的分層遞階商空間鏈中獲取網絡路徑的解。對于網絡路徑分析，針對不同類型的網絡討論粒的選取問題，提出其路徑算法，為網絡路徑分析提供一個商空間理論問題求解模型。
　　 本文的主要工怍包括：
　　 1．研究商空間理論中粒的選取。
　　 在商

4、空間理論中，其取粒度方式有根據(jù)論域、屬性或結構進行劃分三種方法來形成商空間。商空間理論區(qū)別于其他粒計算理論，引入了結構作為研究對象的拓撲信息。本文討論網絡結構中的粒的選取問題，針對不同基本類型的網絡（無權網絡、加權網絡、有向網絡）的粒的選取進行了討論。
　　 2．提出加權網絡的最佳路徑。
　　 針對加權網絡的結構類型的路徑問題，根據(jù)邊權的不同構建等價關系，作為基本粒，將加權網絡粒度分解到不同邊權上的商空間上，形成分層遞階

5、商空間鏈，并基于分層遞階商空間鏈提出加權網絡的最佳路徑搜索算法。最佳路徑通過局部最優(yōu)實現(xiàn)全局最優(yōu)，逼近最短路徑。通過模擬數(shù)據(jù)實驗驗證其最佳路經逼近最短路徑，并就成都市交通網絡的行車路線對最佳路徑和最短路徑進行了比較，體現(xiàn)出最佳路徑的特色。
　　 3．提出基于商空間理論的最短路徑方法
　　 針對無向無權網絡，以極大完全子圖怍為基本粒，形成相容關系商空間，構造出分層遞階商空間，實現(xiàn)無向無權網絡的最短路徑搜索。由于極大完全子圖

6、的求解具有高計算復雜度，不適合于大中型網絡的最短路徑求解。就一般網絡，基于經典的Dijkstra和Floyd算法改進，提出一種根據(jù)網絡最短路徑步數(shù)來求解網絡中所有最短路徑的方法。
　　 4．提出大規(guī)模網絡的社團最短路徑算法。
　　 針對大規(guī)模網絡的網絡分析，其網絡規(guī)模是圖論路經算法的瓶頸，本文提出以社團為基本粒的多粒度網絡分解方法，將大規(guī)模網絡粒化為分層遞階商空間，實現(xiàn)大規(guī)模網絡的預處理。利用分層遞階商空間中的數(shù)據(jù)信息來

7、計算啟發(fā)式路徑搜索方法的估計函數(shù)，以實現(xiàn)大規(guī)模網絡的點對點最短路徑搜索。
　　 就多粒度網絡分解中的大規(guī)模網絡分割問題，本文提出的方法是以模塊度作為評價準則，以節(jié)點網絡屬性作為啟發(fā)式信息對網絡進行分割，使得子圖規(guī)模相當且具有社團群聚特征。社團子圖規(guī)模相當使得經典的圖論算法（如最小生成樹算法）充分發(fā)揮其作用。
　　 通過美國不同規(guī)模的城市交通網絡的實驗，證實了以社團為基本粒的多粒度網絡分解方法的實用性，并就網絡點對點最短路