gps車載導航儀中最短路徑算法設(shè)計與實現(xiàn)畢業(yè)論文(編輯修改稿)
2025-07-22 14:42 本頁面
【文章內(nèi)容簡介】 ： r Dijkstra實現(xiàn)過程第一步 先取意即到的距離為0,而是對所賦的初值。第二步 利用已知,根據(jù)對進行修正。第三步 對所有修正后的求出其最小者。其對應的點是所能一步到達的點中最近的一個,由于所有。因此任何從其它點中轉(zhuǎn)而到達的通路上的距離都大于直接到的距離,因此就是到的最短距離,所以在算法中令并從s中刪去,若k=n則就是到的最短路線,計算結(jié)束。否則令回到第二步,繼續(xù)運算,直到k=n為止。這樣每一次迭代,得到到一點的最短距離,重復上述過程直到。 Floyd算法Floyd算法的基本原理和實現(xiàn)方法為:如果一個矩陣其中表示與間的距離,若與間無路可通,則為無窮大。與間的最短距離存在經(jīng)過與間的和不經(jīng)過兩種情況,所以可以令,n(n為節(jié)點數(shù))。檢查與的值,在此,與分別為目前所知的到與到的最短距離,因此,就是到經(jīng)過的最短距離。所以,若有,就表示從出發(fā)經(jīng)再到的距離要比原來的到距離短,自然把到的重寫成。每當一個搜索完,就是目前到的最短距離。重復這一過程,最后當查完所有時,就為到的最短距離。 A*算法設(shè)計與實現(xiàn) A*算法的優(yōu)勢A*算法在人工智能中是一種典型的啟發(fā)式搜索算法。常用的狀態(tài)空間搜索有深度優(yōu)先和廣度優(yōu)先。廣度優(yōu)先是從初始狀態(tài)一層一層向下找，直到找到目標為止。深度優(yōu)先是按照一定的順序前查找完一個分支，再查找另一個分支，以至找到目標為止。前面說的廣度和深度優(yōu)先搜索有一個很大的缺陷就是他們都是在一個給定的狀態(tài)空間中窮舉。這在狀態(tài)空間不大的情況下是很合適的算法，可是當狀態(tài)空間十分大，且不預測的情況下就不可取了。他的效率實在太低，甚至不可完成。而啟發(fā)式搜索就是在狀態(tài)空間中的搜索對每一個搜索的位置進行評估，得到最好的位置，再從這個位置進行搜索直到目標。這樣可以省略大量無畏的搜索路徑，提到了效率。 總體設(shè)計思想在地圖的主要街道或十字路口設(shè)置預設(shè)點，確定起點和終點坐標后，根據(jù)兩點之間的坐標差找到兩點間的預設(shè)點，從而找到相鄰預設(shè)點間的最優(yōu)值，最后根據(jù)長度找出最短路徑。公式表示為： 其中 是節(jié)點n從初始點到目標點的估價函數(shù)。 是在狀態(tài)空間中從初始節(jié)點到n節(jié)點的實際代價。是從n到目標節(jié)點最佳路徑的估計代價。在這里主要是體現(xiàn)了搜索的啟發(fā)信息，因為是已知的。詳細來說，代表了搜索的廣度的優(yōu)先趨勢。但是當 時，可以省略,而提高效率。 保證找到最短路徑（最優(yōu)解的）條件，關(guān)鍵在于估價函數(shù)的選?。骸 」纼r值= n到目標節(jié)點的距離實際值，這種情況下，搜索的點數(shù)多，搜索范圍大，效率低。但能得到最優(yōu)解。 詳細論述創(chuàng)建兩個表，OPEN表保存所有已生成而未考察的節(jié)點，CLOSED表中記錄已訪問過的節(jié)點。遍歷當前節(jié)點的各個節(jié)點，將n節(jié)點放入CLOSE中，取n節(jié)點的子節(jié)點X,算X的估價值。 While(OPEN!=NULL) { 從OPEN表中取估價值f最小的節(jié)點n?！ f(n節(jié)點==目標節(jié)點) break。 else { if(X in OPEN) 比較兩個X的估價值f //注意是同一個節(jié)點的兩個不同路徑的估價值 if( X的估價值小于OPEN表的估價值 ) 更新OPEN表中的估價值。 //取最小路徑的估價值 if(X in CLOSE) 比較兩個X的估價值 //注意是同一個節(jié)點的兩個不同路徑的估價值 if( X的估價值小于CLOSE表的估價值 ) 更新CLOSE表中的估價值。 把X節(jié)點放入OPEN //取最小路徑的估價值 if(X not in both) 求X的估價值。 并將X插入OPEN表中。 //還沒有排序 } 將n節(jié)點插入CLOSE表中?！ “凑展纼r值將OPEN表中的節(jié)點排序。 //實際上是比較OPEN表內(nèi)節(jié)點f的大小，從最小路徑的節(jié)點向下進行。文中寫到的啟發(fā)式搜索其實還有很多的算法，比如：局部擇優(yōu)搜索法、最好優(yōu)先搜索法等等。這些算法都使用了啟發(fā)函數(shù)，但在具體的選取最佳搜索節(jié)點時的策略不同。象局部擇優(yōu)搜索法，就是在搜索的過程中選取“最佳節(jié)點”后舍棄其他的兄弟節(jié)點，父親節(jié)點，而一直得搜索下去。這種搜索的結(jié)果很明顯，由于舍棄了其他的節(jié)點，可能也把最好的節(jié)點都舍棄了，因為求解的最佳節(jié)點只是在該階段的最佳并不一定是全局的最佳。最好優(yōu)先就聰明多了，他在搜索時，便沒有舍棄節(jié)點（除非該節(jié)點是死節(jié)點），在每一步的估價中都把當前的節(jié)點和以前的節(jié)點
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1