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

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

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

3、運(yùn)用啟發(fā)式搜索策略,并使用o n-the-fly sear c h技術(shù)解決K最短路徑問題,提出一種在K比較小的時(shí)候的高效率算法。實(shí)驗(yàn)證明,該算法在當(dāng)K很小的時(shí)候比現(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ì)算和模擬能力。本文提出了一種改進(jìn)的脈沖耦合神經(jīng)網(wǎng)絡(luò)模型,并對(duì)模型參數(shù)調(diào)整做了詳細(xì)探討。結(jié)合single-pair

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