地下管網(wǎng)最短路徑的算法研究及實現(xiàn).pdf

1、隨著城市建設(shè)的飛速發(fā)展,城市原有的地下管網(wǎng)已經(jīng)遠(yuǎn)遠(yuǎn)滿足不了城市發(fā)展的需要,舊管網(wǎng)的更新、新管網(wǎng)的設(shè)計施工、新區(qū)的管網(wǎng)規(guī)劃都需要準(zhǔn)確掌握地下管網(wǎng)的現(xiàn)狀,而傳統(tǒng)采用圖紙、圖表等形式管理的管網(wǎng)中存在許多問題。而地理信息系統(tǒng)(Geographical Information System,簡稱GIS)是一種在計算機硬軟件支持下,以空間數(shù)據(jù)庫為基礎(chǔ),運用系統(tǒng)工程和信息科學(xué)的理論,對空間數(shù)據(jù)進(jìn)行科學(xué)管理和綜合分析,為規(guī)劃、決定、管理和研究提供信息的

2、技術(shù)系統(tǒng)。最短路徑算法作為該領(lǐng)域中選擇最優(yōu)問題的基礎(chǔ),在地下管網(wǎng)系統(tǒng)中占有重要地位。本文從地下管網(wǎng)管理和空間分析的現(xiàn)狀和實際需求出發(fā),在實現(xiàn)了對地下管網(wǎng)的矢量地圖表達(dá)、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的提取和構(gòu)建的基礎(chǔ)上,針對地下管網(wǎng)“一到多”的特征,利用網(wǎng)絡(luò)通信中的多播思想,提出將多播路由算法應(yīng)用到地下管網(wǎng)空間分析中,從而達(dá)到使地下管網(wǎng)的某些代價如管網(wǎng)路徑長度、投資費用等最小的目的,即解決地下管網(wǎng)的最小生成樹問題。主要工作包括：
　　 ⑴概述GI

3、S的發(fā)展與應(yīng)用中的問題,指出網(wǎng)管規(guī)劃過程面臨的挑戰(zhàn)和處理策略。分析地下管網(wǎng)的特點,對基于地下管網(wǎng)的最短路徑分析的各項關(guān)鍵技術(shù)進(jìn)行了深入的探討和研究。其中,重點研究了地下管網(wǎng)的矢量地圖表達(dá)、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的提取和構(gòu)建等關(guān)鍵技術(shù)。
　　 ⑵結(jié)合目前地下管網(wǎng)空間分析中最短路徑算法過于簡單和粗糙的現(xiàn)狀,提出將經(jīng)典的KPP多播路由算法應(yīng)用到地下管網(wǎng)的最短路徑分析當(dāng)中,并證明與傳統(tǒng)的Dijkstra算法和Froyd算法相比,KPP算法所產(chǎn)生的