路徑規(guī)劃技術(shù)在導(dǎo)游軟件中的應(yīng)用.pdf

1、隨著科學(xué)技術(shù)的進(jìn)步和信息時代的到來，地理信息系統(tǒng)(GIS)技術(shù)得到了蓬勃發(fā)展和廣泛應(yīng)用，導(dǎo)游軟件作為GIS的一個重要應(yīng)用也日益成為應(yīng)用開發(fā)的熱點(diǎn)。其中最優(yōu)路徑規(guī)劃技術(shù)是導(dǎo)游軟件的一個重要研究課題。本論文結(jié)合地理信息系統(tǒng)技術(shù)和電子地圖技術(shù)，分析了各種最短路徑算法的優(yōu)缺點(diǎn)，進(jìn)而對Dijkstra算法提出改進(jìn)，然后討論了動態(tài)規(guī)劃優(yōu)化算法的優(yōu)缺點(diǎn)，將動態(tài)規(guī)劃和改進(jìn)的Dijkstra算法相結(jié)合，設(shè)計出應(yīng)用在導(dǎo)游軟件中的高效的路徑規(guī)劃算法，并模擬實(shí)

2、現(xiàn)。 論文首先分析GIS系統(tǒng)的現(xiàn)狀，介紹了有關(guān)電子地圖的相關(guān)知識，說明路徑規(guī)劃在導(dǎo)游軟件中的重要地位。接著分析了網(wǎng)絡(luò)圖的基本數(shù)據(jù)組織方式。然后介紹路徑規(guī)劃的概念及經(jīng)典的Dijkstra算法，在此基礎(chǔ)上，通過引入二叉堆及鄰接表數(shù)據(jù)結(jié)構(gòu)對算法進(jìn)行改進(jìn)。接下來，為了能在減少最短路徑算法的空間復(fù)雜度的基礎(chǔ)上還能提高其時效性，討論了Dijkstra算法與動態(tài)規(guī)劃理論相結(jié)合的最佳路徑搜索策略，同時通過限制搜索方向減少算法的搜索規(guī)模，提高算法