商空間理論在網(wǎng)絡(luò)路徑分析中研究.pdf

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

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

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

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

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

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

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