隨著人口往城市的快速遷移,全球道路網(wǎng)的規(guī)模在不斷地?cái)U(kuò)大,高效、快速的從龐大的道路網(wǎng)數(shù)據(jù)中計(jì)算兩點(diǎn)之間的最短路徑,成為了學(xué)術(shù)界和工業(yè)界眾多研發(fā)人員的研究課題。經(jīng)過(guò)多年的研究,學(xué)者們已經(jīng)提出了諸多相關(guān)算法,例如Dijkstra算法、CH算法（Construction Hierarchies Algorithm）、Arc-Flag算法、Highway Hierarchies算法,以及一些結(jié)合智能算法的最短路徑算法。但是如何通過(guò)減少數(shù)據(jù)搜索空間,從而達(dá)到有效降低查詢時(shí)間這一問(wèn)題仍然未能得到良好的解決。本文針對(duì)從大規(guī)模道路網(wǎng)數(shù)據(jù)中查詢兩點(diǎn)之間最短路徑存在時(shí)間消耗較大的問(wèn)題,分析研究了實(shí)際道路之間的限制關(guān)系,提出了一種基于節(jié)點(diǎn)度的大規(guī)模道路網(wǎng)數(shù)據(jù)劃分方法,在此基礎(chǔ)上,給出有效可行的解決方案,同時(shí)也保證了算法的性能。論文的主要工作如下:（1）提出了一種基于節(jié)點(diǎn)度的道路劃分算法,以解決劃分道路網(wǎng)數(shù)據(jù)時(shí)容易將節(jié)點(diǎn)分布密集的區(qū)域劃分在不同的子網(wǎng)內(nèi)的問(wèn)題。首先,該算法根據(jù)實(shí)際道路之間的限制關(guān)系處理并存儲(chǔ)道路網(wǎng)數(shù)據(jù);其次,設(shè)置劃分后的子網(wǎng)內(nèi)最大節(jié)點(diǎn)數(shù)量,然后利用Kd-tree劃分道路網(wǎng)數(shù)據(jù),并標(biāo)記劃分后的子網(wǎng)... 

【文章來(lái)源】：四川師范大學(xué)四川省

【文章頁(yè)數(shù)】：73 頁(yè)

【學(xué)位級(jí)別】：碩士

【部分圖文】：

網(wǎng)格劃分德克薩斯州的道路網(wǎng)

圖 2.5 Quad-tree 劃分德克薩斯州道路網(wǎng)-dimensional tree)劃分算法是一種根據(jù)圖中節(jié)點(diǎn)在多的算法，其主要思想是：K-D 樹(shù)每一個(gè)非葉子節(jié)點(diǎn)都

Kd-tree劃分德克薩斯州道路網(wǎng)


本文編號(hào)：3062099