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

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

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