路徑規(guī)劃技術在導游軟件中的應用.pdf

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

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