K最短路徑算法及其應(yīng)用研究.pdf

1、經(jīng)典的網(wǎng)絡(luò)最短路徑(Shortest Path,SP)問題解決靜態(tài)、確定網(wǎng)絡(luò)中單源最短路徑或所有頂點對間的最短路徑問題,這種狹義的SP方法具有很大的應(yīng)用局限性。K最短路徑問題(KSP)作為 SP問題的擴(kuò)展,在實際優(yōu)化決策中期望得到一個按最優(yōu)、次優(yōu)、再次優(yōu)等順序排列的決策集合,其在物流、序列比對、網(wǎng)絡(luò)和文本處理等領(lǐng)域有著非常廣泛的應(yīng)用。因此,快速的KSP算法研究無疑更適應(yīng)實際問題的解決且意義重大。目前,廣泛的應(yīng)用需求推動了KSP問題的研究

2、,并使其再次成為近年來國際上的研究熱點,但相比解決經(jīng)典SP問題的算法,KSP研究的突出成果并不多見。
　　本文針對K最短路徑問題算法,結(jié)合已有研究成果做了較為深入的研究,取得如下成果:
　　1、提出了基于啟發(fā)式搜索的無約束圖中Single-pair KSP快速算法:啟發(fā)式搜索基于每一個狀態(tài)空間中搜索的位置進(jìn)行評估,進(jìn)而得到最好的位置,再從當(dāng)前最好位置進(jìn)行搜索直到目標(biāo)節(jié)點。這種策略可以避免大量無謂的搜索路徑,提高算法效率。本文

3、運用啟發(fā)式搜索策略,并使用o n-the-fly sear c h技術(shù)解決K最短路徑問題,提出一種在K比較小的時候的高效率算法。實驗證明,該算法在當(dāng)K很小的時候比現(xiàn)有的算法效率高。
　　2、研究脈沖耦合神經(jīng)網(wǎng)絡(luò)模型改進(jìn)及其在KSP問題當(dāng)中的應(yīng)用:脈沖耦合神經(jīng)網(wǎng)絡(luò)是一種基于貓的視覺皮層建模提出的神經(jīng)網(wǎng)絡(luò)模型,具有強(qiáng)大的計算和模擬能力。本文提出了一種改進(jìn)的脈沖耦合神經(jīng)網(wǎng)絡(luò)模型,并對模型參數(shù)調(diào)整做了詳細(xì)探討。結(jié)合single-pair

4、KSP和single-source KSP問題研究提出了相應(yīng)的實現(xiàn)算法。同時,結(jié)合當(dāng)前常用的地圖路徑搜索應(yīng)用進(jìn)行了對比仿真。實驗表明,由于PCNN的并行計算特征,使得KSP問題的計算速度大大提高。
　　3、提出了一種基于波傳遞思想的KSP算法:考慮到水流動的自然特性與路徑之間的關(guān)系,當(dāng)波傳遞的速度一定時,其傳遞時間與其經(jīng)過的路徑長度成正比。由于波傳遞與具體節(jié)點的無關(guān)性,可將該思想用于解決針對從一個節(jié)點到其他所有節(jié)點的K最短路徑問題