資源描述：
《并行k最短路徑搜索算法研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、分類號(hào):U49110710-2012124019碩士學(xué)位論文并行K最短路徑搜索算法研究李瑩導(dǎo)師姓名職稱段宗濤教授申請(qǐng)學(xué)位級(jí)別工學(xué)碩士學(xué)科專業(yè)名稱信息與通信工程論文提交日期2015年5月26日論文答辯日期2015年6月6日學(xué)位授予單位長(zhǎng)安大學(xué)ResearchonParallelKShortestPathsSearchAlgorithmAThesisSubmittedfortheDegreeofMasterCandidate：LiYingSupervisor：Prof.DuanZongtaoChang’anUniversity,Xi’an,China論文獨(dú)創(chuàng)性聲明本人聲明：本人所呈交的
2、學(xué)位論文是在導(dǎo)師的指導(dǎo)下，獨(dú)立進(jìn)行研究工作所取得的成果。除論文中已經(jīng)注明引用的內(nèi)容外，對(duì)論文的研究做出重要貢獻(xiàn)的個(gè)人和集體，均己在文中以明確方式標(biāo)明。本論文中不包含任何未加明確注明的其他個(gè)人或集體已經(jīng)公開發(fā)表的成果。本聲明的法律責(zé)任由本人承擔(dān)。論文作者簽名：香f?7WS年《月0曰論文知識(shí)產(chǎn)權(quán)權(quán)屬聲明本人在導(dǎo)師指導(dǎo)下所完成的論文及相關(guān)的職務(wù)作品，知識(shí)產(chǎn)權(quán)歸屬學(xué)校。學(xué)校享有以任何方式發(fā)表、復(fù)制、公開閱覽、借閱以及申請(qǐng)專利等權(quán)利。本人離校后發(fā)表或使用學(xué)位論文或與該論文直接相關(guān)的學(xué)術(shù)論文或成果時(shí)，署名單位仍然為長(zhǎng)安大學(xué)。(保密的論文在解密后應(yīng)遵守此規(guī)定）論文作者簽名：Ii>/!：年（月/陽(yáng)
3、導(dǎo)師簽名：備年Z月/D曰摘要最短路徑搜索不僅在城市交通路網(wǎng)規(guī)劃和人工智能等領(lǐng)域被廣泛應(yīng)用，而且是現(xiàn)階段智能交通行業(yè)研究的焦點(diǎn)。城市的發(fā)展使得城市規(guī)模不斷擴(kuò)大，城市路網(wǎng)變得越來越復(fù)雜，路網(wǎng)節(jié)點(diǎn)數(shù)目也迅速增加，從時(shí)間代價(jià)和計(jì)算量等多方面因素考慮，傳統(tǒng)串行算法無法達(dá)到期望的求解結(jié)果。因此，伴隨著并行技術(shù)發(fā)展，并行算法出現(xiàn)能夠有效減少最短路徑搜索時(shí)間，方便我們?cè)诖笠?guī)模路網(wǎng)中求解最短路徑。一般求解最短路徑的算法存在一些問題，例如，采用Dijkstra算法在大規(guī)模城市交通路網(wǎng)中搜索最短路徑，面對(duì)用戶并發(fā)的出行請(qǐng)求，容易造成交通擁堵，降低了城市交通的運(yùn)行效率。K最短路徑(KShortestPat
4、hs，KSP)算法是路徑搜索算法的另一個(gè)應(yīng)用形式，區(qū)別于其他算法的是它可以搜索出路網(wǎng)中兩點(diǎn)間的最短路徑集合，能夠盡可能的滿足出行者的需求。實(shí)際中，路網(wǎng)規(guī)模越復(fù)雜，KSP算法需要計(jì)算的數(shù)據(jù)量就越大，占2用計(jì)算機(jī)存儲(chǔ)空間也就越多。文中提到的KSP算法具有O(n+n+m)的時(shí)間復(fù)雜度，程序執(zhí)行消耗時(shí)間較長(zhǎng)，導(dǎo)致算法效率和實(shí)時(shí)性不高。本文從最短路徑問題入手，結(jié)合城市路網(wǎng)交通流狀況，分析了城市交通網(wǎng)絡(luò)中最短路徑算法發(fā)展現(xiàn)狀，重點(diǎn)描述了KSP算法。針對(duì)傳統(tǒng)算法存在的問題，本文提出將KSP算法并行化的思想來搜索最短路徑。首先，分析城市道路網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，根據(jù)路網(wǎng)的網(wǎng)絡(luò)結(jié)構(gòu)特點(diǎn)，確定網(wǎng)絡(luò)分解的基本
5、要求、網(wǎng)絡(luò)劃分方法以及交通網(wǎng)絡(luò)分割算法。其次，本文以方格式路網(wǎng)模型為基礎(chǔ)進(jìn)行研究，按照網(wǎng)絡(luò)分割原則劃分網(wǎng)絡(luò)，選擇路徑的源點(diǎn)和終點(diǎn)，運(yùn)用并行K最短路徑(ParallelKShortestPaths，PKSP)算法搜索路徑，能夠得到一個(gè)最短路徑集合。最后，對(duì)PKSP算法的指標(biāo)體系進(jìn)行了評(píng)估，運(yùn)用PKSP算法既降低了搜索路徑的時(shí)間，提高了算法的搜索效率，又能獲得較好的加速比。同時(shí)，將PKSP算法在城市路網(wǎng)交通流分配方面做了應(yīng)用，結(jié)果證明：在大規(guī)模路網(wǎng)中，如果同時(shí)出現(xiàn)多個(gè)出行請(qǐng)求，PKSP算法能夠搜索出多條符合K最短路徑集合選擇要求的最短路徑，擴(kuò)大了路段交通流的分布范圍，降低了發(fā)生交通堵塞
6、的頻率。關(guān)鍵詞：智能交通，路徑搜索，并行技術(shù)，K最短路徑算法iAbstractShortestpathsearchingiswidelyusedinthefieldofurbantrafficnetworkplanningandartificialintelligence,whichisthefocusoftheresearchofintelligenttransportationindustryatpresentstage.Thedevelopmentofthecitymakesthecityscaleexpandsunceasingly,theurbanroadnetworkh
7、asbecamemoreandmorecomplex,thenumberofnetworknodesisalsoincreasingrapidly.Consideringtimecost,calculationandotherfactors,thetraditionalserialalgorithmcan’tobtaintheexpectedresults.Withthedevelopmentofparalleltechnology,theparallelalgori
