先介紹幾個(gè)概念有助于理解Astar算法，
啟發(fā)式搜索:對(duì)每一個(gè)搜索的位置進(jìn)行評(píng)估，得到最好的位置，再?gòu)倪@個(gè)位置進(jìn)行搜索直到目標(biāo)。可以省略大量不必要的搜索，提高效率。
估價(jià)函數(shù):從當(dāng)前節(jié)點(diǎn)移動(dòng)到目標(biāo)節(jié)點(diǎn)的預(yù)估費(fèi)用，這個(gè)估計(jì)就是啟發(fā)式的，在尋路問(wèn)題和迷宮問(wèn)題中，我們通常用曼哈頓估價(jià)函數(shù)（Manhattan）預(yù)估費(fèi)用。 （如果搜索區(qū)域的劃分不是正方形，就不用Manhattan算法（|x|+|y|），換成其他的）
Astar算法與BFS: BFS是Astar算法的一個(gè)特例。對(duì)BFS算法，從當(dāng)前節(jié)點(diǎn)拓展出來(lái)的每一個(gè)沒有被訪問(wèn)過(guò)的節(jié)點(diǎn)都要放入隊(duì)列進(jìn)一步拓展，正因?yàn)槿绱?#xff0c;BFS算法的估計(jì)函數(shù)H永遠(yuǎn)為0，沒有啟發(fā)式的信息，所以可以認(rèn)為是最爛的Astar算法。
開啟列表: 將要被遍歷的點(diǎn)的集合。
關(guān)閉列表:已經(jīng)被遍歷的點(diǎn)的集合。

Astar算法特點(diǎn): 理論上是時(shí)間最優(yōu)的，缺點(diǎn)是空間呈指數(shù)增長(zhǎng)。(IDAstar 算法：這種算法被稱為迭代加深A(yù)star算法，可以有效的解決 Astar 空間增長(zhǎng)帶來(lái)的問(wèn)題，甚至可以不用到優(yōu)先級(jí)隊(duì)列。)

搜索區(qū)域 (綠色–起點(diǎn)A，紅色–終點(diǎn)B，藍(lán)色–墻)

搜索區(qū)域被劃分成了方形網(wǎng)格（二維數(shù)組），像這樣簡(jiǎn)化搜索區(qū)域，是尋路的第一步。

二維數(shù)組的每一個(gè)元素都是一個(gè)方格，被標(biāo)記為 可通過(guò) 和 不可通過(guò)，路徑就是從起點(diǎn)到終點(diǎn)所經(jīng)過(guò)的方塊的集合。（通過(guò)的路徑也可以叫節(jié)點(diǎn)的集合，因?yàn)槁窂讲灰欢ㄒ指畛煞綁K，完全可以是菱形，三角形或是其他形狀，而節(jié)點(diǎn)可以放在形狀的任意位置，所以簡(jiǎn)單通用。）

開始搜索
從A開始,通過(guò)查找相鄰方格，向外拓展直至找到B點(diǎn)。

從A開始將其存入一個(gè)“開啟列表”（待檢查方格的列表）。

尋找起點(diǎn)A周圍所有的可通行方格（忽略墻，水等不可通行的地形方格），將他們加入“開啟列表”。然后設(shè)置起點(diǎn)A為他們的父方格。

從”開啟列表“刪除起點(diǎn)A，將其存入一個(gè)“關(guān)閉列表”（保存所有不需要再次檢查的方格）。如圖暗綠色方格是起始點(diǎn)A的中心。它被用淺藍(lán)色描邊，以表示它被加入到關(guān)閉列表中了。所有可通行相鄰方格都在”開啟列表“之中，被用淺綠色描邊。每個(gè)方格都有一個(gè)灰色指針指向父方格。

接著我們就要開始選擇開啟列表中的臨近方格，選中之后重復(fù)前邊的過(guò)程。但是，如何選擇臨近方格呢？

路徑評(píng)分
選擇臨近方格的關(guān)鍵是這個(gè)等式：F = G + H，我們選取F值最低的方格。
G = 從 起點(diǎn) 開始到 待選方格 的路徑的移動(dòng)耗費(fèi)。（是可以明確計(jì)算出的，而且要實(shí)時(shí)保持是最短最優(yōu)的）
H = 臨近方格 到 終點(diǎn)B 的預(yù)估移動(dòng)耗費(fèi)。（大致預(yù)測(cè)，假設(shè)所有方格可通行忽略了障礙物對(duì)移動(dòng)耗費(fèi)的影響,通常越靠近終點(diǎn)越小）

計(jì)算方法：
G: 通常我們令垂直移動(dòng)一格耗費(fèi)為1，水平移動(dòng)一格耗費(fèi)為1，對(duì)角線移動(dòng)一格為1.414。但是為了簡(jiǎn)化，我們要用近似值，因?yàn)檎麛?shù)對(duì)計(jì)算機(jī)而言計(jì)算更便捷，垂直耗費(fèi)10，水平耗費(fèi)10，對(duì)角線耗費(fèi)14。（如果不用簡(jiǎn)化方法，尋路將變得十分緩慢）
求值的方法就是取其父節(jié)點(diǎn)的G值，再根據(jù)它相對(duì)于父節(jié)點(diǎn)的位置（水平，垂直，對(duì)角線）取耗費(fèi)值，二者相加。
H: H值得估算方法有多種，本文僅介紹一種–曼哈頓f方法（Manhattan)。它計(jì)算的是當(dāng)前格到目標(biāo)格之間水平和垂直得方格的數(shù)量之和，忽略對(duì)角線，障礙物，只是對(duì)剩余距離的一個(gè)估算，非實(shí)際值,這也是這類方法被稱為啟發(fā)式的原因。

F = G + H, 如下圖，F,G,H的值分別位于方格的左上角，左下角，右下角。

繼續(xù)搜索
繼續(xù)搜索時(shí)，從開啟列表中選擇F值最低的方格（如果有兩個(gè)F值相同的方格，通常后存入列表的格子會(huì)更快捷）。然后：
4. 將它從開啟列表刪除，存入關(guān)閉列表。
5. 檢查所有相鄰的方格，略過(guò)已經(jīng)在關(guān)閉列表中的和不可通過(guò)的格子，將他們存入開啟列表，如果它們不在開始列表中，就將當(dāng)前節(jié)點(diǎn)作為他們的父節(jié)點(diǎn)。
6. 如果某個(gè)相鄰格已經(jīng)在開啟列表中，則通過(guò)判斷G值，檢查當(dāng)前當(dāng)前路徑是否更好，如果新的G值更低，則將此相鄰節(jié)點(diǎn)的父節(jié)點(diǎn)改為當(dāng)前節(jié)點(diǎn)，從新計(jì)算它的G和H值，如果不是就什么也不做。

經(jīng)過(guò)上邊的過(guò)程，我們會(huì)很快找到終點(diǎn)。

顯示路徑
從目標(biāo)格開始，按箭頭方向朝父節(jié)點(diǎn)移動(dòng)，最終會(huì)回到起始格，這條路徑就是我們所找到的最優(yōu)路徑。

方法總結(jié)
1.將起始格添加入開啟列表。
2.重復(fù)如下操作：
a. 尋找開啟列表中F值最低的格子，稱其為當(dāng)前格。
b. 把它存入關(guān)閉列表，從當(dāng)前列表中刪除。
c. 對(duì)于相鄰格，如果不可通過(guò)或者已在關(guān)閉列表，則略過(guò)。
反之 ①如果它不在開啟列表就將它存入開啟列表，以當(dāng)前節(jié)點(diǎn)為父節(jié)點(diǎn)，計(jì)算相鄰格的F,G,H.
②若已經(jīng)存在于開啟列表，則用G值檢查新的路徑是否更好，如果G值耕地就把這一相鄰格的父節(jié)點(diǎn)改 為當(dāng)前格，重新計(jì)算相鄰格的G和H。 如果保持開啟列表按F值排序，改變后就需要重新對(duì)開啟列表進(jìn)行排序。
d. 停止，
①如果沒有找到目標(biāo)格，而開啟列表已經(jīng)空了，就表示路徑不存在。
②如果目標(biāo)格被添加如關(guān)閉列表，這是路徑被找到。
3. 保存路徑，從目標(biāo)格開始沿著父節(jié)點(diǎn)移動(dòng)直至回到開始節(jié)點(diǎn)。

總結(jié)

以上是生活随笔為你收集整理的Astar算法基本概念及其实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。