商空間理論逼近最短路徑搜索的研究.pdf

1、人類前進的步伐逐漸加快，無處不在的網(wǎng)絡(luò)規(guī)模逐漸增大，作為圖論中最基本的問題之一的最短路徑搜索也隨之面臨挑戰(zhàn)：在大規(guī)模網(wǎng)絡(luò)中，經(jīng)典求解算法的復(fù)雜度太高。因此，針對大規(guī)模網(wǎng)絡(luò)的最短路徑求解問題，本文結(jié)合了商空間理論的粒度分層思想，給出了分層求解算法，在不同粒度空間上跳轉(zhuǎn)的過程中，求解最短路徑問題。
　　 商空間理論模型是張鈴教授和張鈸院士在對人類思考問題的方式進行深入剖析之后提出的。該理論在表示問題時用的是一個三元組(X，f，T)，

2、再通過粒度的轉(zhuǎn)換，將問題轉(zhuǎn)換成新的三元組([X]，[f]，[T])表示的問題。在不同的粒度空間跳轉(zhuǎn)，將原有問題簡化，解答，最終構(gòu)造出原粒度空間下的問題的解。這種問題求解的思想正是基于人類的思維方式--可以在觀察和分析問題時，對問題構(gòu)造出極不相同的粒度空間，而且往返自如。
　　 劃分原粒度空間下的大型網(wǎng)絡(luò)成若干個子網(wǎng)絡(luò)，再將這些個子網(wǎng)絡(luò)映射到較粗粒度空間下的新網(wǎng)絡(luò)中，經(jīng)過這個映射過程，網(wǎng)絡(luò)的規(guī)模得以大大縮小。新網(wǎng)絡(luò)和原網(wǎng)絡(luò)構(gòu)成了不

3、同層次上的網(wǎng)絡(luò)。在對原問題進行粒度粗化，以及對在新網(wǎng)絡(luò)中求得的解細化到原空間的過程中，實現(xiàn)了不同粒度空間之間的跳轉(zhuǎn)?；谏炭臻g理論的兩大基本原理，本文的最短路徑求解算法解決了傳統(tǒng)算法復(fù)雜度過高的問題。
　　 本文的主要工作為：
　　 1.研究不同類型網(wǎng)絡(luò)的社團劃分方法。
　　 在無權(quán)網(wǎng)絡(luò)和加權(quán)網(wǎng)絡(luò)兩種情況中，結(jié)合Newman等人給出的不同模塊度函數(shù)，以模塊度函數(shù)作為劃分依據(jù)，將規(guī)模較大的網(wǎng)絡(luò)劃分成相對規(guī)模較小的網(wǎng)

4、絡(luò)。這一劃分標準在現(xiàn)今的網(wǎng)絡(luò)劃分算法的研究中，是受到廣泛認可的，并被用于驗證新算法是否具有有效性。
　　 2.在網(wǎng)絡(luò)劃分的基礎(chǔ)上，構(gòu)造不同粒度空間下的層次網(wǎng)絡(luò)。
　　 對劃分得到的若干個子網(wǎng)絡(luò)，分別用新的節(jié)點代替，即在粒度選擇中以是否處于同一社團為等價關(guān)系；根據(jù)原網(wǎng)絡(luò)中各社團之間的邊連接情況，保持原有的連通關(guān)系，構(gòu)造出粗粒度空間下的網(wǎng)絡(luò)，這一新網(wǎng)絡(luò)所處的層次相對較高。
　　 3.在不同的粒度空間下的網(wǎng)絡(luò)間跳轉(zhuǎn)，實

5、現(xiàn)最短路徑的近似求解。
　　 原空間中的最短路徑問題，經(jīng)過網(wǎng)絡(luò)的抽象，轉(zhuǎn)換到在新網(wǎng)絡(luò)中求解，得到的解需要回歸到原網(wǎng)絡(luò)中。而最終解的構(gòu)造是在粒度空間的細化過程中給出的。這樣就實現(xiàn)了原問題的求解在不同粒度空間的跳轉(zhuǎn)。
　　 文章利用計算機生成的網(wǎng)絡(luò)中檢驗分層求解算法的有效性，基于這一基礎(chǔ)驗證，再進一步將此算法應(yīng)用到美國的三個不同規(guī)模州、區(qū)的城市交通網(wǎng)絡(luò)圖中，進行最短路徑的求解。該過程有效地解決了經(jīng)典算法不適用于大規(guī)模網(wǎng)絡(luò)的問