算法介紹

A*（念做：A Star）算法是一種很常用的路徑查找和圖形遍歷算法。它有較好的性能和準(zhǔn)確度。本文在講解算法的同時(shí)也會(huì)提供Python語(yǔ)言的代碼實(shí)現(xiàn)，并會(huì)借助matplotlib庫(kù)動(dòng)態(tài)的展示算法的運(yùn)算過程。

A*算法最初發(fā)表于1968年，由Stanford研究院的Peter Hart, Nils Nilsson以及Bertram Raphael發(fā)表。它可以被認(rèn)為是Dijkstra算法的擴(kuò)展。

由于借助啟發(fā)函數(shù)的引導(dǎo)，A*算法通常擁有更好的性能。

廣度優(yōu)先搜索

為了更好的理解A*算法，我們首先從廣度優(yōu)先（Breadth First）算法講起。

正如其名稱所示，廣度優(yōu)先搜索以廣度做為優(yōu)先級(jí)進(jìn)行搜索。

從起點(diǎn)開始，首先遍歷起點(diǎn)周圍鄰近的點(diǎn)，然后再遍歷已經(jīng)遍歷過的點(diǎn)鄰近的點(diǎn)，逐步的向外擴(kuò)散，直到找到終點(diǎn)。

這種算法就像洪水（Flood fill）一樣向外擴(kuò)張，算法的過程如下圖所示：

在上面這幅動(dòng)態(tài)圖中，算法遍歷了圖中所有的點(diǎn)，這通常沒有必要。對(duì)于有明確終點(diǎn)的問題來說，一旦到達(dá)終點(diǎn)便可以提前終止算法，下面這幅圖對(duì)比了這種情況：

在執(zhí)行算法的過程中，每個(gè)點(diǎn)需要記錄達(dá)到該點(diǎn)的前一個(gè)點(diǎn)的位置 -- 可以稱之為父節(jié)點(diǎn)。這樣做之后，一旦到達(dá)終點(diǎn)，便可以從終點(diǎn)開始，反過來順著父節(jié)點(diǎn)的順序找到起點(diǎn)，由此就構(gòu)成了一條路徑。

Dijkstra算法

Dijkstra算法是由計(jì)算機(jī)科學(xué)家Edsger W. Dijkstra在1956年提出的。

Dijkstra算法用來尋找圖形中節(jié)點(diǎn)之間的最短路徑。

考慮這樣一種場(chǎng)景，在一些情況下，圖形中相鄰節(jié)點(diǎn)之間的移動(dòng)代價(jià)并不相等。例如，游戲中的一幅圖，既有平地也有山脈，那么游戲中的角色在平地和山脈中移動(dòng)的速度通常是不相等的。

在Dijkstra算法中，需要計(jì)算每一個(gè)節(jié)點(diǎn)距離起點(diǎn)的總移動(dòng)代價(jià)。同時(shí)，還需要一個(gè)優(yōu)先隊(duì)列結(jié)構(gòu)。對(duì)于所有待遍歷的節(jié)點(diǎn)，放入優(yōu)先隊(duì)列中會(huì)按照代價(jià)進(jìn)行排序。

在算法運(yùn)行的過程中，每次都從優(yōu)先隊(duì)列中選出代價(jià)最小的作為下一個(gè)遍歷的節(jié)點(diǎn)。直到到達(dá)終點(diǎn)為止。

下面對(duì)比了不考慮節(jié)點(diǎn)移動(dòng)代價(jià)差異的廣度優(yōu)先搜索與考慮移動(dòng)代價(jià)的Dijkstra算法的運(yùn)算結(jié)果：

當(dāng)圖形為網(wǎng)格圖，并且每個(gè)節(jié)點(diǎn)之間的移動(dòng)代價(jià)是相等的，那么Dijkstra算法將和廣度優(yōu)先算法變得一樣。

最佳優(yōu)先搜索

在一些情況下，如果我們可以預(yù)先計(jì)算出每個(gè)節(jié)點(diǎn)到終點(diǎn)的距離，則我們可以利用這個(gè)信息更快的到達(dá)終點(diǎn)。

其原理也很簡(jiǎn)單。與Dijkstra算法類似，我們也使用一個(gè)優(yōu)先隊(duì)列，但此時(shí)以每個(gè)節(jié)點(diǎn)到達(dá)終點(diǎn)的距離作為優(yōu)先級(jí)，每次始終選取到終點(diǎn)移動(dòng)代價(jià)最小（離終點(diǎn)最近）的節(jié)點(diǎn)作為下一個(gè)遍歷的節(jié)點(diǎn)。這種算法稱之為最佳優(yōu)先（Best First）算法。

這樣做可以大大加快路徑的搜索速度，如下圖所示：

但這種算法會(huì)不會(huì)有什么缺點(diǎn)呢？答案是肯定的。

因?yàn)?#xff0c;如果起點(diǎn)和終點(diǎn)之間存在障礙物，則最佳優(yōu)先算法找到的很可能不是最短路徑，下圖描述了這種情況。

A*算法

對(duì)比了上面幾種算法，最后終于可以講解本文的重點(diǎn)：A*算法了。

下面的描述我們將看到，A*算法實(shí)際上是綜合上面這些算法的特點(diǎn)于一身的。

A*算法通過下面這個(gè)函數(shù)來計(jì)算每個(gè)節(jié)點(diǎn)的優(yōu)先級(jí)。

?

f(n)=g(n)+h(n)

其中：

• f(n)?是節(jié)點(diǎn)n的綜合優(yōu)先級(jí)。當(dāng)我們選擇下一個(gè)要遍歷的節(jié)點(diǎn)時(shí)，我們總會(huì)選取綜合優(yōu)先級(jí)最高（值最小）的節(jié)點(diǎn)。
• g(n)?是節(jié)點(diǎn)n距離起點(diǎn)的代價(jià)。
• h(n)?是節(jié)點(diǎn)n距離終點(diǎn)的預(yù)計(jì)代價(jià)，這也就是A*算法的啟發(fā)函數(shù)。關(guān)于啟發(fā)函數(shù)我們?cè)谙旅嬖敿?xì)講解。

A*算法在運(yùn)算過程中，每次從優(yōu)先隊(duì)列中選取f(n)值最小（優(yōu)先級(jí)最高）的節(jié)點(diǎn)作為下一個(gè)待遍歷的節(jié)點(diǎn)。

另外，A*算法使用兩個(gè)集合來表示待遍歷的節(jié)點(diǎn)，與已經(jīng)遍歷過的節(jié)點(diǎn)，這通常稱之為open_set和close_set。

完整的A*算法描述如下：

* 初始化open_set和close_set； * 將起點(diǎn)加入open_set中，并設(shè)置優(yōu)先級(jí)為0（優(yōu)先級(jí)最高）； * 如果open_set不為空，則從open_set中選取優(yōu)先級(jí)最高的節(jié)點(diǎn)n：* 如果節(jié)點(diǎn)n為終點(diǎn)，則：* 從終點(diǎn)開始逐步追蹤parent節(jié)點(diǎn)，一直達(dá)到起點(diǎn)；* 返回找到的結(jié)果路徑，算法結(jié)束；* 如果節(jié)點(diǎn)n不是終點(diǎn)，則：* 將節(jié)點(diǎn)n從open_set中刪除，并加入close_set中；* 遍歷節(jié)點(diǎn)n所有的鄰近節(jié)點(diǎn)：* 如果鄰近節(jié)點(diǎn)m在close_set中，則：* 跳過，選取下一個(gè)鄰近節(jié)點(diǎn)* 如果鄰近節(jié)點(diǎn)m也不在open_set中，則：* 設(shè)置節(jié)點(diǎn)m的parent為節(jié)點(diǎn)n* 計(jì)算節(jié)點(diǎn)m的優(yōu)先級(jí)* 將節(jié)點(diǎn)m加入open_set中

啟發(fā)函數(shù)

上面已經(jīng)提到，啟發(fā)函數(shù)會(huì)影響A*算法的行為。

• 在極端情況下，當(dāng)啟發(fā)函數(shù)h(n)始終為0，則將由g(n)決定節(jié)點(diǎn)的優(yōu)先級(jí)，此時(shí)算法就退化成了Dijkstra算法。
• 如果h(n)始終小于等于節(jié)點(diǎn)n到終點(diǎn)的代價(jià)，則A*算法保證一定能夠找到最短路徑。但是當(dāng)h(n)的值越小，算法將遍歷越多的節(jié)點(diǎn)，也就導(dǎo)致算法越慢。
• 如果h(n)完全等于節(jié)點(diǎn)n到終點(diǎn)的代價(jià)，則A*算法將找到最佳路徑，并且速度很快。可惜的是，并非所有場(chǎng)景下都能做到這一點(diǎn)。因?yàn)樵跊]有達(dá)到終點(diǎn)之前，我們很難確切算出距離終點(diǎn)還有多遠(yuǎn)。
• 如果h(n)的值比節(jié)點(diǎn)n到終點(diǎn)的代價(jià)要大，則A*算法不能保證找到最短路徑，不過此時(shí)會(huì)很快。
• 在另外一個(gè)極端情況下，如果h(n)相較于g(n)大很多，則此時(shí)只有h(n)產(chǎn)生效果，這也就變成了最佳優(yōu)先搜索。

由上面這些信息我們可以知道，通過調(diào)節(jié)啟發(fā)函數(shù)我們可以控制算法的速度和精確度。因?yàn)樵谝恍┣闆r，我們可能未必需要最短路徑，而是希望能夠盡快找到一個(gè)路徑即可。這也是A*算法比較靈活的地方。

對(duì)于網(wǎng)格形式的圖，有以下這些啟發(fā)函數(shù)可以使用：

• 如果圖形中只允許朝上下左右四個(gè)方向移動(dòng)，則可以使用曼哈頓距離（Manhattan distance）。
• 如果圖形中允許朝八個(gè)方向移動(dòng)，則可以使用對(duì)角距離。
• 如果圖形中允許朝任何方向移動(dòng)，則可以使用歐幾里得距離（Euclidean distance）。

關(guān)于距離

曼哈頓距離

如果圖形中只允許朝上下左右四個(gè)方向移動(dòng)，則啟發(fā)函數(shù)可以使用曼哈頓距離，它的計(jì)算方法如下圖所示：

計(jì)算曼哈頓距離的函數(shù)如下，這里的D是指兩個(gè)相鄰節(jié)點(diǎn)之間的移動(dòng)代價(jià)，通常是一個(gè)固定的常數(shù)。

function heuristic(node) =dx = abs(node.x - goal.x)dy = abs(node.y - goal.y)return D * (dx + dy)

對(duì)角距離

如果圖形中允許斜著朝鄰近的節(jié)點(diǎn)移動(dòng)，則啟發(fā)函數(shù)可以使用對(duì)角距離。它的計(jì)算方法如下：

計(jì)算對(duì)角距離的函數(shù)如下，這里的D2指的是兩個(gè)斜著相鄰節(jié)點(diǎn)之間的移動(dòng)代價(jià)。如果所有節(jié)點(diǎn)都正方形，則其值就是2?D。

function heuristic(node) =dx = abs(node.x - goal.x)dy = abs(node.y - goal.y)return D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)

歐幾里得距離

如果圖形中允許朝任意方向移動(dòng)，則可以使用歐幾里得距離。

歐幾里得距離是指兩個(gè)節(jié)點(diǎn)之間的直線距離，因此其計(jì)算方法也是我們比較熟悉的：(p2.x?p1.x)2+(p2.y?p1.y)2。其函數(shù)表示如下：

function heuristic(node) =dx = abs(node.x - goal.x)dy = abs(node.y - goal.y)return D * sqrt(dx * dx + dy * dy)

算法實(shí)現(xiàn)

雖然前面介紹了很多內(nèi)容，但實(shí)際上A*算法并不復(fù)雜，實(shí)現(xiàn)起來也比較簡(jiǎn)單。

下面我們給出一個(gè)Python語(yǔ)言的代碼示例。

之所以使用Python語(yǔ)言是因?yàn)槲覀兛梢越柚鷐atplotlib庫(kù)很方便的將結(jié)果展示出來。在理解了算法之后，通過其他語(yǔ)言實(shí)現(xiàn)也并非難事。

算法的源碼可以到我的github上下載：paulQuei/a-star-algorithm。

我們的算法演示的是在一個(gè)二維的網(wǎng)格圖形上從起點(diǎn)找尋終點(diǎn)的求解過程。

坐標(biāo)點(diǎn)與地圖

首先，我們創(chuàng)建一個(gè)非常簡(jiǎn)單的類來描述圖中的點(diǎn)，相關(guān)代碼如下：

# point.pyimport sysclass Point:def __init__(self, x, y):self.x = xself.y = yself.cost = sys.maxsize

接著，我們實(shí)現(xiàn)一個(gè)描述地圖結(jié)構(gòu)的類。為了簡(jiǎn)化算法的描述:

我們選定左下角坐標(biāo)[0, 0]的點(diǎn)是算法起點(diǎn)，右上角坐標(biāo)[size - 1, size - 1]的點(diǎn)為要找的終點(diǎn)。

為了讓算法更有趣，我們?cè)诘貓D的中間設(shè)置了一個(gè)障礙，并且地圖中還會(huì)包含一些隨機(jī)的障礙。該類的代碼如下：

# random_map.pyimport numpy as npimport pointclass RandomMap:def __init__(self, size=50): ①self.size = sizeself.obstacle = size//8 ②self.GenerateObstacle() ③def GenerateObstacle(self):self.obstacle_point = []self.obstacle_point.append(point.Point(self.size//2, self.size//2))self.obstacle_point.append(point.Point(self.size//2, self.size//2-1))# Generate an obstacle in the middlefor i in range(self.size//2-4, self.size//2): ④self.obstacle_point.append(point.Point(i, self.size-i))self.obstacle_point.append(point.Point(i, self.size-i-1))self.obstacle_point.append(point.Point(self.size-i, i))self.obstacle_point.append(point.Point(self.size-i, i-1))for i in range(self.obstacle-1): ⑤x = np.random.randint(0, self.size)y = np.random.randint(0, self.size)self.obstacle_point.append(point.Point(x, y))if (np.random.rand() > 0.5): # Random boolean ⑥for l in range(self.size//4):self.obstacle_point.append(point.Point(x, y+l))passelse:for l in range(self.size//4):self.obstacle_point.append(point.Point(x+l, y))passdef IsObstacle(self, i ,j): ⑦for p in self.obstacle_point:if i==p.x and j==p.y:return Truereturn False

這段代碼說明如下：

構(gòu)造函數(shù)，地圖的默認(rèn)大小是50x50；

設(shè)置障礙物的數(shù)量為地圖大小除以8；

調(diào)用GenerateObstacle生成隨機(jī)障礙物；

在地圖的中間生成一個(gè)斜著的障礙物；

隨機(jī)生成其他幾個(gè)障礙物；

障礙物的方向也是隨機(jī)的；

定義一個(gè)方法來判斷某個(gè)節(jié)點(diǎn)是否是障礙物；

算法主體

有了基本的數(shù)據(jù)結(jié)構(gòu)之后，我們就可以開始實(shí)現(xiàn)算法主體了。

這里我們通過一個(gè)類來封裝我們的算法。

首先實(shí)現(xiàn)一些算法需要的基本函數(shù)，它們?nèi)缦?#xff1a;

# a_star.pyimport sys import timeimport numpy as npfrom matplotlib.patches import Rectangleimport point import random_mapclass AStar:def __init__(self, map):self.map=mapself.open_set = []self.close_set = []def BaseCost(self, p):x_dis = p.xy_dis = p.y# Distance to start pointreturn x_dis + y_dis + (np.sqrt(2) - 2) * min(x_dis, y_dis)def HeuristicCost(self, p):x_dis = self.map.size - 1 - p.xy_dis = self.map.size - 1 - p.y# Distance to end pointreturn x_dis + y_dis + (np.sqrt(2) - 2) * min(x_dis, y_dis)def TotalCost(self, p):return self.BaseCost(p) + self.HeuristicCost(p)def IsValidPoint(self, x, y):if x < 0 or y < 0:return Falseif x >= self.map.size or y >= self.map.size:return Falsereturn not self.map.IsObstacle(x, y)def IsInPointList(self, p, point_list):for point in point_list:if point.x == p.x and point.y == p.y:return Truereturn Falsedef IsInOpenList(self, p):return self.IsInPointList(p, self.open_set)def IsInCloseList(self, p):return self.IsInPointList(p, self.close_set)def IsStartPoint(self, p):return p.x == 0 and p.y ==0def IsEndPoint(self, p):return p.x == self.map.size-1 and p.y == self.map.size-1

這里的函數(shù)說明如下：

• __init__：類的構(gòu)造函數(shù)。
• BaseCost：節(jié)點(diǎn)到起點(diǎn)的移動(dòng)代價(jià)，對(duì)應(yīng)了上文的g(n)。
• HeuristicCost：節(jié)點(diǎn)到終點(diǎn)的啟發(fā)函數(shù)，對(duì)應(yīng)上文的h(n)。由于我們是基于網(wǎng)格的圖形，所以這個(gè)函數(shù)和上一個(gè)函數(shù)用的是對(duì)角距離。
• TotalCost：代價(jià)總和，即對(duì)應(yīng)上面提到的f(n)。
• IsValidPoint：判斷點(diǎn)是否有效，不在地圖內(nèi)部或者障礙物所在點(diǎn)都是無效的。
• IsInPointList：判斷點(diǎn)是否在某個(gè)集合中。
• IsInOpenList：判斷點(diǎn)是否在open_set中。
• IsInCloseList：判斷點(diǎn)是否在close_set中。
• IsStartPoint：判斷點(diǎn)是否是起點(diǎn)。
• IsEndPoint：判斷點(diǎn)是否是終點(diǎn)。

有了上面這些輔助函數(shù)，就可以開始實(shí)現(xiàn)算法主邏輯了，相關(guān)代碼如下：

# a_star.py def RunAndSaveImage(self, ax, plt):start_time = time.time()start_point = point.Point(0, 0)start_point.cost = 0self.open_set.append(start_point)while True:index = self.SelectPointInOpenList()if index < 0:print('No path found, algorithm failed!!!')returnp = self.open_set[index]rec = Rectangle((p.x, p.y), 1, 1, color='c')ax.add_patch(rec)self.SaveImage(plt)if self.IsEndPoint(p):return self.BuildPath(p, ax, plt, start_time)del self.open_set[index]self.close_set.append(p)# Process all neighborsx = p.xy = p.yself.ProcessPoint(x-1, y+1, p)self.ProcessPoint(x-1, y, p)self.ProcessPoint(x-1, y-1, p)self.ProcessPoint(x, y-1, p)self.ProcessPoint(x+1, y-1, p)self.ProcessPoint(x+1, y, p)self.ProcessPoint(x+1, y+1, p)self.ProcessPoint(x, y+1, p)

這段代碼應(yīng)該不需要太多解釋了，它就是根據(jù)前面的算法邏輯進(jìn)行實(shí)現(xiàn)。為了將結(jié)果展示出來，我們?cè)谒惴ㄟM(jìn)行的每一步，都會(huì)借助于matplotlib庫(kù)將狀態(tài)保存成圖片。

上面這個(gè)函數(shù)調(diào)用了其他幾個(gè)函數(shù)代碼如下：

# a_star.py def SaveImage(self, plt):millis = int(round(time.time() * 1000))filename = './' + str(millis) + '.png'plt.savefig(filename)def ProcessPoint(self, x, y, parent):if not self.IsValidPoint(x, y):return # Do nothing for invalid pointp = point.Point(x, y)if self.IsInCloseList(p):return # Do nothing for visited pointprint('Process Point [', p.x, ',', p.y, ']', ', cost: ', p.cost)if not self.IsInOpenList(p):p.parent = parentp.cost = self.TotalCost(p)self.open_set.append(p)def SelectPointInOpenList(self):index = 0selected_index = -1min_cost = sys.maxsizefor p in self.open_set:cost = self.TotalCost(p)if cost < min_cost:min_cost = costselected_index = indexindex += 1return selected_indexdef BuildPath(self, p, ax, plt, start_time):path = []while True:path.insert(0, p) # Insert firstif self.IsStartPoint(p):breakelse:p = p.parentfor p in path:rec = Rectangle((p.x, p.y), 1, 1, color='g')ax.add_patch(rec)plt.draw()self.SaveImage(plt)end_time = time.time()print('===== Algorithm finish in', int(end_time-start_time), ' seconds')

這三個(gè)函數(shù)應(yīng)該是比較容易理解的：

• SaveImage：將當(dāng)前狀態(tài)保存到圖片中，圖片以當(dāng)前時(shí)間命名。
• ProcessPoint：針對(duì)每一個(gè)節(jié)點(diǎn)進(jìn)行處理：如果是沒有處理過的節(jié)點(diǎn)，則計(jì)算優(yōu)先級(jí)設(shè)置父節(jié)點(diǎn)，并且添加到open_set中。
• SelectPointInOpenList：從open_set中找到優(yōu)先級(jí)最高的節(jié)點(diǎn)，返回其索引。
• BuildPath：從終點(diǎn)往回沿著parent構(gòu)造結(jié)果路徑。然后從起點(diǎn)開始繪制結(jié)果，結(jié)果使用綠色方塊，每次繪制一步便保存一個(gè)圖片。

測(cè)試入口

最后是程序的入口邏輯，使用上面寫的類來查找路徑：

# main.pyimport numpy as np import matplotlib.pyplot as pltfrom matplotlib.patches import Rectangleimport random_map import a_starplt.figure(figsize=(5, 5))map = random_map.RandomMap() ①ax = plt.gca() ax.set_xlim([0, map.size]) ② ax.set_ylim([0, map.size])for i in range(map.size): ③for j in range(map.size):if map.IsObstacle(i,j):rec = Rectangle((i, j), width=1, height=1, color='gray')ax.add_patch(rec)else:rec = Rectangle((i, j), width=1, height=1, edgecolor='gray', facecolor='w')ax.add_patch(rec)rec = Rectangle((0, 0), width = 1, height = 1, facecolor='b') ax.add_patch(rec) ④rec = Rectangle((map.size-1, map.size-1), width = 1, height = 1, facecolor='r') ax.add_patch(rec) ⑤plt.axis('equal') ⑥ plt.axis('off') plt.tight_layout() #plt.show()a_star = a_star.AStar(map) a_star.RunAndSaveImage(ax, plt) ⑦

這段代碼說明如下：

創(chuàng)建一個(gè)隨機(jī)地圖；

設(shè)置圖像的內(nèi)容與地圖大小一致；

繪制地圖：對(duì)于障礙物繪制一個(gè)灰色的方塊，其他區(qū)域繪制一個(gè)白色的的方塊；

繪制起點(diǎn)為藍(lán)色方塊；

繪制終點(diǎn)為紅色方塊；

設(shè)置圖像的坐標(biāo)軸比例相等并且隱藏坐標(biāo)軸；

調(diào)用算法來查找路徑；

由于我們的地圖是隨機(jī)的，所以每次運(yùn)行的結(jié)果可能會(huì)不一樣，下面是我的電腦上某次運(yùn)行的結(jié)果：

如果感興趣這篇文章中的動(dòng)圖是如何制作的，請(qǐng)看我的另外一篇文章：使用Matplotlib繪制3D圖形 - 制作動(dòng)圖。

算法變種

A*算法有不少的變種，這里我們介紹最主要的幾個(gè)。

更多的內(nèi)容請(qǐng)以訪問維基百科：A* Variants。

ARA*

ARA?全稱是Anytime Repairing A*，也稱為Anytime A。

與其他Anytime算法一樣，它具有靈活的時(shí)間成本，即使在它結(jié)束之前被中斷，也可以返回路徑查找或圖形遍歷問題的有效解決方案。方法是在逐步優(yōu)化之前生成快速，非最優(yōu)的結(jié)果。

在現(xiàn)實(shí)世界的規(guī)劃問題中，問題的解決時(shí)間往往是有限的。與時(shí)間相關(guān)的規(guī)劃者對(duì)這種情況都會(huì)比較熟悉：他們能夠快速找到可行的解決方案，然后不斷努力改進(jìn)，直到時(shí)間用完為止。

啟發(fā)式搜索ARA*算法，它根據(jù)可用的搜索時(shí)間調(diào)整其性能邊界。它首先使用松散邊界快速找到次優(yōu)解，然后在時(shí)間允許的情況下逐漸收緊邊界。如果有足夠的時(shí)間，它會(huì)找到可證明的最佳解決方方案。在改進(jìn)其約束的同時(shí)，ARA*重復(fù)使用以前的搜索工作，因此，比其他隨時(shí)搜索方法更有效。

與A*算法不同，Anytime A*算法最重要的功能是，它們可以被停止，然后可以隨時(shí)重啟。該方法使用控制管理器類來處理時(shí)間限制以及停止和重新啟動(dòng)A*算法以找到初始的，可能是次優(yōu)的解決方案，然后繼續(xù)搜索改進(jìn)的解決方案，直到達(dá)到可證明的最佳解決方案。

關(guān)于ARA*的更多內(nèi)容可以閱讀這篇論文：

• ARA?- Anytime A?with Provable Bounds on Sub-Optimality。

D*

D*是Dynamic A*的簡(jiǎn)寫，其算法和A*類似，不同的是，其代價(jià)的計(jì)算在算法運(yùn)行過程中可能會(huì)發(fā)生變化。

D*包含了下面三種增量搜索算法：

• 原始的D*由Anthony Stentz發(fā)表。
• Focussed D*由Anthony Stentz發(fā)表，是一個(gè)增量啟發(fā)式搜索算法，結(jié)合了A*和原始D*的思想。
• D?Lite是由Sven Koenig和Maxim Likhachev基于LPA構(gòu)建的算法。

所有三種搜索算法都解決了相同的基于假設(shè)的路徑規(guī)劃問題，包括使用自由空間假設(shè)進(jìn)行規(guī)劃。在這些環(huán)境中，機(jī)器人必須導(dǎo)航到未知地形中的給定目標(biāo)坐標(biāo)。它假設(shè)地形的未知部分（例如：它不包含障礙物），并在這些假設(shè)下找到從當(dāng)前坐標(biāo)到目標(biāo)坐標(biāo)的最短路徑。

然后機(jī)器人沿著路徑行進(jìn)。當(dāng)它觀察到新的地圖信息（例如以前未知的障礙物）時(shí)，它會(huì)將信息添加到其地圖中，并在必要時(shí)將新的最短路徑從其當(dāng)前坐標(biāo)重新添加到給定的目標(biāo)坐標(biāo)。它會(huì)重復(fù)該過程，直到達(dá)到目標(biāo)坐標(biāo)或確定無法達(dá)到目標(biāo)坐標(biāo)。在穿越未知地形時(shí)，可能經(jīng)常發(fā)現(xiàn)新的障礙，因此重新計(jì)劃需要很快。增量（啟發(fā)式）搜索算法通過使用先前問題的經(jīng)驗(yàn)來加速搜索當(dāng)前問題，從而加速搜索類似搜索問題的序列。假設(shè)目標(biāo)坐標(biāo)沒有改變，則所有三種搜索算法都比重復(fù)的A*搜索更有效。

D*及其變體已廣泛用于移動(dòng)機(jī)器人和自動(dòng)車輛導(dǎo)航。當(dāng)前系統(tǒng)通常基于D* Lite而不是原始D*或Focussed D*。

關(guān)于D*的更多內(nèi)容可以閱讀這兩篇文章：

• Project "Fast Replanning （Incremental Heuristic Search）"
• Real-Time Replanning in Dynamic and Unknown Environments

Field D*

Field D*擴(kuò)展了D*和D* Lite，是一種基于插值（ interpolation-based ）的規(guī)劃算法，它使用線性插值來有效地生成低成本路徑，從而消除不必要的轉(zhuǎn)向。

在給定線性插值假設(shè)的情況下，路徑是最優(yōu)的，并且在實(shí)踐中非常有效。該算法目前被各種現(xiàn)場(chǎng)機(jī)器人系統(tǒng)使用。

關(guān)于Field D*的詳細(xì)內(nèi)容可以看下面這篇論文：

• Field D*: An Interpolation-based Path Planner and Replanner

Block A*

Block A*擴(kuò)展自A*，但它操作是一塊（block）單元而不是單個(gè)單元。

其open_set中的每個(gè)條目都是已到達(dá)但尚未擴(kuò)展的塊，或者需要重新擴(kuò)展的塊。

open_set中塊的優(yōu)先級(jí)稱為其堆值（heap value）。與A*類似，Block A*中的基本循環(huán)是刪除具有最低堆值的條目并將其展開。在擴(kuò)展期間使用LDDB來計(jì)算正在擴(kuò)展的塊中的邊界單元的g值。

LDDB是一種新型數(shù)據(jù)庫(kù)，它包含了本地鄰域邊界點(diǎn)之間的距離。

關(guān)于Block A*的更多內(nèi)容可以看下面這篇論文：

• Block A*: Database-Driven Search with Applications in Any-angle Path-Planning

?

原文鏈接
本文為云棲社區(qū)原創(chuàng)內(nèi)容，未經(jīng)允許不得轉(zhuǎn)載。

總結(jié)

以上是生活随笔為你收集整理的路径规划之 A* 算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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