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

【文章來源】：四川師范大學四川省

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

【學位級別】：碩士

【部分圖文】：

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

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

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


本文編號：3062099