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

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

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

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

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

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