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

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

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

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

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

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