最短路徑算法問(wèn)題.doc
約31頁(yè)DOC格式手機(jī)打開(kāi)展開(kāi)
最短路徑算法問(wèn)題,頁(yè)數(shù) 31 字?jǐn)?shù)11419摘要是計(jì)算機(jī)科學(xué)、運(yùn)籌學(xué)、地理信息系統(tǒng)和交通誘導(dǎo)、導(dǎo)航系統(tǒng)等領(lǐng)域研究的一個(gè)熱點(diǎn)。傳統(tǒng)的最短路徑算法主要有floyd算法和dijkstra算法。floyd算法用于計(jì)算所有節(jié)點(diǎn)之間的最短路徑。dijkstra算法則用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。dijks...


內(nèi)容介紹
此文檔由會(huì)員 倫月 發(fā)布
最短路徑算法問(wèn)題
頁(yè)數(shù) 31 字?jǐn)?shù) 11419
摘 要
最短路徑算法問(wèn)題是計(jì)算機(jī)科學(xué)、運(yùn)籌學(xué)、地理信息系統(tǒng)和交通誘導(dǎo)、導(dǎo)航系統(tǒng)等領(lǐng)域研究的一個(gè)熱點(diǎn)。傳統(tǒng)的最短路徑算法主要有Floyd算法和Dijkstra算法。Floyd算法用于計(jì)算所有節(jié)點(diǎn)之間的最短路徑。Dijkstra算法則用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。Dijkstra算法是已經(jīng)證明的能得出最短路徑的最優(yōu)解,但它的效率是一個(gè)很大的問(wèn)題。對(duì)于具有n個(gè)節(jié)點(diǎn)的一個(gè)圖,計(jì)算一個(gè)節(jié)點(diǎn)到圖中其余節(jié)點(diǎn)最短路徑的算法時(shí)間復(fù)雜度為O(n2)。對(duì)于一座大中型城市,地理節(jié)點(diǎn)數(shù)目可能達(dá)到幾萬(wàn)個(gè)到幾十萬(wàn)個(gè),計(jì)算最短路徑的時(shí)間開(kāi)銷(xiāo)將是非常巨大的。
本文根據(jù)吳一民老師的建議,分析當(dāng)前存在的各種求最短路徑的算法,提出一種新的基于層次圖的最短路徑算法,即將一個(gè)平面圖劃分若干子圖,子圖抽象為一個(gè)高層圖。最短路徑的計(jì)算首先在高層圖中進(jìn)行,縮小了最短路徑的查找范圍,降低了最短路徑計(jì)算的時(shí)間開(kāi)銷(xiāo)。由于可以動(dòng)態(tài)計(jì)算子圖間的阻抗函數(shù),算法可適用于動(dòng)態(tài)交通誘導(dǎo)系統(tǒng)。
關(guān)鍵詞 最短路徑,層次圖模型,Dijkstra算法
ABSTRACT
This paper discusses a new algorithm for the shortest path founding based on hierarchical graphs. It plots out a flat graph into some sub-graphs, which are abstracted as a high-level graph. The calculation for the shortest path founding begins at the high-level graph. This method shrinks the searching range of the shortest path and reduces the time spending of calculating it. Since the impedance function among sub-graphs can be calculated dynamically, this algorithm can be applied to dynamic traffic inducement system.
Index Terms: shortest path, hierarchical graph, Dijkstra algorithm
頁(yè)數(shù) 31 字?jǐn)?shù) 11419
摘 要
最短路徑算法問(wèn)題是計(jì)算機(jī)科學(xué)、運(yùn)籌學(xué)、地理信息系統(tǒng)和交通誘導(dǎo)、導(dǎo)航系統(tǒng)等領(lǐng)域研究的一個(gè)熱點(diǎn)。傳統(tǒng)的最短路徑算法主要有Floyd算法和Dijkstra算法。Floyd算法用于計(jì)算所有節(jié)點(diǎn)之間的最短路徑。Dijkstra算法則用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。Dijkstra算法是已經(jīng)證明的能得出最短路徑的最優(yōu)解,但它的效率是一個(gè)很大的問(wèn)題。對(duì)于具有n個(gè)節(jié)點(diǎn)的一個(gè)圖,計(jì)算一個(gè)節(jié)點(diǎn)到圖中其余節(jié)點(diǎn)最短路徑的算法時(shí)間復(fù)雜度為O(n2)。對(duì)于一座大中型城市,地理節(jié)點(diǎn)數(shù)目可能達(dá)到幾萬(wàn)個(gè)到幾十萬(wàn)個(gè),計(jì)算最短路徑的時(shí)間開(kāi)銷(xiāo)將是非常巨大的。
本文根據(jù)吳一民老師的建議,分析當(dāng)前存在的各種求最短路徑的算法,提出一種新的基于層次圖的最短路徑算法,即將一個(gè)平面圖劃分若干子圖,子圖抽象為一個(gè)高層圖。最短路徑的計(jì)算首先在高層圖中進(jìn)行,縮小了最短路徑的查找范圍,降低了最短路徑計(jì)算的時(shí)間開(kāi)銷(xiāo)。由于可以動(dòng)態(tài)計(jì)算子圖間的阻抗函數(shù),算法可適用于動(dòng)態(tài)交通誘導(dǎo)系統(tǒng)。
關(guān)鍵詞 最短路徑,層次圖模型,Dijkstra算法
ABSTRACT
This paper discusses a new algorithm for the shortest path founding based on hierarchical graphs. It plots out a flat graph into some sub-graphs, which are abstracted as a high-level graph. The calculation for the shortest path founding begins at the high-level graph. This method shrinks the searching range of the shortest path and reduces the time spending of calculating it. Since the impedance function among sub-graphs can be calculated dynamically, this algorithm can be applied to dynamic traffic inducement system.
Index Terms: shortest path, hierarchical graph, Dijkstra algorithm
TA們正在看...
- 宿遷市商業(yè)發(fā)展項(xiàng)目定位研究報(bào)告.doc
- 江蘇蘇州地區(qū)專(zhuān)業(yè)市場(chǎng)調(diào)研分析報(bào)告.doc
- 即墨房地產(chǎn)市場(chǎng)調(diào)查報(bào)告.doc
- 靜安區(qū)南京西路商業(yè)環(huán)境分析調(diào)查.doc
- 和記國(guó)際商業(yè)地產(chǎn)估價(jià)報(bào)告.doc
- ××城現(xiàn)售房屋客戶(hù)群分析及客戶(hù)定位.doc
- 重慶北碚區(qū)房地產(chǎn)市場(chǎng)研究.ppt
- 開(kāi)封瑞安嘉禾廣場(chǎng)市場(chǎng)調(diào)研報(bào)告.doc
- 經(jīng)濟(jì)危機(jī)下中國(guó)消費(fèi)者行為調(diào)查報(bào)告.pdf
- 打井施工組織設(shè)計(jì).doc