【導(dǎo)讀】啟發(fā)式搜索算法的有很多種類(lèi)，其中一種就是A*搜索算法。在狀態(tài)空間對(duì)每一個(gè)可。開(kāi)始繼續(xù)搜索到終點(diǎn)目標(biāo)位置，以上就是啟發(fā)式搜素的基本的定義。對(duì)于每次都要選取。最小估價(jià)的節(jié)點(diǎn)，應(yīng)該用到最小優(yōu)先級(jí)隊(duì)列。不要忘了重載自定義節(jié)點(diǎn)的比較操作符。況下，它的空間增長(zhǎng)將有可能是指數(shù)級(jí)別的。這一搜索算法的的好處就是可以將很多的。不需要的冗余的路徑略去，從而使得時(shí)間和空間的效率大大提升。它的主要的組成部分。為OpenList,CloseList和估價(jià)函數(shù)。他可以應(yīng)用在路由的路徑查找，地圖上路徑查找。

　　

【正文】 法采用了對(duì)角線的方式繼續(xù)選找下一個(gè)可能的節(jié)點(diǎn)。 基于 A*算法的路徑尋找 21 圖 改變重點(diǎn)位置后的路徑圖 圖 估價(jià)值改變后的路徑圖 以上兩張圖是為了比較估價(jià)值對(duì)尋找路徑所產(chǎn)生的影響。 為了控制變量這兩個(gè)圖的障礙物路徑是一致的，我通過(guò) JAVA 的文件流保存將他保存起來(lái)一邊對(duì)比。 基于 A*算法的路徑尋找 22 圖 A 采用的估價(jià)值形式為 privatefinalstaticintG_1 = 14。 privatefinalstaticintG_2 = 10。 privatefinalstaticintG_3 = 14。 privatefinalstaticintG_4 = 10。 privatefinalstaticintG_5 = 14。 privatefinalstaticintG_6 = 10。 privatefinalstaticintG_7 = 14。 privatefinalstaticintG_8 = 10。 privatestaticfinalintG_0 = 14。 即他的邊上估價(jià)值比對(duì)角線上的估價(jià)值更有價(jià)值 而圖 B采用的是最初的對(duì)角線上的估價(jià)值最高的形式。 有上面兩張圖可以看見(jiàn)他們選擇出來(lái)的路徑是一致的，這說(shuō)明了路徑的選擇是依賴于障礙物的位置 ，他不依賴于估價(jià)值的大小。 但是同時(shí)我們也注意到了，這兩次的所用的時(shí)間是不同的 第一次圖 A的情況下，消耗的時(shí)間為 12S 而第二次消耗的時(shí)間為 25 秒幾乎翻了一倍。因此，可以得出一個(gè)結(jié)論估價(jià)值的設(shè)置將會(huì)對(duì)算法效率產(chǎn)生很大的影響。 圖 估價(jià)值改為 7,11后的路徑圖 為了再次的比較我將估價(jià)值做了改變 privatefinalstaticintG_1 = 7。 privatefinalstaticintG_2 = 11。 privatefinalstaticintG_3 = 7。 基于 A*算法的路徑尋找 23 privatefinalstaticintG_4 = 11。 privatefinalstaticintG_5 = 7。 privatefinalstaticintG_6 = 11。 privatefinalstaticintG_7 = 7。 privatefinalstaticintG_8 = 11。 privatestaticfinalintG_0 = 7。 發(fā)現(xiàn)路徑?jīng)]有改變但是時(shí)間變成了 29 秒。 表格 1匯總的不同 g(n)不同值的結(jié)果 邊的估價(jià)值 角的估價(jià)值 所用的時(shí)間 路徑是否一致 1 14 10 12 是 2 10 14 25 是 3 7 11 29 是 4 7 5 9 是 5 10 20 33 是 6 17 10 26 是 因此可見(jiàn)估價(jià)值越小對(duì)于算法效率將會(huì)大大的提高。 圖 估價(jià)值不變的位置變換后的結(jié)果 在估價(jià)值不變的情況下 對(duì)于同一張障礙物圖來(lái)說(shuō)變換終點(diǎn)位置對(duì)算法的時(shí)間產(chǎn)生了變化幾乎發(fā)了一倍，這也同樣證明了他的智能性，不是機(jī)械的查找。 基于 A*算法的路徑尋找 24 圖 平移終點(diǎn)后路徑圖 終點(diǎn)位置將其平移，可以看出中間的路徑?jīng)]有發(fā)生改變。更加證明了選出路徑只依賴于障礙物。 g(n)值的結(jié)論： 通過(guò)以上幾次的實(shí)驗(yàn)可以得出結(jié)論如下： （ 1） 最終的路徑只依賴于障礙物，起點(diǎn)和終點(diǎn)的位置。 （ 2） 估價(jià)值對(duì)算法的效率產(chǎn)生一定的影響，從結(jié)果來(lái)看數(shù)值越大消耗的時(shí)間將會(huì)越大。 （ 3） 不考慮其實(shí)起始和結(jié)束的一小段路徑的話，中間繞過(guò)障礙物的路徑只依賴于周?chē)恼系K物位置。這和算法的原理相符合。 基于 h(n)的變化對(duì)結(jié)果的影響 （ 1） 基于 曼哈頓 距離 的改進(jìn) 我們可以定義曼哈頓距離的正式意義 是在歐幾里得空間的固定直角坐標(biāo)系上兩點(diǎn)所形成的線段對(duì)軸產(chǎn)生的投影的距離總和。 曼哈頓距離依賴座標(biāo)系統(tǒng)的轉(zhuǎn)度，而非系統(tǒng)在座標(biāo)軸上的平移或映射。 在出租車(chē)幾何學(xué)中，一個(gè)圓是由從圓心向各個(gè)固定曼哈頓距離標(biāo)示出來(lái)的點(diǎn)圍成 的區(qū)域。因此這種圓其實(shí)就是旋轉(zhuǎn)了 45 度的正方形。如果有一群圓，任兩圓皆相交，則整群圓必在某點(diǎn)相交；因此曼哈頓距離會(huì)形成一個(gè)超凸度量空間（ Injective metric space）。對(duì)一個(gè)半徑為 r 的圓來(lái)說(shuō)，這個(gè)正方形的圓每邊長(zhǎng) √2r 。此 39。圓 的半徑 r對(duì)基于 A*算法的路徑尋找 25 切比雪夫距離（ L∞ 空間）的二維平面來(lái)說(shuō)，也是一個(gè)對(duì)座標(biāo)軸來(lái)說(shuō)邊長(zhǎng)為 2r的正方形，因此二維切比雪夫距離可視為等同于旋轉(zhuǎn)且放大過(guò)的二維曼哈頓距離。然而這種介于 L1與 L∞ 的相等關(guān)系并不能延伸 到更高的維度。 下面將會(huì)對(duì)估價(jià)函數(shù)最重要的 h(n)進(jìn)行比較，此處的 h為 : return (( ) + ( ))*G_0。 它采用是絕對(duì)值作為估價(jià)值。 當(dāng)采用同一個(gè)障礙物地圖時(shí)： 圖 基于曼哈頓距離的路徑圖 路徑產(chǎn)生一定的變化 ： 圖 局部效果圖 在轉(zhuǎn)角的附近節(jié)點(diǎn)更加曲折，而不是一開(kāi)始貼邊繞過(guò)，在最后也是一條曲線而不是一開(kāi)始的直線，這說(shuō)明這個(gè)估價(jià)函數(shù)更加喜歡曲線的方式繞過(guò)尋求路徑。 基于 A*算法的路徑尋找 26 我們?cè)?使用另外一種 h(n)： return (int) ((( ) + ( ))*G_0)。 . 圖 修改 后的 曼哈頓距離的路徑圖 這次得出的路徑更加的曲折不過(guò)更加接近于最好的路徑，但是他的耗時(shí)接近了 50秒，這有可能是因?yàn)樗菍?duì)數(shù)計(jì)算因此耗時(shí)更高。但是我發(fā)現(xiàn)在開(kāi)始過(guò)程中有些不必要的曲折，并且發(fā)現(xiàn)這里的數(shù)據(jù)類(lèi)型為 INT 值，我將改成 DOUBLE 提高他的精度，希望他可以更加精確地得出結(jié)果。 基于 A*算法的路徑尋找 27 圖 改變精度后的路徑圖 果然隨著精度的提高他的路徑更加 的圓潤(rùn)了并且少了不必要的曲線，并且結(jié)束時(shí)是對(duì)角線，而不是以前的折線，更加節(jié)省了路徑。但是他相應(yīng)的提高了運(yùn)算的時(shí)間 54 秒，不過(guò)這是可以接受的。 （ 2） 基于 對(duì)角線距離 的改進(jìn) . 這個(gè)方法可以平衡 h（ n）和 g(n)之間的關(guān)系 ，可以 更加 充分的考慮到點(diǎn)之間關(guān)系。但是相比起曼哈頓距離的方法他在速度上有可能會(huì)慢點(diǎn)。 xDistance=( )。 yDistance=( )。 if (xDistanceyDistance) { float h。 h = 14*yDistance + 10*(xDistanceyDistance)。 return h*G_0。 } else{ float h。 h = 14*xDistance + 10*(yDistancexDistance)。 return h*G_0。 他會(huì)根據(jù)不同方向來(lái)調(diào)整 下 一個(gè)節(jié)點(diǎn)的位置。 基于 A*算法的路徑尋找 28 圖 對(duì)角線距離的路徑圖 通過(guò)這一個(gè)路徑我們發(fā)現(xiàn)這個(gè)路徑更加的貼近最佳的路徑?；?對(duì)角線 的判斷方法更加適合這一情況。 （ 3） 基于歐式幾何的改進(jìn) 歐式幾何更加接近于人的思維，因此我們嘗試采用這種方式來(lái)進(jìn)行他的改進(jìn)。 return (float) (G_0*(()^2+()^2))。 圖 歐式幾何的路徑圖 基于 A*算法的路徑尋找 29 這條路徑不像對(duì)角線距離的路徑緊貼著 障礙物，而是類(lèi)似于人在畫(huà)圖的時(shí)候 產(chǎn)生的路徑。 （ 4） 基于 Breaking ties 的微調(diào)方案 在某些情況下，我們不希望算法的步數(shù)不超過(guò)某一個(gè)特定的值。我們假設(shè)這個(gè)值為1000，那么我可以采用以下的方式定義 h(n) H(n) *= ( + p) P=1/1000 我們將它與對(duì)角線的方式進(jìn)行結(jié)合 float dx1=()。 float dy1=()。 float dx2=35。 float dy2=39。 float cross = (dx1*dy2dx2*dy1)。 float h = 0。 h +=cross*。 return h。 圖 基于 Breaking ties的路徑圖 至此我們得到了目前最好的一條路徑他基本是以對(duì)角線的方式進(jìn)行的搜索，但是中間的路徑具有了歐式幾何的圓潤(rùn)。 基于 A*算法的路徑尋找 30 6 結(jié)束語(yǔ) 總結(jié) 從第五章的試驗(yàn)可以看出 G（ n）函數(shù)將會(huì)根據(jù)障礙物的位置和父節(jié)點(diǎn)的位置調(diào)整他的子節(jié)點(diǎn)的位置， G(N)函數(shù)的定義將會(huì)影響到算法的效率，越是復(fù)雜的數(shù)據(jù)上的定義就會(huì)耗費(fèi)跟多時(shí)間。 H(N)從以上實(shí)驗(yàn)來(lái)看決定了路徑的最終的形狀，更加精確地函數(shù)，例如對(duì)數(shù)函數(shù)將會(huì)帶來(lái)更加合理的路徑。并且在編程的過(guò)程中，這一個(gè)函數(shù) 的 數(shù)據(jù)類(lèi)型也影響了 產(chǎn)生的路徑 的精度，在調(diào)整為 FLOAT 浮點(diǎn)數(shù)字后路徑看上去更加的圓潤(rùn)了，但是同時(shí)也將耗時(shí)提高了上去。由以上兩點(diǎn)可見(jiàn)估價(jià)函數(shù) f(n)有可以說(shuō)是由節(jié)點(diǎn)和路徑兩種選擇組成的。兩者相互的制約和選擇產(chǎn)生了最后的路徑。 在后面對(duì)于 h(n)的考察，發(fā)現(xiàn)路徑的一些細(xì)節(jié)上比如說(shuō)拐彎等等都依賴于 h(n)對(duì)于下一個(gè)子節(jié)點(diǎn)的判斷，采用不同的距離標(biāo)準(zhǔn)進(jìn)行判斷將會(huì)產(chǎn)生截然不同的路徑結(jié)果。而且當(dāng)我們對(duì)于路徑提出更多要求的的時(shí)候，對(duì)于 h(n)就需要進(jìn)行一定的改變，例如步數(shù)等等。 實(shí)驗(yàn) 存在的問(wèn)題 和改善 這次尋找路徑的試驗(yàn)讓我 清晰的了解到了 A*算法 的優(yōu)勢(shì)和好處。在編寫(xiě)過(guò)程也遇到很多問(wèn)題，通過(guò)網(wǎng)上查找解決辦法，這也是一種很好的經(jīng)驗(yàn)，這一實(shí)驗(yàn)的操作下來(lái)還是比較順利的，并且在指導(dǎo)老師史小紅的指導(dǎo)下對(duì)論文結(jié)構(gòu)和寫(xiě)法進(jìn)行了改進(jìn)，并且對(duì)算法也有了更深入的認(rèn)識(shí)。 這次試驗(yàn)中存在一個(gè)問(wèn)題就是算法時(shí)間不穩(wěn)定，在考慮后排除了算法和程序的問(wèn)題，這一問(wèn)題應(yīng)該是 CPU 和系統(tǒng)任務(wù)分配的問(wèn)題上，本人的機(jī)子為四核處理器。因此有可能被分配到不同的內(nèi)核上進(jìn)行了處理。產(chǎn)生了一定的誤差，為避免這一誤差，數(shù)值采用了平均值的算法。試圖將影響降到最低。 并且這一程序的運(yùn)行是以線程的方式進(jìn)行的設(shè)計(jì)， 因此可能產(chǎn)生一定的擾動(dòng)。 由于本人的能力值有限，這次試驗(yàn)只是實(shí)驗(yàn) A*算法對(duì)其他的算法并沒(méi)有深入，希望以后有機(jī)會(huì)可以繼續(xù)研究，希望可以諒解。 基于 A*算法的路徑尋找 31 參 考 文 獻(xiàn) [1] XiangLiu,A Comparative Study of Astar Algorithms for Search and rescue in Perfect Maze,2020 [2] KhammapunKhantanapoka and KrisanaChinnasarn,Pathfinding of 2D amp。 3D Game RealTime Strategy with Depth DirectionA*Algorithm for MultiLayer,2020 [3] Hongxian Zhang,Research and Application for Combination between Copied Map and A* Algorithm in 2D Game,2020 [4] Alex Kring, Alex J. Champandard, and Nick Samarin, DHPA* and SHPA*: Efficient HierarchicalPathfinding in Dynamic and StaticGame Worlds,2020 [5] Gee ,ALGORITHMS IN A NUTSHELL,東南大學(xué)出版社， 2020 [6] Patrick Lester， Heuristics and A* Pathfinding， ， 2004 基于 A*算法的路徑尋找 32 發(fā)表學(xué)術(shù)論文情況 基于 A*算法的路徑尋找 33 致 謝 在這個(gè)最后大學(xué)時(shí)光，首先感謝我的指導(dǎo)老師史小宏老師，沒(méi)有你的督促和批評(píng)指正。我也不會(huì)堅(jiān)持努力的將這個(gè)畢業(yè)設(shè)計(jì)做好。感謝老師對(duì)我題目和論文各個(gè)地方的指導(dǎo)與幫助。接下來(lái)要感謝我的組員們，在每次和你們相見(jiàn)的時(shí)候，都是歡聲笑語(yǔ)，不想大學(xué)生活已經(jīng)快要結(jié)束了。不知道以后還有沒(méi)有機(jī)會(huì)在這樣的聊天和吃飯。感謝我的父母在此期間對(duì)我關(guān)心與支持。感謝網(wǎng)上無(wú)私奉獻(xiàn)的人民，沒(méi)有你們的幫助，編程中遇到的很多問(wèn)題也無(wú)法 圓滿的解決。 在這次畢業(yè)設(shè)計(jì)同時(shí)，也讓我了解到，山外有山，人外有人。感謝你們讓我知道了自己的渺小，指引了我的方向。