資源描述：
《基于_矩陣乘法_的網(wǎng)絡(luò)最短路徑算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、第7期電子學(xué)報Vol.37No.72009年7月ACTAELECTRONICASINICAJuly2009基于/矩陣乘法0的網(wǎng)絡(luò)最短路徑算法鄧方安,雍龍泉,周濤,劉麗華(陜西理工學(xué)院數(shù)學(xué)系,陜西漢中723001)摘要:網(wǎng)絡(luò)最短路徑問題可以作為許多實際應(yīng)用問題的模型,但傳統(tǒng)的求解算法其迭代過程復(fù)雜.本文描述了基于矩陣乘法的最短路算法,其時間復(fù)雜度與Dijkstra算法相同.在給定的一個網(wǎng)絡(luò)圖中,在不改變網(wǎng)絡(luò)圖中的最短路的條件下,刪除/多余0的結(jié)點或邊,可以達到簡化網(wǎng)絡(luò)圖和提高求解速度的目的,從而降低計算復(fù)雜性.最后,研究了該方法在最短路徑問題
2、和旅行商問題中的應(yīng)用.實例表明,這種算法與傳統(tǒng)的動態(tài)規(guī)劃技術(shù)相比,具有運算簡便、易于理解的優(yōu)點.關(guān)鍵詞:矩陣乘法;最短路問題;約簡原則;旅行商問題中圖分類號:TP30116文獻標識碼:A文章編號:0372-2112(2009)07-1594-05ShortestPathProblemAlgorithminNetworkBasedonMatrixMultiplicationDENGFang-an,YONGLong-quan,ZHOUTao,LIUL-ihua(DepartmentofMathematics,ShaanxiUniversityo
3、fTechnology,Hanzhong,Shaanxi723001,China)Abstract:ShortestPathProbleminnetworkcanbeactedasamodelformanyapplicationproblems,buttheiterationprocessoftheconventionalsolutionalgeorithmiscomplex.Inthispaper,theshortestpathalgorithmbasedonthematrixmultiplicationinaweighted-graph
4、aredescribed,anditstimecomplexityisassameasDijkstraalgorithm.Inagivennetworkgraph,thisalgorithmdeletesparenodesoredgesandreachthegoalthatreducednetworkgraphandimprovedspeedofsolvingproblemunderthecond-itionofunchangedshortestparth.Finally,wegiveexamples,e.g.TravelingSalesm
5、anProblem,shortestpathproblem,toillistrateitsadvanteges,possessingmeritsofsimpleoperationandeasyunderstanding,comparedwithdynamicprogrammingtechnology.Keywords:matrixmultiplication;shortestpathproblem;reducedprinciple;travelingsalesmanproblems出了時間依賴的網(wǎng)絡(luò)的定義和模型,給出一種實用反饋1引言式神經(jīng)
6、網(wǎng)絡(luò)來求解時間依賴的網(wǎng)絡(luò)的最短路徑問題.并日常生活和生產(chǎn)中許多問題都可以用一個網(wǎng)絡(luò)來用模擬實驗驗證了它在不同的網(wǎng)絡(luò)更新時間區(qū)間上收描述.例如,交通網(wǎng)絡(luò),計算機網(wǎng)絡(luò),工程進度網(wǎng)絡(luò),生物斂速度的穩(wěn)定性.結(jié)果是神經(jīng)網(wǎng)絡(luò)求解非NP-難解類優(yōu)[1~4]信息網(wǎng)絡(luò)和互聯(lián)網(wǎng)等.對于諸如最短路徑問題、最化問題的一種新嘗試.本文介紹了基于矩陣乘法運算的小費用問題,最大流問題等經(jīng)典網(wǎng)絡(luò)優(yōu)化問題的解決,最短路算法,并考慮了該算法的時間復(fù)雜度,研究了它[5]除了比較成熟的動態(tài)規(guī)劃技術(shù)外,一些新的進化算的應(yīng)用.法,包括蟻群算法、人工神經(jīng)網(wǎng)絡(luò)和遺傳算法被提[6,7]2算
7、法的描述出.傳統(tǒng)的Bellman動態(tài)優(yōu)化算法可以求解最短路問題,但這種算法需要很大的空間,最好和最壞的情況動態(tài)規(guī)劃是求解許多重要應(yīng)用問題的關(guān)鍵技術(shù),可下的時間差不多相同.雖然它在規(guī)模比較小的時候,可以高效地解決許多用貪心算法或分支定界方法無法解以很好的解決問題,但是,隨著問題規(guī)模的擴大,Bellman決的問題.但該方法比較抽象,難于理解.下面利用/矩動態(tài)優(yōu)化算法就顯得無能為力.文獻[8]擴展了線性代陣乘積0運算求解最短路問題.不難看出:新方法比動態(tài)數(shù)中的矩陣運算,定義了矩陣和與積的概念及運算,通規(guī)劃方法運算簡便,容易理解.過這種方法,可以把
8、求最短路轉(zhuǎn)化為矩陣的運算,計算例1圖1表示從起點A到終點E之間各點的距簡便、有效.文獻[10]用實例證明了著名的Dijkstra算法離,求A到E的最短路徑.在時間依賴的網(wǎng)絡(luò)上不能
